A074792 Least k > 1 such that k^n == 1 (mod n).

2, 3, 4, 3, 6, 5, 8, 3, 4, 9, 12, 5, 14, 13, 16, 3, 18, 5, 20, 3, 4, 21, 24, 5, 6, 25, 4, 13, 30, 11, 32, 3, 34, 33, 36, 5, 38, 37, 16, 3, 42, 5, 44, 21, 16, 45, 48, 5, 8, 9, 52, 5, 54, 5, 16, 13, 7, 57, 60, 7, 62, 61, 4, 3, 66, 23, 68, 13, 70, 29, 72, 5, 74, 73, 16, 37, 78, 17, 80, 3

Offset: 1

Author

Benoit Cloitre, Sep 07 2002

Keywords

• nonn

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000

Crossrefs

a(n) = {A076944(n)}^(1/n).

Cf. A076942, A076943, A076944.

Programs

Mathematica

Do[k = 2; While[ !IntegerQ[(k^n - 1)/n], k++ ]; Print[k], {n, 1, 80}] (* Robert G. Wilson v *)

PARI

a(n)=if(n<0,0,s=2; while((s^n-1)%n>0,s++); s)

PARI

a(n)=my(s=2); while(Mod(s,n)^n-1!=0, s++); return(s) \\ Rémy Sigrist, Apr 02 2017

Formula

If p is prime a(p)=p+1 and a(2p)=2p-1; if n is in A050384 a(n)=n+1; if n is in A067945 a(n)=3 etc. It seems that sum(k=1, n, a(k)) is asymptotic to c*n^2 with c=0.2...