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]

Ejemplo elemental

El número 3 es una raíz primitiva módulo 7 ^[5] porque ${\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 .

Definición

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 $\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 ( $\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 $\mathbb {Z}$ ^×
_$en$es 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 $\mathbb {Z}$ $\mathbb {Z}$ ^×
_$en$.

Cuando $\mathbb {Z}$ ^×
_$en$no 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 $\mathbb {Z}$ ^×
_$en$es cíclico), el orden de $\mathbb {Z}$ ^×
_$en$se 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$ .

Ejemplos

Por ejemplo, si $n$ = 14 entonces los elementos de $\mathbb {Z}$ ^×
_$en$son 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 ² , x ³ , ... (mód 14) 1:1 3:3, 9, 13, 11, 5, 1 5:5, 11, 13, 9, 3, 1 9:9, 11, 111:11, 9, 113: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 $\mathbb {Z}$ ^×
₁₅son las clases de congruencia {1, 2, 4, 7, 8, 11, 13, 14}; hay $φ$ (15) = 8 de ellas.

xx, x ² , x ³ , ... (mód 15) 1:1 2:2, 4, 8, 1 4:4, 1 7:7, 4, 13, 1 8:8, 4, 2, 111:11, 113:13, 4, 7, 114: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 )

Tabla de raíces primitivas

Los números que tienen una raíz primitiva tienen la forma $n$

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 . $n$ $\varphi (n)=\lambda (n),$

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

Propiedades

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 . $2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}$ $123\equiv -1\equiv \mu (31-1){\pmod {31}}$

Si es una raíz primitiva módulo el primo , entonces . $a$ $p$ $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 .

Encontrando raíces primitivas

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 $\varphi (n)$ $\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. $\varphi (n)=\lambda (n)~.$

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

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]

\varphi \left(\varphi (n)\right)

ya que, en general, un grupo cíclico con $r$ elementos tiene generadores. $\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] $\varphi (n-1)$ $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$ .

Orden de magnitud de las raíces primitivas

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

Límites superiores

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

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

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

Límites inferiores

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

Aplicaciones

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]

Véase también

Notas al pie

^ "Uno de los problemas no resueltos más importantes en la teoría de campos finitos es el diseño de un algoritmo rápido para construir raíces primitivas. von zur Gathen & Shparlinski 1998, pp. 15-24
^ "No existe una fórmula conveniente para calcular [la raíz menos primitiva]". Robbins 2006, p. 159

Referencias

^ Weisstein, Eric W. "Grupo de multiplicación de módulos". MundoMatemático .
^ Raíz primitiva, Enciclopedia de Matemáticas
^ (Vinogradov 2003, págs. 105-121, § VI RAÍCES E ÍNDICES PRIMITIVOS)
^ (Gauss 1986, artículos 52-56, 82-891)
^ Stromquist, Walter. "¿Qué son las raíces primitivas?". Matemáticas. Bryn Mawr College. Archivado desde el original el 2017-07-03 . Consultado el 2017-07-03 .
^ Weisstein, Eric W. "Grupo de multiplicación de módulos". MundoMatemático .
^ Raíz primitiva, Enciclopedia de Matemáticas .
^ Vinogradov 2003, págs. 105–121, § VI Raíces primitivas e índices.
^ Vinogradov 2003, pág. 106.
^ Gauss 1986, artículo 92.
^ Gauss 1986, artículos 80.
^ Gauss 1986, artículo 81.
^ (secuencia A010554 en la OEIS )
^ Knuth, Donald E. (1998). Algoritmos seminuméricos . El arte de la programación informática. Vol. 2 (3.ª ed.). Addison–Wesley. Sección 4.5.4, página 391.
^ ab Cohen, Henri (1993). Un curso de teoría algebraica computacional de números . Berlín: Springer . pág. 26. ISBN. 978-3-540-55640-4.
^ abcd Ribenboim, Paulo (1996). El nuevo libro de registros de números primos . Nueva York, NY: Springer . p. 24. ISBN. 978-0-387-94457-9.
^ Burgess, DA (1962). "Sobre sumas de caracteres y raíces primitivas †". Actas de la London Mathematical Society . s3-12 (1): 179–192. doi :10.1112/plms/s3-12.1.179.
^ Grosswald, E. (1981). "Sobre el límite de Burgess para raíces primitivas módulo primos y una aplicación a Γ(p)". American Journal of Mathematics . 103 (6): 1171–1183. doi :10.2307/2374229. ISSN 0002-9327. JSTOR 2374229.
^ Bach y Shallit 1996, pág. 254.
^ Gentle, James E. (2003). Generación de números aleatorios y métodos de Monte Carlo (2.ª ed.). Nueva York: Springer. ISBN 0-387-00178-6.OCLC 51534945 .
^ Walker, R. (1990). El diseño y la aplicación de elementos modulares de difusión acústica (PDF) . Departamento de Investigación de la BBC (Informe). British Broadcasting Corporation . Consultado el 25 de marzo de 2019 .
^ Feldman, Eliot (julio de 1995). "Una rejilla de reflexión que anula la reflexión especular: un cono de silencio". J. Acoust. Soc. Am . 98 (1): 623–634. Bibcode :1995ASAJ...98..623F. doi :10.1121/1.413656.

Fuentes

Bach, Eric; Shallit, Jeffrey (1996). Algoritmos eficientes . Teoría algorítmica de números. Vol. I. Cambridge, MA: The MIT Press . ISBN 978-0-262-02405-1.

Carella, NA (2015). "Raíces primitivas mínimas". Revista internacional de matemáticas y ciencias de la computación . 10 (2): 185–194. arXiv : 1709.01172 .

Las Disquisitiones Arithmeticae han sido traducidas del latín ciceroniano de Gauss al inglés y al alemán. La edición alemana incluye todos sus artículos sobre teoría de números: todas las pruebas de reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre reciprocidad bicuadrática y notas inéditas.

Gauss, Carl Friedrich (1986) [1801]. Disquisiciones Arithmeticae . Traducido por Clarke, Arthur A. (segunda edición corregida). Nueva York, Nueva York: Springer . ISBN 978-0-387-96254-2.

Gauss, Carl Friedrich (1965) [1801]. Untersuchungen über höhere Arithmetik [ Estudios de aritmética superior ] (en alemán). Traducido por Maser, H. (2ª ed.). Nueva York, Nueva York: Chelsea. ISBN 978-0-8284-0191-3.

Robbins, Neville (2006). Introducción a la teoría de números. Jones & Bartlett Learning. ISBN 978-0-7637-3768-9.

Vinogradov, IM (2003). "§ VI Raíces primitivas e índices". Elementos de teoría de números . Mineola, NY: Dover Publications. pp. 105–121. ISBN. 978-0-486-49530-9.

von zur Gathen, Joachim ; Shparlinski, Igor (1998). "Órdenes de períodos de Gauss en cuerpos finitos". Álgebra aplicable en ingeniería, comunicación y computación . 9 (1): 15–24. CiteSeerX 10.1.1.46.5504 . doi :10.1007/s002000050093. MR 1624824. S2CID 19232025.

Lectura adicional

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

Enlaces externos

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 .