Sorry, an error occurred while loading the content.

## Re: [PrimeNumbers] GCD result

Expand Messages
• 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 1 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.
Ask your question on www.Answers.yahoo.com

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

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 2 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.