Questions: Primitive Roots and Cyclic Groups Mod p

Question 1

Which of the following best describes why 3 is a primitive root mod 7?

• A. 3 is prime and less than 7
• B. 3 satisfies 3^6 ≡ 1 (mod 7) by Fermat's Little Theorem
• C. The powers 3¹, 3², 3³, 3⁴, 3⁵, 3⁶ (mod 7) produce all six nonzero residues {1, 2, 3, 4, 5, 6}
• D. gcd(3, 7) = 1, so 3 is invertible mod 7

Answer: (C)

Being a primitive root means having order p−1 — the maximum possible. Option B (Fermat's Little Theorem) is true of EVERY nonzero element mod a prime, not just primitive roots: 1^6 ≡ 1 (mod 7) as well, but 1 has order 1 not 6. Option D (invertibility) is also true of all nonzero residues mod a prime. The defining property of a primitive root is that its cyclic subgroup includes all p−1 nonzero residues — it is a generator of the full multiplicative group (Z/7Z)*.

Question 2

For the prime p = 11, how many primitive roots exist mod 11?

• A. 1, since primitive roots are unique
• B. 4, since φ(10) = φ(2·5) = 1·4 = 4
• C. 10, since every nonzero element is a primitive root mod a prime
• D. 5, since there are 5 odd residues less than 11

Answer: (B)

The number of primitive roots mod p is φ(p−1). Here p−1 = 10 = 2·5, so φ(10) = φ(2)·φ(5) = 1·4 = 4. Once you find one primitive root g, all others are g^k for gcd(k, p−1) = 1. Option C is wrong because most elements mod a prime are NOT primitive roots: 1 always has order 1, −1 (= 10 mod 11) has order 2, etc. Only elements with the maximum possible order p−1 qualify.

Question 3

Nearly every integer modulus n ≥ 2 has at least one primitive root.

• T. True
• F. False

Answer: False

Primitive roots exist for primes p, prime powers p^k, twice prime powers 2p^k, and for n = 1, 2, 4 — but not for all moduli. For example, no primitive root exists mod 8: the nonzero odd residues mod 8 are {1, 3, 5, 7}, and every element satisfies a² ≡ 1 (mod 8). The maximum order is 2, but φ(8) = 4, so no element generates (Z/8Z)*. The multiplicative group mod composite numbers can be isomorphic to a direct product of cyclic groups, which is not itself cyclic — and a non-cyclic group has no single generator.

Question 4

If g is a primitive root mod p, then g^k is also a primitive root mod p if and only if gcd(k, p−1) = 1.

• T. True
• F. False

Answer: True

The order of g^k is (p−1)/gcd(k, p−1). For g^k to be a primitive root (order p−1), we need gcd(k, p−1) = 1. This gives exactly φ(p−1) values of k in {1, ..., p−1} for which g^k is a primitive root, confirming that (Z/pZ)* has exactly φ(p−1) generators.

Question 5

Explain why the existence of a primitive root mod p implies that the multiplicative group (Z/pZ)* is cyclic. What does 'cyclic' mean in this context?

Model answer: A group is cyclic if it is generated by a single element — every element of the group is a power of that generator. If g is a primitive root mod p, then the p−1 powers g¹, g², ..., g^(p−1) are all distinct (since g has order p−1, no two powers in this range are congruent mod p) and exhaust all p−1 nonzero residues. Therefore every element of (Z/pZ)* is a power of g, making g a generator and (Z/pZ)* a cyclic group of order p−1.

The cyclic structure is what makes discrete logarithms well-defined: in a cyclic group, every element has a unique discrete logarithm relative to a generator, establishing a bijection between group elements and exponents mod p−1. This is precisely the algebraic foundation that Diffie-Hellman key exchange and ElGamal encryption exploit.