Questions: Primitive Roots and Cyclic Groups Modulo a Prime

Question 1

In the group (ℤ/7ℤ)*, the element 2 satisfies 2³ ≡ 1 (mod 7). Why is 2 NOT a primitive root modulo 7?

• A. Because 2 is an even number and primitive roots must be odd
• B. Because 2's multiplicative order is 3, which is less than p−1 = 6, so it generates only a proper subgroup
• C. Because Fermat's Little Theorem requires all elements to have order exactly p−1
• D. Because 2 cannot generate residues greater than 4 modulo 7

Answer: (B)

A primitive root must have multiplicative order exactly p−1 — it must cycle through ALL nonzero residues before returning to 1. Since 2³ ≡ 1 (mod 7), the element 2 returns to 1 after only 3 steps, generating the subgroup {1, 2, 4}. Fermat's Little Theorem (option C) only guarantees that g^(p−1) ≡ 1 — it says the order *divides* p−1, not that it *equals* p−1. Most elements have smaller orders and generate only proper subgroups.

Question 2

The security of Diffie-Hellman key exchange relies on a primitive root g modulo a large prime p. An attacker knows g, p, and the public value g^x mod p, but needs to find x. Why does the existence of a primitive root make this problem hard while making g^x easy to compute?

• A. Computing g^x is hard because x could be any of p−1 possible values, making brute force necessary
• B. Computing g^x mod p is fast via repeated squaring; recovering x from g^x mod p (the discrete log) is believed computationally hard because no efficient algorithm is known for large primes
• C. The primitive root property means g^x cycles through all residues, so g^x can equal any nonzero value, making the output unpredictable
• D. Computing g^x is easy because g is always small; the hardness comes from the modular reduction step

Answer: (B)

The asymmetry is algorithmic: modular exponentiation can be done in O(log x) multiplications via repeated squaring, but reversing it — given g^x mod p, finding x — is the discrete logarithm problem, believed to require exponential time for large primes. Option A confuses hardness with the number of possible values; the key insight is the computational gap between forward and inverse operations that primitive roots make possible.

Question 3

Fermat's Little Theorem guarantees that g^(p−1) ≡ 1 (mod p) for most nonzero g. This means nearly every nonzero element of (ℤ/pℤ)* is a primitive root modulo p.

• T. True
• F. False

Answer: False

Fermat's Little Theorem says the multiplicative order of g *divides* p−1 — it guarantees g^(p−1) ≡ 1, but not that p−1 is the *smallest* such exponent. An element with order d | (p−1) where d < p−1 satisfies the theorem but generates only a subgroup of size d, not the full group. Primitive roots are the special elements whose order is exactly p−1. Their count is φ(p−1), which for large p is much smaller than p−1.

Question 4

The number of primitive roots modulo a prime p equals p−2.

• T. True
• F. False

Answer: False

The number of primitive roots modulo p is φ(p−1) — Euler's totient of p−1, counting how many integers less than p−1 are coprime to it. This is generally much less than p−2. For example, modulo 7 (p−1 = 6), φ(6) = 2, so there are exactly 2 primitive roots (3 and 5), not 5. The formula φ(p−1) follows from the fact that in a cyclic group of order n, the number of generators is φ(n).

Question 5

What is the multiplicative order of an element g in (ℤ/pℤ)*, and why must g be a primitive root for the discrete logarithm problem to be well-defined for every nonzero target h?

Model answer: The multiplicative order of g is the smallest positive integer k such that g^k ≡ 1 (mod p). If g is a primitive root, its order is p−1, meaning g^1, g^2, …, g^(p−1) produce every nonzero residue exactly once. This means every nonzero h can be written as g^x for some unique x ∈ {1, …, p−1} — the discrete log exists and is unique. If g has smaller order d < p−1, then g only generates a subgroup of size d, and there are nonzero elements h outside that subgroup with no discrete log base g at all.

The requirement that the base be a primitive root is what guarantees every element of the group has a discrete logarithm — i.e., that the map x ↦ g^x is a bijection from {1,…,p−1} to (ℤ/pℤ)*. Without this, the discrete log is undefined for elements outside the subgroup generated by g, and the cryptographic application breaks down.