2^n mod n = e

[Joe Crump]

The online integer encyclopedia contains several sequences
of 2^n mod n.

	http://www.research.att.com/~njas/sequences/index.html

	In particular, the info Richard Guy pointed out is in:

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
um=036236
----------------------------------------------------------------------------
--------------------
ID Number: A036236
Sequence:
3,4700063497,6,19147,10669,25,9,2228071,18,262279,3763,95,1010,481,20,
 
45,35,2873,2951,3175999,42,555,50,95921,27,174934013,36,777,49,140039,
           56
Name:      a(n) = least k with 2^k mod k = n (inverse of A015910).
Comments:  No n exists with 2^n mod n = 1. a(3) first computed by Lehmers.
References R. K. Guy, Unsolved Problems in Number Theory, Section F10.
See also:  Cf. A015910, A036237.
Keywords:  hard,nonn,nice
Offset:    2
Author(s): David Wilson (wilson at ctron.com)
Extension: a(33) <= 319020450922208555, per Dean Hickerson
----------------------------------------------------------------------------
--------------------

	I've added a few in the past, such as 2^n mod n = 7, 11, 15. But,
they
don't go very far (just ran a brute-force app for a few hours)...

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
um=033981
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
um=033982
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
um=033983


	Are there any decent algorithms, or helpful tricks for finding
solutions 'n' to
2^n mod n = e, where 'e' very small, say e <= 31? Or have these numbers
already
been computed and collected somewhere?

Thanks!

- Joe

-----Original Message-----
From: Richard Guy [mailto:rkg at cpsc.ucalgary.ca]
Sent: Thursday, June 10, 1999 8:49 PM
To: NMBRTHRY at LISTSERV.NODAK.EDU
Subject: Re: n|[(2^n)-3] ; Ron Graham ...


There was some email about this recently, from a different enquirer, I
think.  F10 (p.250 of 2nd edition) of UPINT [Unsolved Problems in
Number Theory, by Guy:ed.] states that the Lehmers have shown that the
smallest solution of 2^n = 3 mod n is n=470063497=19*47*5263229.
Graham had asked the Lehmers to look for a solution.  In a sense they
were lucky, as they planned to go only to half a billion.  At the time
there were those who thought that there might not be a solution.  I
don't know of another, and would be interested to learn if one is
found.  It may be that this is the only place that the result is
published.  R.