Notes - Primitive Roots

The following are notes from Introduction to Cryptography with Coding Theory.

• Consider the powers of 3 (mod 7)
• 3¹≡ 3, 3²≡ 2, 3³≡ 6, 3⁴≡ 4, 3⁵≡ 5, 3⁶≡ 1
• Note that we obtain all nonzero congruence classes mod 7 as powers of 3
• Generally when p is a prime, a primitive root mod p is a number whose powers yield every nonzero class mod p
• Primitive Roots
• Let g be a primitive root for the prime p
• Let n be an integer. Then gⁿ≡ 1 (mod p) if and only if n ≡ 0 (mod p - 1)
• If j and k are integers, then g^j ≡ g^j (mod p) if and only if j ≡ k (mod p - 1)

Back to ToC