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 2

The property is satisfied by these two values of n: 4700063497 and also by 63130707451134435989380140059866138830623361447484274774099906755.

Max Alekseyev

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

(1) In order that 485 divide 2

(2) In order that q divide 2

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

(5) Any prime factor of 2

(6) Are there any values n in between (6.b) and (6.c) that satisfy:

n|[(2^{n})-3] |
(6.a) |

(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 |