cp's OEIS Frontend

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

%I A182816 #56 Sep 03 2020 01:58:56
%S A182816 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,
%T A182816 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,
%U A182816 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
%N A182816 Number of values b in Z/nZ such that b^n = b.
%C A182816 a(n) is the number of nonnegative bases b < n such that b^n == b (mod n).
%H A182816 Robert Israel, <a href="/A182816/b182816.txt">Table of n, a(n) for n = 1..10000</a>
%F A182816 a(n) = n for primes A000040 and Carmichael numbers A002997.
%F A182816 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
%F A182816 a(p^k) = p for prime p with k > 0. - _Thomas Ordowski_, Sep 05 2018
%p A182816 f:= n -> mul(1+igcd(n-1,p[1]-1), p = ifactors(n)[2]):
%p A182816 map(f, [$1..200]); # _Robert Israel_, Sep 05 2018
%t A182816 Table[Times @@ Map[(1 + GCD[n - 1, # - 1]) &, FactorInteger[n][[All, 1]] ], {n, 113}] (* _Michael De Vlieger_, Sep 01 2020 *)
%o A182816 (PARI) A182816(n)=sum(a=1,n,Mod(a,n)^n==a);
%o A182816 (PARI) { A182816(n) = my(p=factor(n)[,1]); prod(j=1,#p,1+gcd(n-1,p[j]-1)); } \\ _Max Alekseyev_, Dec 06 2010
%Y A182816 Cf. A063994.
%K A182816 nonn
%O A182816 1,2
%A A182816 _M. F. Hasler_, Dec 05 2010