For what values of n integer is it true that nth power of 2 is 3 mod n? In
terse mathematical symbols this condition can be written 2n == 3 (mod n).
Another way to say this is for what values of n integer is 2 raised
to the nth power, then reduced by 3, evenly divisible by n?
The property is satisfied by these two values of n:
4700063497
and also by 63130707451134435989380140059866138830623361447484274774099906755.
Max Alekseyev pointed out that
Two lists
the value 8365386194032363 found by J. Crump in 2000. Alekseyev found yet
another value, 3468371109448915. {He suggested use of Mathematica's
PowerMod; the online documentation indicates that
PowerMod[a, b, n] gives ab mod n.}
Joe Crump found yet another value, 10991007971508067. His email sent
1/22/07 is appended.
How could we track large quantities?
Words and Symbols
For another view please go to Modulo.
Date: Wed, 14 Jul 1999
To: klinger@cs.ucla.edu
From: R. L. Graham
Subject: Re: Two values. >Re: n|[(2^n)-3]
Dear Allen,
Thanks for the follow-up letter. I think there has been additional electronic
discussion about how Peter Montgomery found this example (according to
Andrew Odlyzko at AT&T Labs).
... The next trick is to show
that there are infinitely (many) such numbers n such that n | 2^n -3.
Best regards,
Ron Graham
Date: Thu, 15 Jul 1999
To: klinger@cs.ucla.edu
From: Andrew Odlyzko
Subject: Re: please let me know about
Dear Allen,
Peter Montgomery's message to the NMBRTHRY list is enclosed below.
Best regards,
Andrew
Date: Thu, 24 Jun 1999
From: Peter Lawrence Montgomery
Sender: Number Theory List
Subject: New solution to 2^n == 3 (mod n)
According to problem F10 in Richard Guy's `Unsolved Problems in Number Theory',
the only known
solution to the congruence 2^n == 3 (mod n) with n > 1 is n = 19 * 47 * 5263229.
The 65-digit number n2 below is another solution. It was found on June 23, 1999 at CWI, Amsterdam.
This n2 was found by guessing that the solution would
have the (form) n = r * q, where r = 485 and q is prime.
In order that 485 divide 2^n - 3 we require n == 19 (mod 48).
In order that q divide 2^n - 3 we require q divide 2^r - 3.
The factorization of 2^485 - 3 was achieved by the number field
sieve algorithm. It took one CPU-month, spread over three
calendar-days, using SGI and SPARC workstations at CWI.
One prime factor, called p63 below, is in the desired
congruence class (mod 48) and gives the new solution.
Ostensibly there are phi(48) = 16 potential congruence classes
for primes modulo 48, but we know that 6 is a quadratic
residue modulo any factor of 2^485 - 3.
Hence any prime factor of 2^485 - 3 will be congruent to
1, 5, 19, or 23 modulo 24, giving only eight possibilities modulo 48.
This made r = 485 especially worthy of investigation.
I have tried to factor 2^r - 3 for several other r, primarily
by the elliptic curve method, without finding another solution
to the congruence. I thank Paul Leyland (Microsoft Research)
and Paul Zimmermann (Inria) for assisting in these factorizations.
Peter Montgomery
Microsoft Research and CWI
############## Maple code below
n1 := 19 * 47 * 5263229;
2 &^ n1 mod n1; # 3
p63 := 130166407115741105132742556824466265630151260716462422214638983;
n2 := 5 * 97 * p63;
2 &^ n2 mod n2; # 3
p63 mod 48;
n2 mod 48;
evalf(n2);
p68 := 22341942494294113473321292753921092454785291734670955227136157571499;
(2^485 - 3)/(53 * 53 * 2285189 * 5351237 * p63 * p68); # 1
isprime(p63);
isprime(p68);
;quit;
************************************************************************
Andrew Odlyzko
AT&T Labs - Research
************************************************************************
Date: 11/13/06
From: Max Alekseyev
Subject: a new solution to 2^n = 3 (mod n)
Dear Allen,
Your web page indicates that you may be interested in this computational
result.
I have found a new solution to the congruence 2^n = 3 (mod n), which is
n = 3468371109448915
So, the total number of known solutions became 4. :)
Regards,
Max
Date: 1/22/07
Inspired by recent
communications, I looked back into this problem and was able to find
another solution.
10991007971508067 = 97 * 15287 * 7412138453
This brings the list of known solutions to:
4700063497
3468371109448915
8365386194032363
10991007971508067
63130707451134435989380140059866138830623361447484274774099906755
Joe K. Crump
Needed Clarifications
(1) In order that 485 divide 2n - 3 we require n == 19 (mod 48).
(2) In order that q divide 2n - 3 we require q divide 2r - 3.
(3) Ostensibly there are phi(48) = 16 potential congruence classes for primes modulo 48
(4) We know that 6 is a quadratic
residue modulo any factor of 2485 - 3.
(5) Any prime factor of 2485 - 3 will be congruent to
1, 5, 19, or 23 modulo 24, giving only eight possibilities modulo 48.
(This made r = 485 especially worthy of investigation.)
(6) Are there any values n in between (6.b) and (6.c) that satisfy:
n|[(2n)-3]
(6.a)
(6.b)
4700063497
(6.c)
63130707451134435989380140059866138830623361447484274774099906755
Most of the results came from communicating by email to
NMBRTHRY@LISTSERV.NODAK.EDU.