Otra definición equivalente de raíz primitiva mod $n$ es (de Wikipedia),
un número $g$ es una raíz primitiva módulo $n$ si todo número coprimo a $n$ es congruente con una potencia de $g$ modulo $n$
Por ejemplo, $3$ es una raíz primitiva módulo $7$ pero no modulo $11$ porque
Módulo $7$ , $$3^0\equiv1,\; 3^1\equiv3,\; 3^2\equiv2,\; 3^3\equiv6,\; 3^4\equiv4,\; 3^5\equiv5,\; 3^6\equiv1\pmod{7}$$
Y tienes todos los resultados posibles: $1, 3, 2, 6, 4, 5$ . No se puede conseguir un $0$ pero $0$ no es coprima de $7$ así que no es un problema. Por lo tanto, $3$ es una raíz primitiva módulo $7$ .
Mientras que el módulo $11$ , $$3^0\equiv1,\; 3^1\equiv3,\; 3^2\equiv9,\; 3^3\equiv5,\; 3^4\equiv4,\; 3^5\equiv1\pmod{11}$$
Y modulo $11$ , sólo tienes los valores posibles $1, 3, 9, 5, 4$ y la secuencia comienza a repetirse después de $3^5$ , so nunca conseguirás un $3^k\equiv2$ por ejemplo. Por lo tanto, $3$ es no una raíz primitiva módulo $11$ .
La secuencia $g^k$ siempre se repite el módulo $n$ después de algún valor de $k$ ya que sólo puede asumir un número finito de valores (por lo que al menos un valor aparece al menos dos veces, por ejemplo $r,s$ y $r>s$ tienes $g^r \equiv g^{s}$ ), y un término depende sólo del anterior: $g^{k+1}\equiv g\cdot g^k$ . Así, $g^{r+k}\equiv g^{s+k}$ para todos $k$ .
Si $g$ y $n$ son coprimos, se simplifica un poco, porque $g^k\equiv g^{k'} \pmod{n}$ para algunos $k, k'$ con $k>k'$ implica $g^{k-k'}\equiv 1$ (se puede tomar la inversa modular porque entonces todo $g^k$ son coprimos a $n$ ), entonces con $r=k-k'$ , usted tiene $g^{k+r}\equiv g^kg^r\equiv g^k$ para todos $k$ .
Si $g$ y $n$ no son coprimos, no es tan sencillo: si $g^r \equiv 0 \pmod{n}$ para algunos $r$ entonces $g^{k+r}\equiv g^kg^r\equiv 0$ para todos $k$ . Pero también puede tener una secuencia repetida sin $1$ , por ejemplo, modulo $15$ ,
$$3^0\equiv1,\; 3^1\equiv3,\; 3^2\equiv9,\; 3^3\equiv12,\; 3^4\equiv6,\; 3^5\equiv3\pmod{15}$$
Y empieza a repetirse después de $3^4$ con números no coprimos a $15$ desde $g=3$ no es coprima de $n$ o bien. Y en realidad, si $g$ y $n$ no son coprimos, nunca se obtiene un $1$ de nuevo después de $g^0\equiv1 \pmod{n}$ porque todos los $g^k$ tienen un factor común con $n$ .
Alternativamente, el orden multiplicativo de $g$ modulo $n$ es el menor exponente $k$ tal que $g^k\equiv 1\pmod{n}$ .
Aquí se ve que el orden multiplicativo de $3$ modulo $7$ es $6$ y el orden multiplicativo de $3$ modulo $11$ es $5$ así que según su definición.., $3$ es efectivamente una raíz primitiva módulo $7$ pero no modulo $11$ .
Obsérvese también que el orden multiplicativo de $g$ módulo de un primo $p$ es siempre menor o igual que $p-1$ ya que El pequeño teorema de Fermat establece que para un primo $p$ y $a$ no divisible por $p$ , $a^{p-1}\equiv 1 \pmod{p}$ . Entonces el orden multiplicativo es también siempre un divisor de $p-1$ y conduce a un algoritmo sencillo para buscar raíces primitivas:
Para probar una posible $g$ , tome la factorización entera de $p-1$ y para cada factor primo $d$ de $p-1$ , computa $g^{(p-1)/d}$ modulo $p$ . Si ninguno de ellos es $1$ entonces $g$ es una raíz primitiva módulo $p$ ya que $k=p-1$ es entonces el más pequeño $k$ tal que $g^k\equiv 1\pmod{p}$ .
Para los grandes $p$ y el uso de la tecnología modular exponenciación al cuadrado es mucho más rápido que computar todo $g^k$ modulo $p$ para $k=0,1,\ldots,p-1$ y comprobar si todos los valores posibles están ahí (pero todavía se necesita una factorización de enteros).
