gen-define-primitive-roots-and-give-one-short-worked-example-c2a0

Define primitive roots and give one short worked example.

# Primitive Roots ## Definition A **primitive root** modulo *n* is an integer *g* such that its powers generate all integers coprime to *n*. Formally, *g* is a primitive root mod *n* if: - gcd(*g*, *n*) = 1, and - The order of *g* mod *n* equals φ(*n*) (Euler's totient function) Equivalently, the set {*g*¹, *g*², *g*³, ..., *g*^φ(*n*)} mod *n* produces all φ(*n*) integers coprime to *n*. ## Worked Example **Question:** Is *g* = 2 a primitive root mod 5? **Solution:** First, φ(5) = 4 (since 5 is prime). For 2 to be a primitive root mod 5, we need the order of 2 to equal 4. Calculate powers of 2 mod 5: - 2¹ ≡ 2 (mod 5) - 2² ≡ 4 (mod 5) - 2³ ≡ 8 ≡ 3 (mod 5) - 2⁴ ≡ 6 ≡ 1 (mod 5) Since 2⁴ ≡ 1 (mod 5) and no smaller positive power gives 1, the order of 2 is 4. Also note: {2, 4, 3, 1} = {1, 2, 3, 4}, which is exactly the set of all integers coprime to 5. **Answer:** Yes, 2 is a primitive root mod 5. ✓