A182816 Number of values b in Z/nZ such that b^n = b.

1, 2, 3, 2, 5, 4, 7, 2, 3, 4, 11, 4, 13, 4, 9, 2, 17, 4, 19, 4, 9, 4, 23, 4, 5, 4, 3, 8, 29, 8, 31, 2, 9, 4, 9, 4, 37, 4, 9, 4, 41, 8, 43, 4, 15, 4, 47, 4, 7, 4, 9, 8, 53, 4, 9, 4, 9, 4, 59, 8, 61, 4, 9, 2, 25, 24, 67, 4, 9, 16, 71, 4, 73, 4, 9, 8, 9, 8, 79, 4, 3, 4, 83, 8, 25, 4, 9, 4, 89, 8, 49, 4, 9, 4, 9, 4, 97, 4, 9, 4, 101, 8, 103, 4, 45, 4, 107, 4, 109, 8, 9, 8, 113

Offset

1,2

Comments

a(n) is the number of nonnegative bases b < n such that b^n == b (mod n).

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Formula

a(n) = n for primes A000040 and Carmichael numbers A002997.

a(n) = Product_{i=1..m} (1 + gcd(n-1, p_i-1)), where p_1, p_2, ..., p_m are all distinct primes dividing n. - Max Alekseyev, Dec 06 2010

a(p^k) = p for prime p with k > 0. - Thomas Ordowski, Sep 05 2018

Maple

f:= n -> mul(1+igcd(n-1, p[1]-1), p = ifactors(n)[2]):
map(f, [$1..200]); # Robert Israel, Sep 05 2018

Mathematica

Table[Times @@ Map[(1 + GCD[n - 1, # - 1]) &, FactorInteger[n][[All, 1]] ], {n, 113}] (* Michael De Vlieger, Sep 01 2020 *)

Prog

(PARI) A182816(n)=sum(a=1, n, Mod(a, n)^n==a);
(PARI) { A182816(n) = my(p=factor(n)[, 1]); prod(j=1, #p, 1+gcd(n-1, p[j]-1)); } \\ Max Alekseyev, Dec 06 2010

Crossrefs

Cf. A063994.

Sequence in context: A127433 A055573 A238729 * A367580 A195637 A181861

Adjacent sequences: A182813 A182814 A182815 * A182817 A182818 A182819

Keyword

nonn

Author

M. F. Hasler, Dec 05 2010

Status

approved