|
%I
%S 1,0,3,4700063497,6,19147,10669,25,9,2228071,18,262279,3763,95,1010,
%T 481,20,45,35,2873,2951,3175999,42,555,50,95921,27,174934013,36,777,
%U 49,140039,56,2463240427,110,477,697,91,578,623,156,2453,540923,55,70,345119,287
%N Least inverse of A015910: smallest integer k > 0 such that 2^k mod k = n, or 0 if no such k exists.
%C 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. [From Max Alekseyev]
%C Labos Elemer (labos(AT)ana.sote.hu) asked on Sept 27, 2001 if all numbers > 1 eventually appear in A015910, that is, if a(n) > 0 for n > 1.
%C a(n) > 10^11 for n = 69, 185, 231, 273, 309, 311, 405, 465, 581, 619, 649, 669, 675, 741, 771, 799, 849, 871, 881, 885, 939, 981, ... - _Hans Havermann_, Apr 19 2007
%D P. Erdos and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathematique, 28, 1980.
%D R. K. Guy, Unsolved Problems in Number Theory, Section F10.
%H Joe K. Crump, <a href="http://www.immortaltheory.com/NumberTheory/2nmodn.htm">2^n mod n</a>
%H Hans Havermann, <a href="/A036236/a036236.txt">Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/2.html">2</a>
%H David W. Wilson, <a href="/A036236/b036236.txt">Table of n, a(n) for n = 0..1026</a> (from the Havermann file)
%F 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
%e n = 0: 2^1 mod 1 = 0, a(0) = 1;
%e n = 1: 2^k mod k = 1, no such k exists, so a(1) = 0;
%e n = 2: 2^3 mod 3 = 2, a(2) = 3;
%e n = 3: 2^4700063497 mod 4700063497 = 3, a(3) = 4700063497.
%t 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
%t 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
%o (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
%Y Cf. A015910, A015948, A078457, A119678, A119679, A127816, A119715, A119714, A127817, A127818, A127819, A127820, A127821.
%Y Bisections: A122182, A124977.
%K nonn,nice,changed
%O 0,3
%A _David W. Wilson_
%E a(3) was first computed by the Lehmers.
%E More terms from Joe K. Crump (joecr(AT)carolina.rr.com), Sep 04 2000
%E a(69) = 887817490061261 = 29 * 37 * 12967 * 63809371. [From _Hagen von Eitzen_, Jul 26 2009]
%E Edited by _Max Alekseyev_, Jul 29 2011
|
