Raíz primitiva módulo n

En aritmética modular, un número g es un módulo raíz primitivo n si cada número a coprimos a n es congruente con una potencia de g módulo n. Es decir, g es un módulo raíz primitivo n si para cada entero a coprimos a n, hay algún número entero k para el cual g^k ≡ a (mod n ). Tal valor k se denomina índice o logaritmo discreto de a a la base g módulo n. Entonces g es un módulo raíz primitivo n si y solo si g es un generador del grupo multiplicativo de enteros módulo n.

Gauss definió las raíces primitivas en el artículo 57 de las Disquisitiones Arithmeticae (1801), donde atribuye a Euler la acuñación del término. En el Artículo 56 afirmó que Lambert y Euler los conocían, pero fue el primero en demostrar rigurosamente que existen raíces primitivas para un primo n. De hecho, las Disquisitiones contienen dos pruebas: la del artículo 54 es una prueba de existencia no constructiva, mientras que la prueba del artículo 55 es constructiva.

Ejemplo elemental

El número 3 es una raíz primitiva módulo 7 porque

31=30× × 3↑ ↑ 1× × 3=3↑ ↑ 3()mod7)32=31× × 3↑ ↑ 3× × 3=9↑ ↑ 2()mod7)33=32× × 3↑ ↑ 2× × 3=6↑ ↑ 6()mod7)34=33× × 3↑ ↑ 6× × 3=18↑ ↑ 4()mod7)35=34× × 3↑ ↑ 4× × 3=12↑ ↑ 5()mod7)36=35× × 3↑ ↑ 5× × 3=15↑ ↑ 1()mod7)37=36× × 3↑ ↑ 1× × 3=3↑ ↑ 3()mod7){displaystyle {begin{array}{rcrcrcrcrcr}3^{1} {0}times 3 equiv &1times 3 = 3, 3, 3, 3, 3, 3, 3, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, {7}3^{2} {3^{1}times 3 limitequiv &3times 3⁄3}3^{3^{2}fnMicrosoft Sans 3 = 3 = 6 personas {7}3^{4} {3}times 3 limitequiv > 3 = 3 = 3,18 {7}3^{5} {4}times 3 ventajaequiv &4times 3 = 3 = 12 personas {7}3^{6} {5}times 3 limitequiv >5times 3 = 3 = = 15 = equiv &1 {7}3^{7} {6}times 3 limitequiv > 1times 3 limit= 3 limit= 3 limit= 3 limitequiv &3{pmod {7}\\end{array}}}

Aquí vemos que el período de 3^k módulo 7 es 6. Los restos en el período, que son 3, 2, 6, 4, 5, 1, forman un reordenamiento de todos los residuos distintos de cero módulo 7, lo que implica que 3 es de hecho una raíz primitiva módulo 7. Esto se deriva del hecho de que una secuencia (g^k módulo n) siempre se repite después de algún valor de k, ya que módulo n produce un número finito de valores. Si g es un módulo raíz primitivo n y n es primo, entonces el período de repetición es n − 1. Se ha demostrado que las permutaciones creadas de esta forma (y sus desplazamientos circulares) son matrices de Costas.

Definición

Si n es un entero positivo, los enteros de 0 a 0 n − 1 que son coprime n (o equivalentemente, las clases de congruencia coprime a n) formar un grupo, con modulo de multiplicación n como la operación; es denotado por Z{displaystyle mathbb {Z}^×
_n, y se llama el grupo de unidades modulo n, o el grupo de clases primitivas modulo n. Como se explica en el grupo multiplicativo del artículo de enteros modulo n, este grupo multiplicativo (Z{displaystyle mathbb {Z}^×
_n) es cíclico si n es igual a 2, 4, p^k, o 2p^k Donde p^k es un poder de un número primo impar. Cuando (y sólo cuándo) este grupo Z{displaystyle mathbb {Z}^×
_n es cíclico, un generador de este grupo cíclico se llama un primitivo modulo n (o en lenguaje más completo raíz primitiva de la unidad modulo n, destacando su papel como una solución fundamental raíces de la unidad ecuaciones polinómicas X^m
− 1 en el anillo Z{displaystyle mathbb {Z}_n), o simplemente un elemento primitivo Z{displaystyle mathbb {Z}^×
_n.

Cuando Z{displaystyle mathbb {Z}^×
_n es no cíclico, tales elementos primitivos mod n no existen. En su lugar, cada componente principal de n tiene sus propias raíces subprimitivas (ver 15 en los ejemplos siguientes).

Para cualquier n o no Z{displaystyle mathbb {Z}^×
_n es cíclica), el orden de Z{displaystyle mathbb {Z}^×
_n es dada por la función totiente de Euler φ()n(sequence) A000010 en el OEIS). Y entonces, el teorema de Euler dice que a^φ()n) (modelo) n) para todos a coprime n; el poder más bajo de a que es congruente con 1 modulo n se llama el orden multiplicativo a modulo n. En particular, para a ser un modulo de raíz primitivo n, a^φ()n) tiene que ser el poder más pequeño a que es congruente con 1 modulo n.

Ejemplos

Por ejemplo, si n = 14 entonces los elementos de Z{displaystyle mathbb {Z}^×
_n son las clases de congruencia {1, 3, 5, 9, 11, 13}; hay φ(14) = 6 de ellos. Aquí hay una tabla de sus poderes modulo 14:

 x x, x2, x3,... (mod 14)
1: 1
3: 3, 9, 13, 11, 5, 1
5: 5, 11, 13, 9, 3, 1
9: 9, 11, 1
11: 11, 9, 1
13: 13, 1

El orden de 1 es 1, los órdenes de 3 y 5 son 6, los órdenes de 9 y 11 son 3, y el orden de 13 es 2. Así, 3 y 5 son las raíces primitivas módulo 14.

Por un segundo ejemplo n = 15. Los elementos de Z{displaystyle mathbb {Z}^×
₁₅ son las clases de congruencia {1, 2, 4, 7, 8, 11, 13, 14}; hay φ(15) = 8 de ellos.

 x x, x2, x3(mod 15)
1: 1
2: 2, 4, 8, 1
4: 4, 1
7: 7, 4, 13, 1
8: 8, 4, 2, 1
11: 11, 1
13: 13, 4, 7, 1
14: 14, 1

Como no hay ningún número cuyo orden sea 8, no hay raíces primitivas módulo 15. De hecho, λ(15) = 4, donde λ es la función de Carmichael. (secuencia A002322 en el OEIS)

Tabla de raíces primitivas

Números n{displaystyle n} que tienen una raíz primitiva son de la forma

<math alttext="{displaystyle nin {1,2,4,p^{k},2cdot p^{k};;|;;2

n▪ ▪ {}1,2,4,pk,2⋅ ⋅ pkSilencio2.pprimo;k▪ ▪ N},{displaystyle nin {1,2,4,p^{k},2cdot p^{k};;;;kin mathbb {N} },}<img alt="{displaystyle nin {1,2,4,p^{k},2cdot p^{k};;|;;2

= 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19,

Estos son los números n{displaystyle n} con φ φ ()n)=λ λ ()n),{displaystyle varphi (n)=lambda (n),} guardado también en la secuencia A033948 en el OEIS.

La siguiente tabla enumera el modulo de raíces primitivas n hasta n=31{displaystyle n=31}:

n{displaystyle n}	primitivas raíces modulo n{displaystyle n}	orden φ φ ()n),{displaystyle varphi (n),} ()OEIS: A000010)	exponente λ λ ()n),{displaystyle lambda (n),} ()OEIS: A002322)
1	0	1	1
2	1	1	1
3	2	2	2
4	3	2	2
5	2, 3	4	4
6	5	2	2
7	3, 5	6	6
8		4	2
9	2, 5	6	6
10	3, 7	4	4
11	2, 6, 7, 8	10	10
12		4	2
13	2, 6, 7, 11	12	12
14	3, 5	6	6
15		8	4
16		8	4
17	3, 5, 6, 7, 10, 11, 12, 14	16	16
18	5, 11	6	6
19	2, 3, 10, 13, 14, 15	18	18
20		8	4
21		12	6
22	7, 13, 17, 19	10	10
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22	22
24		8	2
25	2, 3, 8, 12, 13, 17, 22, 23	20	20
26	7, 11, 15, 19	12	12
27	2, 5, 11, 14, 20, 23	18	18
28		12	6
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28	28
30		8	4
31	3, 11, 12, 13, 17, 21, 22, 24	30	30

Propiedades

Gauss demostró que para cualquier número primo p (con la única excepción de p = 3), el producto de sus raíces primitivas es congruente con 1 módulo p.

También demostró que para cualquier número primo p, la suma de sus raíces primitivas es congruente con μ(p − 1) módulo p, donde μ es el Función de Möbius.

Por ejemplo,

p = 3,	μ2) = 1.	La raíz primitiva es 2.
p = 5,	μ(4) = 0.	Las raíces primitivas son 2 y 3.
p = 7,	μ(6) = 1.	Las raíces primitivas son 3 y 5.
p = 31,	μ(30) = 1.	Las raíces primitivas son 3, 11, 12, 13, 17, 21, 22 y 24.

Por ejemplo, el producto de estas últimas raíces primitivas es 26⋅ ⋅ 34⋅ ⋅ 7⋅ ⋅ 112⋅ ⋅ 13⋅ ⋅ 17=970377408↑ ↑ 1()mod31){displaystyle 2^{6}cdot 3^{4}cdot 7cdot 11^{2}cdot 13cdot 17=970377408equiv 1{pmod {31}}, y su suma es 123↑ ↑ − − 1↑ ↑ μ μ ()31− − 1)()mod31){displaystyle 123equiv -1equiv mu (31-1){pmod {31}}.

Si a{displaystyle a} es un modulo de la raíz primitiva p{displaystyle p}, entonces ap− − 12↑ ↑ − − 1()modp){displaystyle a^{frac {p-1}{2}equiv} - ¿Qué?.

La conjetura de Artin sobre las raíces primitivas establece que un número entero a no es ni un cuadrado perfecto ni −1 es una raiz primitiva con modulo de infinitos numeros primos.

Encontrar raíces primitivas

No fórmula general simple para calcular el modulo de raíces primitivas n es conocido. Sin embargo, hay métodos para localizar una raíz primitiva que es más rápida que simplemente probar a todos los candidatos. Si el orden multiplicativo (su exponente) de un número m modulo n es igual a φ φ ()n){displaystyle varphi (n)} (la orden de Z{displaystyle mathbb {Z}^×
_n), entonces es una raíz primitiva. De hecho el contrario es cierto: Si m es un modulo de raíz primitivo n, entonces el orden multiplicativo m es φ φ ()n)=λ λ ()n).{displaystyle varphi (n)=lambda (n)~.} Podemos usar esto para probar a un candidato m para ver si es primitivo.

Para 1}" xmlns="http://www.w3.org/1998/Math/MathML">n■1{displaystyle n confía1}1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ee74e1cc07e7041edf0fcbd4481f5cd32ad17b64" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;"/> primero, compute φ φ ()n).{displaystyle varphi (n)~.} Entonces determinar los diferentes factores principales φ φ ()n){displaystyle varphi (n)}, di p₁,... p_k. Finalmente, compute

gφ φ ()n)/pimodnparai=1,...... ,k{fn}bmod {fn}bquad {mbox{ for }i=1,ldotsk}

utilizando un algoritmo rápido para la exponenciación modular, como la exponenciación al cuadrado. Un número g para el cual estos k los resultados son todos diferentes de 1 es una raíz primitiva.

El número de raíces primitivas módulo n, si las hay, es igual a

φ φ ()φ φ ()n)){displaystyle varphi left(varphi (n)right)}

desde, en general, un grupo cíclico r elementos φ φ ()r){displaystyle varphi (r)} generadores, con r ser los enteros coprime n, que genera n.

Para el mejor n, esto es igual φ φ ()n− − 1){displaystyle varphi (n-1)}, y desde n/φ φ ()n− − 1)▪ ▪ O()log⁡ ⁡ log⁡ ⁡ n){displaystyle n/varphi (n-1)in O(log log n)} los generadores son muy comunes entre {2,... nY por lo tanto es relativamente fácil encontrar uno.

Si g es un módulo raíz primitivo p, entonces g también es un módulo raíz primitivo todas las potencias p^k a menos que g^p−1 ≡ 1 (mod p²); en ese caso, g + p es.

Si g es un módulo raíz primitivo p^k, entonces g es también un módulo raíz primitivo todas las potencias menores de p.

Si g es un módulo raíz primitivo p^k, luego g o g + p^k (cualquiera que sea impar) es una raíz primitiva módulo 2p^k.

Encontrar raíces primitivas módulo p también es equivalente a encontrar las raíces del (p − 1) módulo del polinomio ciclotómico p.

Orden de magnitud de raíces primitivas

La raíz menos primitiva g_p modulo p (en el rango 1, 2,..., p − 1) es generalmente pequeño.

Límites superiores

Burgess (1962) demostró que por cada ε ■ 0 hay un C tales que gp≤ ≤ Cp14+ε ε .{displaystyle G_{p}leq C,p^{frac {1}{4}+varepsilon }~

Grosswald (1981) demostró que si e^{e^{24}}approx 10^{11504079571}}" xmlns="http://www.w3.org/1998/Math/MathML">p■ee24.. 1011504079571{displaystyle p títuloe^{e^{24}approx 10^{11504079571}e^{e^{24}}approx 10^{11504079571}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0dfee8ad9d804c1e1d4e7fff3f47e83777d4f9b4" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:22.636ex; height:3.343ex;"/>, entonces <math alttext="{displaystyle g_{p}

gp.p0.499.{displaystyle ¿Qué?<img alt="{displaystyle g_{p}

Shoup (1990, 1992) probó, asumiendo la hipótesis generalizada de Riemann, que g_p = O(log⁶ p).

Límites inferiores

Fridlander (1949) y Salié (1950) demostraron que existe una constante positiva C tal que para infinitos números primos g_p > C registra p.

Se puede demostrar de manera elemental que para cualquier número entero positivo M existen infinitos números primos tales que M < g_p < p − M.

Aplicaciones

Un módulo raíz primitivo n se usa a menudo en generadores de números pseudoaleatorios y criptografía, incluido el esquema de intercambio de claves Diffie-Hellman. Los difusores de sonido se han basado en conceptos teóricos de números como raíces primitivas y residuos cuadráticos.