You compute powers of 4 modulo 15 and find 4¹ ≡ 4, 4² ≡ 1 (mod 15), so the order of 4 mod 15 is 2. Note that φ(15) = 8. Which statement about 2 must be true by the theory?
A2 must divide 15
B2 must divide φ(15) = 8
C2 must equal φ(15) = 8, since every element has order equal to φ(n)
D2 must be the smallest prime factor of 15
The order of any element a modulo n always divides φ(n), by Lagrange's theorem: the powers of a form a cyclic subgroup of the multiplicative group (Z/nZ)*, and every subgroup's size divides the group's order. Here ord(4) = 2 and φ(15) = 8, and indeed 2 divides 8. Option C states the common misconception — that every element has order exactly φ(n). This is only true for primitive roots, which are special. Elements can have smaller orders that divide φ(n). Fermat's Little Theorem guarantees a^φ(n) ≡ 1, but φ(n) is an upper bound on the order's possible values, not the order itself.
Question 2 Multiple Choice
Which of the following is TRUE about primitive roots modulo n?
AEvery positive integer n has at least one primitive root
BAn element a is a primitive root mod n if and only if its order equals φ(n) — meaning its successive powers cycle through every unit modulo n before returning to 1
CA primitive root modulo n must itself be a prime number
DPrimitive roots exist only when n is prime
A primitive root is precisely an element whose order equals φ(n), the size of the full multiplicative group. Such an element generates the entire group — its powers {a, a², ..., a^φ(n) ≡ 1} produce every unit modulo n. For example, 3 mod 7 is a primitive root because its six powers give all nonzero residues mod 7. Option A is false: not every n has primitive roots — they exist for n = 1, 2, 4, p^k, and 2p^k (for odd prime p), but not, for example, mod 8 or mod 15. Option C is false: 3 is prime but 2 mod 7 is not a primitive root (order 3), so primeness is irrelevant.
Question 3 True / False
If a^k ≡ 1 (mod n) for some positive integer k, then the order of a modulo n must divide k.
TTrue
FFalse
Answer: True
This is a key divisibility property of the order. If d = ord_n(a), then a^k ≡ 1 (mod n) if and only if d divides k. The 'only if' direction: write k = qd + r with 0 ≤ r < d. Then a^k = (a^d)^q · a^r ≡ 1^q · a^r = a^r ≡ 1 (mod n), so a^r ≡ 1. Since r < d and d is the smallest positive exponent with a^d ≡ 1, we must have r = 0, meaning d | k. This fact has immediate practical use: knowing some exponent k that gives 1 immediately tells you the order divides k, restricting your search to divisors of k.
Question 4 True / False
By Fermat's Little Theorem, the order of any element a modulo a prime p is exactly p − 1.
TTrue
FFalse
Answer: False
Fermat's Little Theorem says a^(p−1) ≡ 1 (mod p) for gcd(a, p) = 1. This means the order of a *divides* p − 1, not that it *equals* p − 1. For example, mod 7: the order of 2 is 3 (since 2³ = 8 ≡ 1 mod 7), and the order of 6 is 2 (since 6² = 36 ≡ 1 mod 7), while p − 1 = 6. Only elements with order exactly p − 1 are primitive roots, and not every element is a primitive root. Confusing 'divides p−1' with 'equals p−1' is the most common error when first encountering order theory.
Question 5 Short Answer
When searching for the order of a modulo n, why is it sufficient to check only the divisors of φ(n) rather than all integers from 1 to φ(n)?
Think about your answer, then reveal below.
Model answer: The order of a modulo n always divides φ(n), by Lagrange's theorem: the powers of a form a cyclic subgroup of (Z/nZ)*, and subgroup sizes divide the group order φ(n). Since the order must be a divisor of φ(n), there is no need to check integers that don't divide φ(n) — they cannot be the order. For example, if φ(n) = 12, the possible orders are 1, 2, 3, 4, 6, or 12, so we check only these six values rather than all twelve. The strategy is to test the divisors of φ(n) in increasing order; the smallest k with a^k ≡ 1 (mod n) is the order.