Are there always even number of primitive roots?
Because
1. For every primitive root there is a multiplicative inverse that is also a primitive root
2. A primitive root and its inverse are never equivalent
... so we can pair them up.
Does the modulo need to be prime?
(1) phi(n) is always even for n>=3. ( https://mathworld.wolfram.com/TotientFunction.html )
(2) If n has a primitive root, then it has exactly phi(phi(n)) of them ( https://oeis.org/A010554 )
(3) n has a primitive root if it is of the form 2, 4, p^a, or 2p^a, where p is an odd prime and a>=1 ( https://mathworld.wolfram.com/PrimitiveRoot.html )
From https://oeis.org/A046144, the only numbers with an odd number of primitive roots are 2, 3, 4 and 6.
The totient function phi(n), also called Euler's totient function, is defined as the number of positive integers <=n that are relatively prime to (i.e., do not contain any factor in common with) n, where 1 is counted as being relatively prime to all numbers. Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function phi(n) can be simply defined as the number of totatives of n. For example, there are eight totatives of 24 (1, 5,...
Tariq
恐龍化石 Dino Fossil