Primitive-root modulus classification
ID: primitive-root-modulus-classification
With the one-element unit group convention at , a positive integer modulus admits a primitive root exactly whenwhere is an odd prime and .
For existence, the finite subgroup of a field multiplicative group is cyclic theorem supplies a primitive root modulo . At least one of and satisfies the primitive-root lifting criterion: if , thenThus lifting a primitive root to odd prime powers gives every . The Chinese remainder theorem for unit groups identifies with because is trivial. The moduli two and four are checked directly.
For exclusion, a cyclic group has at most two solutions of . If a modulus has two distinct odd prime factors, or is divisible by both four and an odd prime number, independent sign choices under the Chinese remainder theorem give at least four such units. A pure power with also has the four distinct roots and . These cover every omitted case.
When a primitive root exists, their number is . If generates the unit group of size , its power has multiplicative order , so exactly the coprime exponent classes generate. Here is Euler's totient function.
New to topics? Read the docs here!