Expand Messages
• ... Hard to prove, because it s false. For example: GCD(254, 2^(2*254^2)-2) = 254. GCD(423, 2^(2*423^2)-2) = 47. similarly 635 - a GCD of 127 658 - 94 1143
Message 1 of 6 , Jan 27, 2007
On 1/27/07, Sebastian Martin <sebi_sebi@...> wrote:
> Prove that:
>
> GCD(n,2^(2n^2) - 2)= 1 if n is odd
> 2 if n is even
> for all integer n.

Hard to prove, because it's false.

For example:
GCD(254, 2^(2*254^2)-2) = 254.
GCD(423, 2^(2*423^2)-2) = 47.
similarly 635 -> a GCD of 127
658 -> 94
1143 -> 127
1504 -> 94
1524 -> 254
1739 -> 47
2032 -> 254
2413 -> 127
2585 -> 47

Now, explaining why 47 and 127 appear as the common factors (other
than the obvious 1s and 2s), that sounds like it might be interesting.

Are there other (larger) numbers that will appear later?

--Joshua Zucker
• Removing individuals from the To: list. I know I certainly don t need to receive things both by direct mail and the list, and am projecting that onto others.
Message 2 of 6 , Jan 28, 2007
Removing individuals from the To: list. I know I certainly don't need to
receive things both by direct mail and the list, and am projecting that onto
others.

--- Joshua Zucker <joshua.zucker@...> wrote:
> On 1/27/07, Sebastian Martin <sebi_sebi@...> wrote:
> > Prove that:
> >
> > GCD(n,2^(2n^2) - 2)= 1 if n is odd
> > 2 if n is even
> > for all integer n.
>
> Hard to prove, because it's false.

And not just false, but ...

> For example:
> GCD(254, 2^(2*254^2)-2) = 254.
> GCD(423, 2^(2*423^2)-2) = 47.

... you guessed it - falsifiable with very small examples that can be found in

? for(n=1,500,g=gcd(n,lift(Mod(2,n)^(2*n^2))-2);if(g>2-n%2,print(n" "g)))
254 254
423 47
time = 0 ms.

no time at all!

> similarly 635 -> a GCD of 127
> 658 -> 94
> 1143 -> 127
> 1504 -> 94
> 1524 -> 254
> 1739 -> 47
> 2032 -> 254
> 2413 -> 127
> 2585 -> 47
>
> Now, explaining why 47 and 127 appear as the common factors (other
> than the obvious 1s and 2s), that sounds like it might be interesting.
>
> Are there other (larger) numbers that will appear later?

Pruning:

?
for(n=1,10000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127,print(n"
"factor(g))))
7024 Mat([439, 1])
8843 Mat([239, 1])
time = 84 ms.

Pruning further:

?
for(n=10000,100000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127&&g!=239&&g!=439,print(n"
"factor(g))))
11601 Mat([1289, 1])
25661 Mat([383, 1])
33530 Mat([479, 1])
47020 Mat([2351, 1])
47492 Mat([383, 1])
47693 Mat([1289, 1])
58871 Mat([3463, 1])
63477 Mat([2351, 1])
75837 Mat([1487, 1])
80129 Mat([11447, 1])
80951 Mat([479, 1])
81122 Mat([863, 1])
90260 Mat([4513, 1])
94045 Mat([2687, 1])
98814 Mat([383, 1])

Pruning even further:
?
for(n=100000,1000000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127&&g!=239&&g!=439&&g!=383&&g!=479&&g!=863&&g!=1289&&g!=1487&&g!=2351&&g!=2687&&g!=3463&&g!=4513&&g!=11447,print(n"
"factor(g))))
103526 Mat([1399, 1])
105121 Mat([3391, 1])
122230 Mat([719, 1])
129806 Mat([1583, 1])
133910 Mat([1913, 1])
135891 Mat([719, 1])
160404 Mat([13367, 1])
160424 Mat([1823, 1])
222441 Mat([1399, 1])
233118 Mat([1439, 1])
236587 Mat([18199, 1])
244729 [47, 1; 127, 1]
247126 [47, 1; 239, 1]
278062 Mat([3391, 1])
302122 Mat([5209, 1])
314739 Mat([11657, 1])
323297 Mat([1913, 1])
324206 Mat([3449, 1])
355327 Mat([2207, 1])
367372 Mat([3167, 1])
380351 Mat([719, 1])
382016 [47, 1; 127, 1]
387643 Mat([13367, 1])
393213 Mat([131071, 1])
394012 Mat([719, 1])
400377 Mat([3607, 1])
401590 Mat([5737, 1])
406831 Mat([1583, 1])
416783 Mat([18121, 1])
429493 Mat([1399, 1])
431079 Mat([13063, 1])
452335 Mat([6959, 1])
459699 Mat([4943, 1])
463601 Mat([5209, 1])
488304 Mat([3391, 1])
510598 Mat([23209, 1])
525518 Mat([37537, 1])
532048 Mat([3023, 1])
539036 Mat([7927, 1])
548408 Mat([1399, 1])
550773 Mat([20399, 1])
555051 Mat([26431, 1])
575577 Mat([2063, 1])
578993 [47, 1; 127, 1]
591117 Mat([1913, 1])
638472 Mat([719, 1])
652133 Mat([719, 1])
661245 Mat([3391, 1])
666752 Mat([5209, 1])
698119 [127, 1; 239, 1]
699325 Mat([2543, 1])
708451 Mat([13367, 1])
716280 [47, 1; 127, 1]
721649 Mat([23279, 1])
748547 Mat([20231, 1])
755460 Mat([1399, 1])
780504 Mat([1913, 1])
801523 Mat([1439, 1])
818515 [127, 1; 1289, 1]
828231 Mat([5209, 1])
845322 Mat([1583, 1])
871487 Mat([3391, 1])
874375 Mat([1399, 1])
896593 Mat([719, 1])
910254 Mat([719, 1])
915291 Mat([7823, 1])
935690 Mat([13367, 1])
948831 Mat([24329, 1])
964458 Mat([4871, 1])
969553 Mat([5737, 1])
time = 10,649 ms.

What do we conclude from this:

1) Post not requests for proofs of simply-falsifiable things to multiple
mailing lists, lest thee bring upon thyself a gargantuan public shaming in
so-doing.

2) Use Pari/GP to avoid (1)

3) Other stuff, dunno what. Joshua - do you want to take over from here?

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________
Need a quick answer? Get one in minutes from people who know.
• ... The first appearance of all primes that appear before n=30000000 can be found in the file gcd(n,2^(2n^2)-2) in the Prime Tables folder of the
Message 3 of 6 , Jan 28, 2007
--- Phil Carmody <thefatphil@...> wrote:
> 3) Other stuff, dunno what. Joshua - do you want to take over from here?

The first appearance of all primes that appear before n=30000000 can be found
in the file "gcd(n,2^(2n^2)-2)" in the Prime Tables folder of the primenumbers
yahoogroup.

Some primes appear quite late. p=11423 only appears at n=29596993.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________
Learn how on Yahoo! Small Business.
• I am sorry to have committed this mistake. I promise to check better the results. But I verified it for several chains of 200 numbers and only 1 and 2 were
Message 4 of 6 , Jan 28, 2007
I am sorry to have committed this mistake.
I promise to check better the results.
But I verified it for several chains of 200 numbers and only 1 and 2 were going out.
Nevertheless I believe that this has interest.

Sincerely

Serbastian Martin Ruiz

Phil Carmody <thefatphil@...> escribió:
Removing individuals from the To: list. I know I certainly don't need to
receive things both by direct mail and the list, and am projecting that onto
others.

--- Joshua Zucker <joshua.zucker@...> wrote:
> On 1/27/07, Sebastian Martin <sebi_sebi@...> wrote:
> > Prove that:
> >
> > GCD(n,2^(2n^2) - 2)= 1 if n is odd
> > 2 if n is even
> > for all integer n.
>
> Hard to prove, because it's false.

And not just false, but ...

> For example:
> GCD(254, 2^(2*254^2)-2) = 254.
> GCD(423, 2^(2*423^2)-2) = 47.

... you guessed it - falsifiable with very small examples that can be found in

? for(n=1,500,g=gcd(n,lift(Mod(2,n)^(2*n^2))-2);if(g>2-n%2,print(n" "g)))
254 254
423 47
time = 0 ms.

no time at all!

> similarly 635 -> a GCD of 127
> 658 -> 94
> 1143 -> 127
> 1504 -> 94
> 1524 -> 254
> 1739 -> 47
> 2032 -> 254
> 2413 -> 127
> 2585 -> 47
>
> Now, explaining why 47 and 127 appear as the common factors (other
> than the obvious 1s and 2s), that sounds like it might be interesting.
>
> Are there other (larger) numbers that will appear later?

Pruning:

?
for(n=1,10000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127,print(n"
"factor(g))))
7024 Mat([439, 1])
8843 Mat([239, 1])
time = 84 ms.

Pruning further:

?
for(n=10000,100000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127&&g!=239&&g!=439,print(n"
"factor(g))))
11601 Mat([1289, 1])
25661 Mat([383, 1])
33530 Mat([479, 1])
47020 Mat([2351, 1])
47492 Mat([383, 1])
47693 Mat([1289, 1])
58871 Mat([3463, 1])
63477 Mat([2351, 1])
75837 Mat([1487, 1])
80129 Mat([11447, 1])
80951 Mat([479, 1])
81122 Mat([863, 1])
90260 Mat([4513, 1])
94045 Mat([2687, 1])
98814 Mat([383, 1])

Pruning even further:
?
for(n=100000,1000000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127&&g!=239&&g!=439&&g!=383&&g!=479&&g!=863&&g!=1289&&g!=1487&&g!=2351&&g!=2687&&g!=3463&&g!=4513&&g!=11447,print(n"
"factor(g))))
103526 Mat([1399, 1])
105121 Mat([3391, 1])
122230 Mat([719, 1])
129806 Mat([1583, 1])
133910 Mat([1913, 1])
135891 Mat([719, 1])
160404 Mat([13367, 1])
160424 Mat([1823, 1])
222441 Mat([1399, 1])
233118 Mat([1439, 1])
236587 Mat([18199, 1])
244729 [47, 1; 127, 1]
247126 [47, 1; 239, 1]
278062 Mat([3391, 1])
302122 Mat([5209, 1])
314739 Mat([11657, 1])
323297 Mat([1913, 1])
324206 Mat([3449, 1])
355327 Mat([2207, 1])
367372 Mat([3167, 1])
380351 Mat([719, 1])
382016 [47, 1; 127, 1]
387643 Mat([13367, 1])
393213 Mat([131071, 1])
394012 Mat([719, 1])
400377 Mat([3607, 1])
401590 Mat([5737, 1])
406831 Mat([1583, 1])
416783 Mat([18121, 1])
429493 Mat([1399, 1])
431079 Mat([13063, 1])
452335 Mat([6959, 1])
459699 Mat([4943, 1])
463601 Mat([5209, 1])
488304 Mat([3391, 1])
510598 Mat([23209, 1])
525518 Mat([37537, 1])
532048 Mat([3023, 1])
539036 Mat([7927, 1])
548408 Mat([1399, 1])
550773 Mat([20399, 1])
555051 Mat([26431, 1])
575577 Mat([2063, 1])
578993 [47, 1; 127, 1]
591117 Mat([1913, 1])
638472 Mat([719, 1])
652133 Mat([719, 1])
661245 Mat([3391, 1])
666752 Mat([5209, 1])
698119 [127, 1; 239, 1]
699325 Mat([2543, 1])
708451 Mat([13367, 1])
716280 [47, 1; 127, 1]
721649 Mat([23279, 1])
748547 Mat([20231, 1])
755460 Mat([1399, 1])
780504 Mat([1913, 1])
801523 Mat([1439, 1])
818515 [127, 1; 1289, 1]
828231 Mat([5209, 1])
845322 Mat([1583, 1])
871487 Mat([3391, 1])
874375 Mat([1399, 1])
896593 Mat([719, 1])
910254 Mat([719, 1])
915291 Mat([7823, 1])
935690 Mat([13367, 1])
948831 Mat([24329, 1])
964458 Mat([4871, 1])
969553 Mat([5737, 1])
time = 10,649 ms.

What do we conclude from this:

1) Post not requests for proofs of simply-falsifiable things to multiple
mailing lists, lest thee bring upon thyself a gargantuan public shaming in
so-doing.

2) Use Pari/GP to avoid (1)

3) Other stuff, dunno what. Joshua - do you want to take over from here?

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________________
Need a quick answer? Get one in minutes from people who know.

---------------------------------

LLama Gratis a cualquier PC del Mundo.
Llamadas a fijos y móviles desde 1 céntimo por minuto.
http://es.voice.yahoo.com

[Non-text portions of this message have been removed]
• ... What is the interest? That is, why all the 2s in 2^(2n^2)-2? Why not -1? Or just n as the exponent? Or just n^2? Or something else? Did this
Message 5 of 6 , Jan 28, 2007
On 1/28/07, Sebastian Martin <sebi_sebi@...> wrote:
> I am sorry to have committed this mistake.
> I promise to check better the results.
> But I verified it for several chains of 200 numbers and only 1 and 2 were going out.
> Nevertheless I believe that this has interest.

What is the interest? That is, why all the 2s in 2^(2n^2)-2? Why not
-1? Or just n as the exponent? Or just n^2? Or something else? Did
this relationship come up in investigating some other idea, or was it
just an arbitrary pick?

Also, to fill in more of what I think is the most interesting part of
the investigation, namely which primes p appear in the gcd here, we
have Max (Thanks Max!)

--Joshua Zucker

from: Max Alekseyev
Odd prime p can divide gcd(n, 2^(2n^2)-2) if and only if the
multiplicative order of 2 modulo p is odd and 2 is a square modulo
this order.
The following simple PARI script gives a list of all such primes below 10^4:

forprime(p=3,10^4, q=znorder(Mod(2,p)); if( (q%2) &&
issquare(Mod(2,q)), print1(p,", ")) )

47, 127, 239, 383, 439, 479, 719, 863, 1289, 1399, 1439, 1487, 1583,
1823, 1913, 2063, 2207, 2351, 2447, 2543, 2687, 2879, 3023, 3119,
3167, 3359, 3391, 3449, 3463, 3607, 4079, 4127, 4463, 4513, 4567,
4703, 4799, 4871, 4943, 5087, 5209, 5519, 5737, 5807, 6047, 6089,
6287, 6719, 6791, 6857, 6863, 6959, 7247, 7583, 7727, 7823, 7927,
8167, 8447, 8543, 8783, 9431, 9743, 9839, 9887

I will give an example of n such that 719 divides gcd(n, 2^(2n^2)-2).

The multiplicative order of 2 modulo 719 is 359. Therefore, 719
divides gcd(n, 2^(2n^2)-2) if and only if
n = 0 (mod 719)
2n^2 - 1 = 0 (mod 359) ==> n = +- 170 (mod 359)
This system of congruences have a solution
n = 122230 or 135891 (mod 258121)

In particular, for n=122230 we have gcd(n, 2^(2n^2)-2)=1438 which is a
multiple of 719 (as expected).

Max
Your message has been successfully submitted and would be delivered to recipients shortly.