Grupo multiplicativo de números enteros módulo n

Grupo de unidades del anillo de números enteros módulo n

En aritmética modular , los números enteros coprimos (primos relativos) con n del conjunto de n números enteros no negativos forman un grupo bajo la multiplicación módulo n , llamado grupo multiplicativo de números enteros módulo n . De manera equivalente, los elementos de este grupo pueden considerarse como las clases de congruencia , también conocidas como residuos módulo n , que son coprimos con n . De ahí que otro nombre sea el grupo de clases de residuos primitivos módulo n . En la teoría de anillos , una rama del álgebra abstracta , se describe como el grupo de unidades del anillo de números enteros módulo n . Aquí, unidades se refiere a elementos con un inverso multiplicativo , que, en este anillo, son exactamente aquellos coprimos con n . ${\displaystyle \{0,1,\dots ,n-1\}}$

Este grupo, usualmente denotado como , es fundamental en la teoría de números . Se utiliza en criptografía , factorización de números enteros y pruebas de primalidad . Es un grupo abeliano , finito cuyo orden está dado por la función totient de Euler : Para primo n el grupo es cíclico y en general la estructura es fácil de describir, pero no se conoce una fórmula general simple para encontrar generadores . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n).}$

Axiomas de grupo

Es un ejercicio sencillo demostrar que, bajo la multiplicación, el conjunto de clases de congruencia módulo n que son coprimos con n satisfacen los axiomas de un grupo abeliano .

De hecho, a es coprimo con n si y solo si mcd ( a , n ) = 1 . Los números enteros de la misma clase de congruencia a ≡ b (mod n ) satisfacen mcd( a , n ) = mcd( b , n ) ; por lo tanto, uno es coprimo con n si y solo si el otro lo es. Por lo tanto, la noción de clases de congruencia módulo n que son coprimos con n está bien definida.

Dado que mcd( a , n ) = 1 y mcd( b , n ) = 1 implica mcd( ab , n ) = 1 , el conjunto de clases coprimas a n es cerrado bajo la multiplicación.

La multiplicación de enteros respeta las clases de congruencia, es decir, a ≡ a' y b ≡ b' (mod n ) implica ab ≡ a'b' (mod n ) . Esto implica que la multiplicación es asociativa, conmutativa y que la clase 1 es la única identidad multiplicativa.

Finalmente, dado a , el inverso multiplicativo de a módulo n es un entero x que satisface ax ≡ 1 (mod n ) . Existe precisamente cuando a es coprimo con n , porque en ese caso mcd( a , n ) = 1 y por el lema de Bézout hay enteros x e y que satisfacen ax + ny = 1 . Nótese que la ecuación ax + ny = 1 implica que x es coprimo con n , por lo que el inverso multiplicativo pertenece al grupo.

Notación

El conjunto de (clases de congruencia de) números enteros módulo n con las operaciones de adición y multiplicación es un anillo . Se denota   o    (la notación se refiere a tomar el cociente de números enteros módulo el ideal o que consiste en los múltiplos de n ). Fuera de la teoría de números, a menudo se utiliza la notación más simple, aunque puede confundirse con los números enteros p -ádicos cuando n es un número primo. ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /(n)}$ ${\displaystyle n\mathbb {Z} }$ ${\displaystyle (n)}$ ${\displaystyle \mathbb {Z} _{n}}$

El grupo multiplicativo de números enteros módulo n , que es el grupo de unidades en este anillo, puede escribirse como (según el autor)   (para Einheit en alemán , que se traduce como unidad ), o notaciones similares. Este artículo utiliza ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}$   ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*},}$   ${\displaystyle \mathrm {U} (\mathbb {Z} /n\mathbb {Z} ),}$   ${\displaystyle \mathrm {E} (\mathbb {Z} /n\mathbb {Z} )}$ ${\displaystyle \mathbb {Z} _{n}^{*}}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}$

La notación se refiere al grupo cíclico de orden n . Es isomorfo al grupo de números enteros módulo n bajo adición. Nótese que o también puede referirse al grupo bajo adición. Por ejemplo, el grupo multiplicativo para un primo p es cíclico y, por lo tanto, isomorfo al grupo aditivo , pero el isomorfismo no es obvio. ${\displaystyle \mathrm {C} _{n}}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} _{n}}$ ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ ${\displaystyle \mathbb {Z} /(p-1)\mathbb {Z} }$

Estructura

El orden del grupo multiplicativo de los números enteros módulo n es el número de números enteros coprimos con n . Se da por la función totiente de Euler : (secuencia A000010 en la OEIS ). Para primo p , . ${\displaystyle \{0,1,\dots ,n-1\}}$ ${\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n)}$ ${\displaystyle \varphi (p)=p-1}$

Caso cíclico

El grupo es cíclico 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 no es cíclico. ^{[1] [2] [3]} Esto fue demostrado por primera vez por Gauss . ^[4] ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Esto significa que para estos n :

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \mathrm {C} _{\varphi (n)},}$dónde ${\displaystyle \varphi (p^{k})=\varphi (2p^{k})=p^{k}-p^{k-1}.}$

Por definición, el grupo es cíclico si y solo si tiene un generador g (un conjunto generador { g } de tamaño uno), es decir, las potencias dan todos los residuos posibles módulo n coprimos con n (las primeras potencias dan cada uno exactamente una vez). Un generador de se llama raíz primitiva módulo n . ^[5] Si hay algún generador, entonces hay de ellos. ${\displaystyle g^{0},g^{1},g^{2},\dots ,}$ ${\displaystyle \varphi (n)}$ ${\displaystyle g^{0},\dots ,g^{\varphi (n)-1}}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle \varphi (\varphi (n))}$

Potencias de 2

Módulo 1, dos números enteros cualesquiera son congruentes, es decir, solo hay una clase de congruencia, [0], coprimo con 1. Por lo tanto, es el grupo trivial con φ(1) = 1 elemento. Debido a su naturaleza trivial, el caso de congruencias módulo 1 generalmente se ignora y algunos autores optan por no incluir el caso de n = 1 en los enunciados de los teoremas. ${\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$

Módulo 2 solo hay una clase de congruencia coprima, [1], por lo que el grupo trivial es . ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$

Módulo 4 hay dos clases de congruencia coprimos, [1] y [3], por lo que el grupo cíclico tiene dos elementos. ${\displaystyle (\mathbb {Z} /4\mathbb {Z} )^{\times }\cong \mathrm {C} _{2},}$

Módulo 8 hay cuatro clases de congruencia coprimos, [1], [3], [5] y [7]. El cuadrado de cada una de ellas es 1, por lo que el grupo de cuatro de Klein . ${\displaystyle (\mathbb {Z} /8\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$

Módulo 16 hay ocho clases de congruencia coprimas [1], [3], [5], [7], [9], [11], [13] y [15]. es el subgrupo de torsión 2 (es decir, el cuadrado de cada elemento es 1), por lo que no es cíclico. Las potencias de 3, son un subgrupo de orden 4, al igual que las potencias de 5,   Por lo tanto ${\displaystyle \{\pm 1,\pm 7\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$ ${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }}$ ${\displaystyle \{1,3,9,11\}}$ ${\displaystyle \{1,5,9,13\}.}$ ${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{4}.}$

El patrón mostrado por 8 y 16 se cumple ^[6] para potencias mayores 2 ^k , k > 2 : es el subgrupo de 2-torsiones, por lo que no puede ser cíclico, y las potencias de 3 son un subgrupo cíclico de orden 2 ^{k − 2} , por lo que: ${\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$ ${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }}$

${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2^{k-2}}.}$

Números compuestos generales

Por el teorema fundamental de los grupos abelianos finitos , el grupo es isomorfo a un producto directo de grupos cíclicos de órdenes de potencia primos. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Más específicamente, el teorema del resto chino ^[7] dice que si entonces el anillo es el producto directo de los anillos correspondientes a cada uno de sus factores de potencia primos: ${\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

${\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} \dots \;\;}$

De manera similar, el grupo de unidades es el producto directo de los grupos correspondientes a cada uno de los factores de potencia primos: ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong (\mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} )^{\times }\dots \;.}$

Para cada potencia prima impar, el factor correspondiente es el grupo cíclico de orden , que puede factorizarse a su vez en grupos cíclicos de órdenes de potencias primas. Para potencias de 2, el factor no es cíclico a menos que k = 0, 1, 2, pero se factoriza en grupos cíclicos como se describió anteriormente. ${\displaystyle p^{k}}$ ${\displaystyle (\mathbb {Z} /{p^{k}}\mathbb {Z} )^{\times }}$ ${\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}}$ ${\displaystyle (\mathbb {Z} /{2^{k}}\mathbb {Z} )^{\times }}$

El orden del grupo es el producto de los órdenes de los grupos cíclicos en el producto directo. El exponente del grupo, es decir, el mínimo común múltiplo de los órdenes en los grupos cíclicos, viene dado por la función de Carmichael (secuencia A002322 en la OEIS ). En otras palabras, es el número más pequeño tal que para cada a coprimo de n , se cumple . Divide y es igual a él si y solo si el grupo es cíclico. ${\displaystyle \varphi (n)}$ ${\displaystyle \lambda (n)}$ ${\displaystyle \lambda (n)}$ ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$ ${\displaystyle \varphi (n)}$

Subgrupo de falsos testigos

Si n es compuesto, existe un subgrupo posiblemente propio de , llamado el "grupo de falsos testigos", que comprende las soluciones de la ecuación , los elementos que, elevados a la potencia n − 1 , son congruentes con 1 módulo n . ^[8] El pequeño teorema de Fermat establece que para n = p un primo, este grupo consta de todos los ; por lo tanto, para n compuesto, tales residuos x son "falsos positivos" o "falsos testigos" para la primalidad de n . El número x = 2 es el más utilizado en esta comprobación básica de primalidad, y n = 341 = 11 × 31 es notable ya que , y n = 341 es el número compuesto más pequeño para el que x = 2 es un falso testigo de primalidad. De hecho, el subgrupo de falsos testigos para 341 contiene 100 elementos, y es de índice 3 dentro del grupo de 300 elementos . ${\displaystyle \mathbb {Z} _{n}^{\times }}$ ${\displaystyle x^{n-1}=1}$ ${\displaystyle x\in \mathbb {Z} _{p}^{\times }}$ ${\displaystyle 2^{341-1}\equiv 1\mod 341}$ ${\displaystyle \mathbb {Z} _{341}^{\times }}$

Ejemplos

norte= 9

El ejemplo más pequeño con un subgrupo no trivial de testigos falsos es 9 = 3 × 3 . Hay 6 residuos coprimos con 9: 1, 2, 4, 5, 7, 8. Como 8 es congruente con −1 módulo 9 , se deduce que 8 ⁸ es congruente con 1 módulo 9. Por lo tanto, 1 y 8 son falsos positivos para la "primalidad" de 9 (ya que 9 no es realmente primo). De hecho, estos son los únicos, por lo que el subgrupo {1,8} es el subgrupo de testigos falsos. El mismo argumento muestra que n − 1 es un "testigo falso" para cualquier compuesto impar n .

norte= 91

Para n = 91 (= 7 × 13), hay residuos coprimos con 91, la mitad de ellos (es decir, 36 de ellos) son falsos testigos de 91, a saber, 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88 y 90, ya que para estos valores de x , x ⁹⁰ es congruente con 1 mod 91. ${\displaystyle \varphi (91)=72}$

norte= 561

n = 561 (= 3 × 11 × 17) es un número de Carmichael , por lo tanto s ⁵⁶⁰ es congruente con 1 módulo 561 para cualquier entero s coprimo con 561. El subgrupo de falsos testigos, en este caso, no es propio; es el grupo entero de unidades multiplicativas módulo 561, que consta de 320 residuos.

Ejemplos

Esta tabla muestra la descomposición cíclica de y un grupo electrógeno para n ≤ 128. La descomposición y los grupos electrógenos no son únicos; por ejemplo, ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

${\displaystyle \displaystyle {\begin{aligned}(\mathbb {Z} /35\mathbb {Z} )^{\times }&\cong (\mathbb {Z} /5\mathbb {Z} )^{\times }\times (\mathbb {Z} /7\mathbb {Z} )^{\times }\cong \mathrm {C} _{4}\times \mathrm {C} _{6}\cong \mathrm {C} _{4}\times \mathrm {C} _{2}\times \mathrm {C} _{3}\cong \mathrm {C} _{2}\times \mathrm {C} _{12}\cong (\mathbb {Z} /4\mathbb {Z} )^{\times }\times (\mathbb {Z} /13\mathbb {Z} )^{\times }\\&\cong (\mathbb {Z} /52\mathbb {Z} )^{\times }\end{aligned}}}$

(pero ). La tabla siguiente muestra la descomposición más corta (entre ellas, se elige la lexicográficamente primero; esto garantiza que los grupos isomorfos se enumeren con las mismas descomposiciones). El conjunto generador también se elige para que sea lo más corto posible y, para n con raíz primitiva, se enumera la raíz primitiva módulo n más pequeña. ${\displaystyle \not \cong \mathrm {C} _{24}\cong \mathrm {C} _{8}\times \mathrm {C} _{3}}$

Por ejemplo, tomemos . Entonces significa que el orden del grupo es 8 (es decir, hay 8 números menores que 20 y coprimos con él); significa que el orden de cada elemento divide a 4, es decir, la cuarta potencia de cualquier número coprimo con 20 es congruente con 1 (mod 20). El conjunto {3,19} genera el grupo, lo que significa que cada elemento de es de la forma 3 ^a × 19 ^b (donde a es 0, 1, 2 o 3, porque el elemento 3 tiene orden 4, y de manera similar b es 0 o 1, porque el elemento 19 tiene orden 2). ${\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$ ${\displaystyle \varphi (20)=8}$ ${\displaystyle \lambda (20)=4}$ ${\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$

La raíz primitiva más pequeña módulo n es (0 si no existe raíz)

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, ... (secuencia A046145 en la OEIS )

Los números de los elementos en un conjunto generador mínimo de módulo n son

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, ... (secuencia A046072 en la OEIS )

Véase también

• Factorización de curva elíptica de Lenstra

Notas

1. Weisstein, Eric W. "Grupo de multiplicación de módulos". MundoMatemático .
2. "Raíz primitiva - Enciclopedia de Matemáticas". encyclopediaofmath.org . Consultado el 6 de julio de 2024 .
3. Vinogradov 2003, pp. 105–121, § VI RAÍCES PRIMITIVAS E ÍNDICES
4. Gauss 1986, artículos. 52–56, 82–891.
5. Vinogradov 2003, pág. 106.
6. Gauss 1986, artículos 90–91.
7. Riesel aborda todos estos temas. Riesel 1994, págs. 267-275.
8. Erdős, Paul ; Pomerance, Carl (1986). "Sobre el número de testigos falsos para un número compuesto". Matemáticas de la computación . 46 (173): 259–279. doi : 10.1090/s0025-5718-1986-0815848-x . Zbl  0586.10003.

Referencias

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), Disquisitiones Arithmeticae (traducción al inglés, segunda edición corregida) , traducido por Clarke, Arthur A., ​​Nueva York: Springer , ISBN 978-0-387-96254-2
• Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae y otros artículos sobre teoría de números) (traducción al alemán, segunda edición) , traducido por Maser, H., Nueva York: Chelsea, ISBN 978-0-852-3-5 978-0-8284-0191-3
• Riesel, Hans (1994), Números primos y métodos informáticos para factorización (segunda edición) , Boston: Birkhäuser, ISBN 978-0-8176-3743-9
• Vinogradov, IM (2003), "§ VI Raíces primitivas e índices", Elementos de teoría de números , Mineola, NY: Dover Publications, págs. 105-121, ISBN 978-0-486-49530-9

Enlaces externos

• Weisstein, Eric W. "Grupo de multiplicación de módulos". MundoMatemático .
• Weisstein, Eric W. "Raíz primitiva". MathWorld .
• Herramienta basada en la web para calcular de forma interactiva tablas de grupos por John Jones
• Secuencia OEIS A033948 (Números que tienen una raíz primitiva (el grupo multiplicativo módulo n es cíclico))
• Números n tales que el grupo multiplicativo módulo n es el producto directo de k grupos cíclicos:
  • k = 2 secuencia OEIS A272592 (2 grupos cíclicos)
  • k = 3 secuencia OEIS A272593 (3 grupos cíclicos)
  • k = 4 secuencia OEIS A272594 (4 grupos cíclicos)
• Secuencia OEIS A272590 (El número m más pequeño tal que el grupo multiplicativo módulo m es el producto directo de n grupos cíclicos)