login
Number of distinct prime residues of k^n (mod n), k=0..n-1.
4

%I #12 Sep 24 2022 16:19:48

%S 0,0,1,0,2,1,3,0,0,1,4,0,5,3,6,0,6,0,7,1,2,3,8,0,1,4,0,0,9,1,10,0,11,

%T 4,11,0,11,6,3,0,12,1,13,2,3,7,14,0,2,0,15,2,15,0,3,0,5,6,16,0,17,8,0,

%U 0,18,3,18,2,19,2,19,0,20,10,2,4,21,1,21,0,0

%N Number of distinct prime residues of k^n (mod n), k=0..n-1.

%C If n is a prime number, a(n) = A000720(n) - 1 because the number of distinct residues of k^n (mod n) = n.

%H Harvey P. Dale, <a href="/A202034/b202034.txt">Table of n, a(n) for n = 1..1000</a>

%e a(7) = 3 because k^7 == 0, 1, 2, 3, 4, 5, 6 (mod 7) including 3 prime residues 2, 3, 5.

%p for n from 1 to 100 do: W:={}:for k from 0 to n-1 do:z:= irem(k^n,n): if type(z,prime)=true then W:=W union {z}:else fi:od: x:=nops(W): printf(`%d, `,x): od:

%t Table[Length[Select[Union[Table[Mod[k^n, n], {k, 0, n - 1}]], PrimeQ]], {n, 81}] (* _Alonso del Arte_, Dec 10 2011 *)

%t Count[Union[#],_?PrimeQ]&/@Table[PowerMod[k,n,n],{n,100},{k,0,n-1}] (* _Harvey P. Dale_, Sep 24 2022 *)

%Y Cf. A000720, A132213, A195637.

%K nonn

%O 1,5

%A _Michel Lagneau_, Dec 09 2011