A036236 Least inverse of A015910: smallest integer k > 0 such that 2^k mod k = n, or 0 if no such k exists.

1, 0, 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, 2463240427, 110, 477, 697, 91, 578, 623, 156, 2453, 540923, 55, 70, 345119, 287

Offset: 0

Author

David W. Wilson

Keywords

• nonn
• nice

Comments

a(1) = 0, that is, no n exists with 2^n mod n = 1. Proof: Assume that there exists such n > 1. Consider its smallest prime divisor p. Then 2^n == 1 (mod p) implying that the multiplicative order ord_p(2) divides n. However, since ord_p(2) < p and p is the smallest divisor of n, we have ord_p(2) = 1, that is, p divides 2^1 - 1 = 1 which is impossible. - Max Alekseyev

_Labos Elemer_ asked on Sep 27 2001 if all numbers > 1 eventually appear in A015910, that is, if a(n) > 0 for n > 1.

Ron Graham's conjecture from 1960 states that for any n > 1 there are infinitely many solutions to 2^k mod k = n. - Max Alekseyev, Oct 19 2024

Obviously k > n. - Daniel Forgues, Jul 06 2015

Examples

			n = 0: 2^1 mod 1 = 0, a(0) = 1;
n = 1: 2^k mod k = 1, no such k exists, so a(1) = 0;
n = 2: 2^3 mod 3 = 2, a(2) = 3;
n = 3: 2^4700063497 mod 4700063497 = 3, a(3) = 4700063497.
		

References

• P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique, 28, 1980.
• R. K. Guy, Unsolved Problems in Number Theory, Section F10.

Links

• David W. Wilson, Table of n, a(n) for n = 0..1026 (from the Havermann file)
• Joe K. Crump, 2^n mod n
• Hans Havermann, Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown
• Nick Hobson, Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown. [With 101 new terms and 2 corrections, this supersedes the earlier table from Hans Havermann. The corrections are to terms a(799) and a(881), where smaller values of k were found.]
• Nick Hobson, C program
• Eric Weisstein's World of Mathematics, 2

Crossrefs

Cf. A015910, A015948, A078457, A119678, A119679, A127816, A119715, A119714, A127817, A127818, A127819, A127820, A127821.

Bisections: A122182, A124977.

Programs

Mathematica

a = Table[0, {75} ]; Do[ b = PowerMod[2, n, n]; If[b < 76 && a[[b]] == 0, a[[b]] = n], {n, 1, 5*10^9} ]; a
(* Second program: *)
t = Table[0, {1000} ]; k = 1; While[ k < 6500000000, b = PowerMod[2, k, k]; If[b < 1001 && t[[b]] == 0, t[[b]] = k]; k++ ]; t
nk[n_] := Module[ {k}, k = 1; While[PowerMod[2, k, k] != n, k++]; k]
Join[{1, 0}, Table[nk[i], {i, 2, 46}]]  (* Robert Price, Oct 11 2018 *)

PARI

a(n)=if(n==1,return(0));my(k=n);while(lift(Mod(2,k)^k)!=n,k++);k \\ Charles R Greathouse IV, Oct 12 2011

Formula

It's obvious that for each k, a(k) > k and we can easily prove that 2^(3^n) = 3^n-1 (mod 3^n). So 3^n is the least k with 2^k mod k = 3^n-1. Hence for each n, a(3^n-1) = 3^n. - Farideh Firoozbakht, Nov 14 2006

Extensions

a(3) was first computed by the Lehmers.

More terms from Joe K. Crump (joecr(AT)carolina.rr.com), Sep 04 2000

a(69) = 887817490061261 = 29 * 37 * 12967 * 63809371. - Hagen von Eitzen, Jul 26 2009

Edited by Max Alekseyev, Jul 29 2011