Cuando p es un primo, una raíz primitiva mod p es un número cuyas potencias producen todos los números mod p con excepción del 0 (1, 2, 3, ... p-1).

Considere las potencias de 3 mod 7:

3¹ ≡ 3
3² ≡ 2
3³ ≡ 6
3⁴ ≡ 4
3⁵ ≡ 5
3⁶ ≡ 1

Obsérvese que se obtienen todos los números mod 7 con excepción del 0 como potencias de 3 (1, 2, 3, 4, 5, 6). Esto significa que 3 es una raíz primitiva mod 7.

Ahora consideramos las potencias de 2 mod 7:

2¹ ≡ 2
2² ≡ 4
2³ ≡ 1
2⁴ ≡ 2
2⁵ ≡ 4
2⁶ ≡ 1

Obsérvese que no se obtienen todos los números mod 7 con excepción del 0 como potencias de 2 (1, 2, 3, 4, 5, 6). Esto significa que 2 NO es una raíz primitiva mod 7.

---

Referencias

1. Trappe, W., Washington, L. (2006). Discrete Logarithms. En Introduction to Cryptography with Coding Theory(210-212). United States of America: Prentice Hall.