¿Qué son las raíces primitivas módulo n?

Question

Estoy tratando de entender lo que son las raíces primitivas para un determinado $\bmod\ n$ . La definición de Wolfram es lo siguiente:

Una raíz primitiva de un primo $p$ es un número entero $g$ de tal manera que $g\ ( \bmod\ p)$ tiene orden multiplicador $p-1$

Lo principal que me confunde es qué es el "orden multiplicativo". Además, para la notación $g\ ( \bmod\ p)$ ¿dice que $g$ veces $\bmod\ p$ o tiene algo que ver con su congruencia?

Perdón por la pregunta básica, ¡cualquier aclaración sería genial!

Answer 1

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).

Answer 2

Te preguntas por el anillo (con estructura aditiva y estructura multiplicativa) $\mathbb Z$ modulo $n$ , a menudo denotado como $\mathbb Z/(n)$ . Puedes sumar y puedes multiplicar módulo $n$ Las operaciones tienen mucho sentido.

Para un general (no necesariamente primo) $n$ la estructura multiplicativa puede ser bastante poco cuidadosa. Por ejemplo, cuando $n=8$ , usted tiene $4\cdot2=0$ , producto de dos cosas no nulas que resulta ser cero. Hay cantidades módulo $n$ ("residuos mod $n$ ") que tienen recíprocos, sin embargo: para el caso $n=15$ tenemos $2\cdot8=1$ , modulo $15$ . Los residuos que tienen recíprocos se pueden denotar $(\mathbb Z/(n))^*$ o algo así, y este sistema es una estructura multiplicativa por sí misma, un "grupo multiplicativo". En ciertas circunstancias Este grupo multiplicativo es "cíclico", es decir, hay un elemento particular cuyas potencias pasan por todas las cosas en $(\mathbb Z/(n))^*$ . Por ejemplo, se puede comprobar que los elementos de $(\mathbb Z/(9))^*$ son $\{1,2,4,5,7,8\}$ y también se puede comprobar que cada una de ellas es una potencia de dos, módulo nueve. Cuando hay un residuo tan bonito como $2$ está aquí, se llama raíz primitiva y es un Teorema serio que cuando $n$ es un primo, siempre hay una raíz primitiva. Por ejemplo, $n=5$ tiene $2$ para un p.r, $n=7$ no puede usar $2$ pero $3$ es un buen p.r. Hay algunas pautas útiles para encontrar una raíz primitiva, pero no quiero ir allí esta noche. El hecho importante es que los únicos números $n$ que tienen raíces primitivas módulo $n$ son de la forma $2^\varepsilon p^m$ , donde $\varepsilon$ es $0$ o $1$ , $p$ es un primo impar, y $m\ge0$