- Let q a positive integer and 1<=r<=q. Is there a theorem that tells
us how many integers a, 1<=a<=q, verify a^r=1 mod(q)?
I have found that:
(1) if q is prime or a power of a prime p, i.e. q=p^x, then there
are GCD(r,EulerPhi(q)) integers a that satisfy a^r=1 mod(q).
(2) if q is a product of two powers of primes p' and p'', i.e.
q=p'^x p''^y, then there are GCD(r,Carmichael(q))*GCD(r,Phi
(q)/Carmichael(q)) integers a that satisfy a^r=1 mod(q).
Are these results correct and can we generalize to any integer q?
Thanks for your help