A333433 a(n) is the n-th number m that divides n^m - 1 (or 0 if m does not exist).

1, 0, 4, 21, 8, 1555, 9, 6223, 40, 999, 20, 130801, 24, 4484077, 128, 117, 60, 118285781329, 42, 1432001198261, 104, 819, 72, 302508121, 81, 75625, 200, 61731, 78, 14507145975869, 72, 21958351241, 820, 12321, 289, 4375, 144

Offset

1,3

Comments

From Jinyuan Wang, Mar 25 2020: (Start)

For n > 2, n < a(n) < q^(n-1), where q is a prime factor of n - 1.

If p is a prime, then a(p^e+1) is divisible by p. Proof: we can prove that p | m for m > 1 and n = p^e + 1. If n^m == 1 (mod m) and m > 1 is the minimum value that cannot be divisible by p, then gcd(m, eulerphi(m)) = 1. Thus, m must be of the form q*p_2*...*p_k, where q < p_2 < ... < p_k. Note that q | (n^m - 1) = (n^q - 1)*(Sum_{i=0..(m/q)-1} n)^(i*q)) and n^q - 1 can never be divisible by q. Therefore, Sum_{i=0..(m/q)-1} n^(i*q) == n^(m/q) - 1 == 0 (mod q). Because n^(q-1) == 1 (mod q) and gcd(m/q, q - 1) = 1, then n == 1 (mod q), a contradiction! (End)

a(38) <= 14948925257859919. - Giovanni Resta, Apr 15 2020

Links

Table of n, a(n) for n=1..37.

OEIS Wiki, 2^n mod n

Formula

a(n) = A333432(n,n).

Prog

(PARI) {a(n) = if(n==2, 0, my(cnt=0, k=0); while(cnt<n, k++; if(Mod(n, k)^k==1, cnt++)); k)}

Crossrefs

Main diagonal of A333432.

Cf. A014960, A128358, A128360, A333430.

Sequence in context: A083192 A225540 A128452 * A202450 A144292 A338421

Adjacent sequences: A333430 A333431 A333432 * A333434 A333435 A333436

Keyword

nonn,more

Author

Seiichi Manyama, Mar 21 2020

Extensions

a(30)-a(37) from Giovanni Resta, Apr 15 2020

Status

approved