어떤 정수 a가 주어졌을 때, a^n의 형태가 (mod p)의 모든 나머지를 가지고 있다면, 이것을 Primitive Root라고 한다. a = 3, p = 7의 예를 들어보자.
3 ≡ 3 (mod 7)
9 ≡ 2 (mod 7)
27 ≡ 6 (mod 7)
81 ≡ 4 (mod 7)
243 ≡ 5 (mod 7)
729 ≡ 1 (mod 7)
여기서, 1, 2, 3, 4, 5, 6의 나머지를 얻었는데, 이것은 7의 모든 나머지를 가진 것이다. 이와 같은 경우, 3은 mod 7의 Primitive Root이다. 또, Prime Number p는 Φ(p - 1)의 Primitive Root를 가진다. 예를 들어, 2, 6, 7, 8은 mod 11의 Primitive Root이다.
3 ≡ 3 (mod 7)
9 ≡ 2 (mod 7)
27 ≡ 6 (mod 7)
81 ≡ 4 (mod 7)
243 ≡ 5 (mod 7)
729 ≡ 1 (mod 7)
여기서, 1, 2, 3, 4, 5, 6의 나머지를 얻었는데, 이것은 7의 모든 나머지를 가진 것이다. 이와 같은 경우, 3은 mod 7의 Primitive Root이다. 또, Prime Number p는 Φ(p - 1)의 Primitive Root를 가진다. 예를 들어, 2, 6, 7, 8은 mod 11의 Primitive Root이다.