%I #6 Mar 30 2012 18:35:59
%S 1,2,2,3,2,6,2,5,4,10,2,9,2,14,6,9,2,14,2,15,8,22,2,15,6,26,10,9,2,30,
%T 2,17,12,34,12,21,2,38,14,25,2,42,2,33,8,46,2,27,8,42,18,15,2,38,18,
%U 35,20,58,2,45,2,62,16,33,8,18,2,51,24,30,2,35,2,74
%N Number of distinct residues of x^(n-1) (mod n), x=0..n-1.
%C a(n) = 2 if n prime because the residues are 0 and 1 (Fermat's little theorem).
%C a(n) = n if n = 2p, p prime > 2. But there exists nonprime numbers q such that a(2q) = 2q, for example q = 1, 15, 21, 39,...
%e a(8) = 5 because x^7 == 0, 1, 3, 5, 7 (mod 8) => 5 distinct residues.
%t Length[Union[#]]& /@ Table[Mod[k^(n-1), n], {n, 74}, {k, n}]
%Y Cf. A000224, A195637.
%K nonn
%O 1,2
%A _Michel Lagneau_, Oct 19 2011
|