Finding Primitive Roots

Number Theory · Axiom Academy

EXAMPLE Finding Primitive Roots Step-by-step worked example of finding a primitive root modulo a prime Excellent work! You've completed this example on finding primitive roots. Here's what we learned: Definition: An integer g is a primitive root modulo p if its order equals φ(p) = p - 1 Testing Strategy: To verify g is a primitive root, check that g^((p-1)/q) ≢ 1 (mod p) for each prime divisor q of p - 1 Prime Factorization: Finding the prime factorization of p - 1 is essential for efficient testing Systematic Search: Test small integers systematically (2, 3, 5, ...) until you find a primitive root Guaranteed Existence: Every prime has at least one primitive root (in fact, it has φ(p-1) primitive roots) This systematic approach works for any prime. Practice with different primes to build confidence!

This is the written version of the interactive lesson above. See the full Number Theory course.