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) = 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
KEYWORD
nonn
AUTHOR
M. F. Hasler, Dec 05 2010
STATUS
approved