Módulo raíz primitivo n

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

Gauss definió las raíces primitivas en el artículo 57 de las Disquisitiones Arithmeticae (1801), donde le dio crédito a Euler por haber acuñado el 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 Disquisiciones 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 .

Una raíz primitiva existe si y sólo 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 números 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}{rcrcrcrccr}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}\ multiplicado por 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\end{array}}

Aquí vemos que el período de 3 ^$k$ módulo 7 es 6. Los restos del período, que son 3, 2, 6, 4, 5, 1, forman una reordenación de todos los restos distintos de cero módulo 7, lo que implica que 3 es de hecho un 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 período 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 a $n$ (o equivalentemente, las clases de congruencia coprimos a $n$ ) forman un grupo , con el módulo de multiplicación $n$ como operación; se denota por $\mathbb {Z}$ ^×
_$norte$, y se llama 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}$ ^×
_$norte$) es cíclico si y sólo si $n$ $es$ $igual$ a 2, 4, $pk$ o 2pk $donde$ pk $es$ una potencia de un número primo $impar$ . ^[6]^[7]^[8] Cuando (y sólo cuando) este grupo $\mathbb {Z}$ ^×
_$norte$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 solución fundamental de las raíces de ecuaciones polinómicas unitarias X^$metro$
− 1 en el anillo _$n$ ), o simplemente un elemento primitivo de $\mathbb {Z}$ $\mathbb {Z}$ ^×
_$norte$.

Cuando $\mathbb {Z}$ ^×
_$norte$es no cíclico, tales elementos primitivos mod $n$ no existen. En cambio, cada componente primo de $n$ tiene sus propias raíces subprimitivas (ver $15$ en los ejemplos siguientes).

Para cualquier $n$ (ya sea o no $\mathbb {Z}$ ^×
_$norte$es cíclico), el orden de $\mathbb {Z}$ ^×
_$norte$viene dada por la función totiente de Euler $φ$ ( $n$ ) (secuencia A000010 en el OEIS ). Y luego, el teorema de Euler dice que $a$ ^{$φ$ ( $n$ )} ≡ 1 (mod $n$ ) para todo $a$ coprimo de $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 sea congruente con 1 módulo $n$ .

Ejemplos

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

xx, x ² , x ³ , ... (mod 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 ellos.

xx, x ² , x ³ , ... (mod 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. De hecho, $λ$ (15) = 4 , donde $λ$ es la función de Carmichael . (secuencia A002322 en la OEIS )

Tabla de raíces primitivas.

Los números que tienen 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]

Estos son los números que también se mantienen en la secuencia A033948 en el 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 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 número entero dado $a$ que no es ni un cuadrado perfecto ni −1 es una raíz primitiva módulo de infinitos primos .

Encontrar raíces primitivas

No se conoce ninguna fórmula general simple para calcular el módulo $n de raíces primitivas.$ ^[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}$ ^×
_$norte$), entonces es una raíz primitiva. De hecho, lo contrario 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 al 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 un módulo de raíz primitivo $p$ , entonces $g$ también es un módulo de raíz primitivo para todas las potencias $p k$ a menos que $g$ ^{$p$ −1} ≡ 1 (mod $p$ ² ); en ese caso, $g$ + $p$ es. ^[15]

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

Si $g$ es un módulo de raíz primitivo $p k$ , entonces $g$ o $g$ + $p k$ (el que sea impar) es un módulo de raíz primitivo 2 $p k$ . ^[15]

Encontrar raíces primitivas módulo $p$ también es equivalente a encontrar las raíces del ( $p$ − 1)st 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 por cada ε > 0 existe un $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 generalizada de Riemann , 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 números primos $g p$ > $C$ log $p$ .

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

Aplicaciones

Un módulo raíz primitivo $n$ se utiliza a menudo en generadores de números pseudoaleatorios ^[20] y criptografía , incluido el esquema de intercambio de claves Diffie-Hellman . Los difusores de sonido se han basado en conceptos de la teoría de números como raíces primitivas y residuos cuadráticos . ^[21]^[22]

Ver también

Notas a pie de página

^ "Uno de los problemas sin resolver 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 y Shparlinski 1998, págs. 15-24
^ "No existe una fórmula conveniente para calcular [la raíz menos primitiva]". Robbins 2006, pág. 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 y Clarke 1986, artículos 52–56, 82–891)
^ Stromquist, Walter. "¿Qué son las raíces primitivas?". Matemáticas. Universidad Bryn Mawr. Archivado desde el original el 3 de julio de 2017 . Consultado el 3 de julio de 2017 .
^ 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.
^ Vinogradov 2003, pag. 106.
^ Gauss y Clarke 1986, artículo 92 .
^ Gauss y Clarke 1986, artes. 80 .
^ Gauss y Clarke 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. apartado 4.5.4, página 391.
^ ab Cohen, Henri (1993). Un curso de teoría algebraica computacional de números . Berlín: Springer . pag. 26.ISBN 978-3-540-55640-4.
^ abcd Ribenboim, Paulo (1996). El nuevo libro de registros de números primos . Nueva York, Nueva York: Springer . pag. 24.ISBN 978-0-387-94457-9.
^ Burgess, DA (1962). "Sobre sumas de caracteres y raíces primitivas †". Actas de la Sociedad Matemática de Londres . T3-12 (1): 179-192. doi :10.1112/plms/s3-12.1.179.
^ Grosswald, E. (1981). "Sobre Burgess' Bound for Primitive Roots Modulo Primes y una aplicación a Γ (p)". Revista Estadounidense de Matemáticas . 103 (6): 1171-1183. doi :10.2307/2374229. ISSN 0002-9327. JSTOR 2374229.
^ Bach y Shallit 1996, pág. 254.
^ Gentil, 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.
^ Caminante, R. (1990). El diseño y aplicación de elementos difusores acústicos modulares (PDF) . Departamento de Investigación de la BBC (Reporte). 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. acústico. Soc. Soy . 98 (1): 623–634. Código bibliográfico : 1995ASAJ...98..623F. doi : 10.1121/1.413656.

Fuentes

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

Carella, NA (2015). "Raíces primitivas menos primas". Revista Internacional de Matemáticas e Informática . 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 la reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre la 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). Principio de la teoría de números. Aprendizaje de Jones y Bartlett. ISBN 978-0-7637-3768-9.

Vinogradov, IM (2003). "§ VI Raíces e índices primitivos". Elementos de la teoría de números . Mineola, Nueva York: Publicaciones de Dover. págs. 105-121. ISBN 978-0-486-49530-9.

von zur Gathen, Joaquín ; Shparlinski, Igor (1998). "Órdenes de períodos de Gauss en campos finitos". Álgebra Aplicable en Ingeniería, Comunicaciones y Computación . 9 (1): 15-24. CiteSeerX 10.1.1.46.5504 . doi :10.1007/s002000050093. SEÑOR 1624824. S2CID 19232025.

Otras lecturas

Mineral, 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". MundoMatemático .
Bosquecillo. "Residuos cuadráticos y raíces primitivas". Matemáticas. Tecnología de Michigan.
"Calculadora de raíces primitivas". Tulipán azul .