Primitive Roots

Number Theory · Axiom Academy

Generators of the Multiplicative Group and their Properties 1. Definition of Primitive Roots An integer g is a primitive root modulo n if: gcd( g , n ) = 1 (so g is a unit mod n ) That is, g has maximal order in the group (Z/ n Z)*. Example: Let's explore primitive roots modulo 7. Since 7 is prime, φ(7) = 6, so we need an element of order 6 that generates all units 1, 2, 3, 4, 5, 6 . Theorem (Existence of Primitive Roots) Primitive roots exist modulo n if and only if: n = 2p^k (twice an odd prime power) This means primitive roots exist for moduli like 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, ... but not for 8, 12, 15, 16, ... Why not modulo 8? Let's examine the structure: 3. Primitive Roots Modulo Primes When p is prime, the multiplicative group (Z/ p Z)* is cyclic of order φ( p ) = p - 1. Any generator of this cyclic group is a primitive root. Example: Finding all primitive roots modulo 11. Since φ(11) = 10, we need elements of order 10. Let's test g = 2: Theorem (Number of Primitive Roots) If primitive roots exist modulo n , then there are exactly φ(φ( n )) primitive roots modulo n . This follows from the fact that if g is a primitive root mod n , then g^k is also a primitive root if and only if gcd( k , φ( n )) = 1. Example: How many primitive roots exist modulo 7? φ(7) = 6, so there are φ(6) = φ(2·3) = φ(2)·φ(3) = 1·2 = 2 primitive roots.

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