Raíz primitiva módulo n

En aritmética modular , un número g es una raíz primitiva módulo  n si todo número a coprimo con n es congruente con una potencia de g módulo n . Es decir, g es una raíz primitiva módulo  n si para todo entero a coprimo con n , existe algún entero k para el cual g ^k ≡ a (mod  n ). Tal valor k se denomina índice o logaritmo discreto de a en base g módulo n . Por lo tanto, g es una raíz primitiva módulo  n si y solo si g es un generador del grupo multiplicativo de los enteros módulo n .

Gauss definió las raíces primitivas en el artículo 57 de las Disquisitiones Arithmeticae (1801), donde atribuyó a Euler la invención del término. En el artículo 56 afirmó que Lambert y Euler las conocían, pero él 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 del artículo 55 es constructiva .

Existe una raíz primitiva si y solo si n es 1, 2, 4, p ^k o 2 p ^k , donde p es un primo impar y k > 0 . Para todos los demás valores de n el grupo multiplicativo de los enteros módulo n no es cíclico . ^{[1] [2] [3]} Esto fue demostrado por primera vez por Gauss . ^[4]

El número 3 es una raíz primitiva módulo 7 ^[5] porque $${\displaystyle {\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\end{matriz}}}$$

Aquí vemos que el periodo de 3 ^k módulo 7 es 6. Los restos en el periodo, que son 3, 2, 6, 4, 5, 1, forman un reordenamiento de todos los restos 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 el módulo  n produce un número finito de valores. Si g es una raíz primitiva módulo  n y n es primo, entonces el periodo de repetición es n − 1. Se ha demostrado que las permutaciones creadas de esta manera (y sus desplazamientos circulares) son matrices de Costas .

Si n es un entero positivo, los números enteros de 1 a n − 1 que son coprimos con n (o equivalentemente, las clases de congruencia coprimos con n ) forman un grupo , con multiplicación módulo n como operación; se denota por${\displaystyle \mathbb {Z}}$^×
_en, y se denomina grupo de unidades módulo n , o grupo de clases primitivas módulo n . Como se explica en el artículo grupo multiplicativo de números enteros módulo n , este grupo multiplicativo (${\displaystyle \mathbb {Z}}$^×
_en) es cíclico si y solo si n es igual a 2, 4, p ^k o 2 p ^k donde p ^k es una potencia de un número primo impar . ^{[6] [7] [8]} Cuando (y solo cuando) este grupo${\displaystyle \mathbb {Z}}$^×
_enes cíclico, un generador de este grupo cíclico se llama raíz primitiva módulo n ^[9] (o en un lenguaje más completo raíz primitiva de unidad módulo n , enfatizando su papel como una solución fundamental de las raíces de ecuaciones polinomiales unitarias X^metro
− 1 en el anillo _n ), o simplemente un elemento primitivo de${\displaystyle \mathbb {Z}}$ ${\displaystyle \mathbb {Z}}$^×
_en.

Cuando${\displaystyle \mathbb {Z}}$^×
_enno es cíclico, por lo que no existen elementos primitivos módulo n . En cambio, cada componente primo de n tiene sus propias raíces subprimitivas (ver 15 en los ejemplos siguientes).

Para cualquier n (sea o no${\displaystyle \mathbb {Z}}$^×
_enes cíclico), el orden de${\displaystyle \mathbb {Z}}$^×
_ense da por la función totiente de Euler φ ( n ) (secuencia A000010 en la OEIS ). Y luego, el teorema de Euler dice que a ^{φ ( n )} ≡ 1 (mod n ) para cada a coprimo con n ; la potencia más baja de a que es congruente con 1 módulo n se llama orden multiplicativo de a módulo n . En particular, para que a sea una raíz primitiva módulo n , a ^{φ ( n )} tiene que ser la potencia más pequeña de a que es congruente con 1 módulo n .

Por ejemplo, si n = 14 entonces los elementos de${\displaystyle \mathbb {Z}}$^×
_enson las clases de congruencia {1, 3, 5, 9, 11, 13}; hay φ (14) = 6 de ellas. Aquí hay una tabla de sus potencias módulo 14:

xx, x 2 , x 3 , ... (mód 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. Por lo tanto, 3 y 5 son las raíces primitivas módulo 14.

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

xx, x 2 , x 3 , ... (mód 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 existe ningún número cuyo orden sea 8, no existen raíces primitivas módulo 15. En efecto, λ (15) = 4 , donde λ es la función de Carmichael . (secuencia A002322 en la OEIS )

Los números que tienen una raíz primitiva tienen la forma ${\displaystyle n}$

${\displaystyle n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ prime}};\;k\in \mathbb {N} \},}$

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. ^[10]

Éstos son los números que también se mantienen en la secuencia A033948 en la OEIS . ${\displaystyle n}$${\displaystyle \varphi (n)=\lambda (n),}$

La siguiente tabla enumera las raíces primitivas módulo n hasta : ${\displaystyle n=31}$

Gauss demostró ^[11] 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ó ^[12] que para cualquier número primo p , la suma de sus raíces primitivas es congruente con μ ( p − 1) módulo p , donde μ es la función de Möbius .

Por ejemplo,

Por ejemplo, el producto de las últimas raíces primitivas es , y su suma es . ${\displaystyle 2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}}$${\displaystyle 123\equiv -1\equiv \mu (31-1){\pmod {31}}}$

Si es una raíz primitiva módulo el primo , entonces . ${\displaystyle a}$${\displaystyle p}$${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$

La conjetura de Artin sobre las raíces primitivas establece que un entero dado a que no es ni un cuadrado perfecto ni −1 es una raíz primitiva módulo infinitos primos .

No se conoce ninguna fórmula general sencilla para calcular raíces primitivas módulo n . ^{[a] [b]} Sin embargo, existen métodos para localizar una raíz primitiva que son más rápidos que simplemente probar todos los candidatos. Si el orden multiplicativo (su exponente ) de un número m módulo n es igual a (el orden de${\displaystyle \varphi (n)}$${\displaystyle \mathbb {Z} }$^×
_en), entonces es una raíz primitiva. De hecho, lo inverso es cierto: si m es una raíz primitiva módulo n , entonces el orden multiplicativo de m es Podemos usar esto para probar un candidato m para ver si es primitivo. ${\displaystyle \varphi (n)=\lambda (n)~.}$

Primero , calcule. Luego, determine los diferentes factores primos de , digamos p ₁ , ..., p _k . Finalmente, calcule ${\displaystyle n>1}$${\displaystyle \varphi (n)~.}$${\displaystyle \varphi (n)}$

${\displaystyle g^{\varphi (n)/p_{i}}{\bmod {n}}\qquad {\mbox{ for }}i=1,\ldots ,k}$

utilizando un algoritmo rápido para la exponenciación modular, como la exponenciación por cuadrado . Un número g para el cual estos k 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 ^[13]

${\displaystyle \varphi \left(\varphi (n)\right)}$

ya que, en general, un grupo cíclico con r elementos tiene generadores. ${\displaystyle \varphi (r)}$

Para el primo n , esto es igual a , y dado que los generadores son muy comunes entre {2, ..., n −1}, es relativamente fácil encontrar uno. ^[14]${\displaystyle \varphi (n-1)}$${\displaystyle n/\varphi (n-1)\in O(\log \log n)}$

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

Si g es una raíz primitiva módulo p ^k , entonces g también es una raíz primitiva módulo todas las potencias más pequeñas de p .

Si g es una raíz primitiva módulo p ^k , entonces g o g + p ^k (cualquiera que sea impar) es una raíz primitiva módulo 2 p ^k . ^[15]

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

La raíz menos primitiva g _p módulo p (en el rango 1, 2, ..., p − 1 ) es generalmente pequeña.

Burgess (1962) demostró ^{[16] [17]} que para cada ε > 0 existe una C tal que${\displaystyle g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }~.}$

Grosswald (1981) demostró ^{[16] [18]} que si , entonces${\displaystyle p>e^{e^{24}}\approx 10^{11504079571}}$${\displaystyle g_{p}<p^{0.499}~.}$

Shoup (1990, 1992) demostró, ^[19] asumiendo la hipótesis de Riemann generalizada , que g _p = O(log ⁶ p ).

Fridlander (1949) y Salié (1950) demostraron ^[16] que existe una constante positiva C tal que para infinitos primos g _p > C log p .

Se puede demostrar ^[16] de manera elemental que para cualquier entero positivo M existen infinitos primos tales que M < g _p < p − M .

En los generadores de números pseudoaleatorios ^[20] y en la criptografía , incluido el esquema de intercambio de claves Diffie-Hellman , se suele utilizar una raíz primitiva módulo n . Los difusores de sonido se han basado en conceptos de teoría de números, como raíces primitivas y residuos cuadráticos . ^{[21] [22]}

• Ore, Oystein (1988). Teoría de números y su historia. Dover. Págs. 284-302. ISBN. 978-0-486-65620-5..

• Weisstein, Eric W. "Raíz primitiva". MathWorld .
• Holt. "Residuos cuadráticos y raíces primitivas". Matemáticas. Michigan Tech.
• "Calculadora de raíces primitivas". BlueTulip .