Recent Communications
Recent Communications - Includes 11/13/06, 1/22/07 Updates

Allen Klinger, © 1/22/2007

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 large are these numbers?

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.
22 Jan 2007 Version http://www.cs.ucla.edu/~klinger/newno.html
©2007 Allen Klinger