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 (relativamente primos) con respecto a n del conjunto de n números enteros no negativos forman un grupo bajo módulo de multiplicación n , llamado grupo multiplicativo de números enteros módulo n . De manera equivalente, los elementos de este grupo pueden considerarse como clases de congruencia , también conocidas como residuos módulo n , que son coprimos de 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 inverso multiplicativo , que, en este anillo, son exactamente aquellos coprimos de n . ${\displaystyle \{0,1,\dots ,n-1\}}$

Este grupo cociente , normalmente denotado , es fundamental en la teoría de números . Se utiliza en criptografía , factorización de enteros y pruebas de primalidad . Es un grupo finito abeliano cuyo orden viene dado por la función totiente de Euler : para el número primo n , el grupo es cíclico y, en general, la estructura es fácil de describir, pero no se conoce ninguna 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 multiplicación, el conjunto de clases de congruencia módulo n que son coprimos de n satisfacen los axiomas de un grupo abeliano .

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

Dado que mcd( a , n ) = 1 y mcd( b , n ) = 1 implica mcd( ab , n ) = 1 , el conjunto de clases coprimos a n está cerrado bajo 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 de 1 es la identidad multiplicativa única.

Finalmente, dado a , el inverso multiplicativo de un módulo n es un número entero x que satisface ax ≡ 1 (mod n ) . Existe precisamente cuando a es coprimo de n , porque en ese caso mcd( a , n ) = 1 y según el lema de Bézout hay números enteros xey que satisfacen ax + ny = 1 . Observe que la ecuación ax + ny = 1 implica que x es coprimo de 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 suma y multiplicación es un anillo . Se denota   por o    (la notación se refiere a tomar el cociente de números enteros módulo el ideal o formado por los múltiplos de n ). Fuera de la teoría de números se utiliza a menudo la notación más simple , aunque puede confundirse con los 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 el alemán Einheit , 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 suma. Tenga en cuenta que o también puede referirse al grupo bajo suma. Por ejemplo, el grupo multiplicativo de un primo p es cíclico y, por 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 números enteros módulo n es el número de números enteros coprimos de n . Viene dada por la función totient de Euler : (secuencia A000010 en el 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 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 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 sólo 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 coprimo a n (las primeras potencias dan a cada uno exactamente una vez ). Un generador de se llama módulo raíz primitivo n . ^[5] Si hay algún generador, entonces los hay. ${\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, sólo hay una clase de congruencia, [0], coprimo a 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 del teorema. ${\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$

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

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

En el módulo 8 existen cuatro clases de congruencia coprimos, [1], [3], [5] y [7]. El cuadrado de cada uno de ellos 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},}$

En el módulo 16 existen ocho clases de congruencia coprimos [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 superiores 2 ^k , k > 2 : es el subgrupo de torsión 2, 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

Según el teorema fundamental de los grupos abelianos finitos , el grupo es isomorfo a un producto directo de grupos cíclicos de órdenes de potencias primarias. ${\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 primaria impar, el factor correspondiente es el grupo cíclico de orden , que puede factorizarse aún más en grupos cíclicos de órdenes de potencia primaria. 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 Carmichael (secuencia A002322 en la OEIS ). En otras palabras, es el número más pequeño tal que para cada uno de ellos se cumple un coprimo de n . Se divide y es igual a él si y sólo 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 testigos falsos

Si n es compuesto, existe un subgrupo propio de , llamado "grupo de testigos falsos", que comprende las soluciones de la ecuación , los elementos que, elevados a la potencia n − 1 , son congruentes a 1 módulo n . ^[8] El pequeño teorema de Fermat establece que para n = p un primo, este grupo consta de todos ; por lo tanto, para n compuesto, dichos residuos x son "falsos positivos" o "falsos testigos" de la primalidad de n . El número x = 2 se usa con mayor frecuencia en esta verificació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 cual x = 2 es un falso testigo de la primalidad. De hecho, el subgrupo de testigos falsos 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 de 9: 1, 2, 4, 5, 7, 8. Dado que 8 es congruente con −1 módulo 9 , se deduce que 8 ⁸ es congruente con 1 módulo 9. Entonces 1 y 8 son falsos positivos para la "primalidad" de 9 (ya que 9 en realidad no es 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 "falso testigo" para cualquier compuesto impar n .

norte = 91

Para n = 91 (= 7 × 13), hay residuos coprimos de 91, la mitad de ellos (es decir, 36 de ellos) son falsos testigos de 91, es decir, 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 de 561. El subgrupo de testigos falsos, en este caso, no es apropiado; es el grupo completo de unidades multiplicativas módulo 561, que consta de 320 residuos.

Ejemplos

Esta tabla muestra la descomposición cíclica de 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 siguiente tabla enumera la descomposición más corta (entre ellas, se elige la lexicográficamente primero; esto garantiza que los grupos isomórficos se enumeran 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 el módulo de raíz primitiva n más pequeño. ${\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 a 20 es congruente a 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 }}$

El mod n de raíz primitivo más pequeño 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 el OEIS )

Los números de los elementos en un conjunto generador mínimo de mod 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 el OEIS )

Ver también

• Factorización de la 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
3. (Vinogradov 2003, págs. 105-121, § VI RAÍCES E ÍNDICES PRIMITIVOS)
4. (Gauss y Clarke 1986, artículos 52–56, 82–891) harv error: no target: CITEREFGaussClarke1986 (help)
5. (Vinogradov 2003, pag.106)
6. (Gauss y Clarke 1986, artículos 90–91) harv error: no target: CITEREFGaussClarke1986 (help)
7. Riesel cubre todo esto. (Riesel 1994, págs. 267-275)
8. Erdős, Paul ; Pomerancia, 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 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), 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 Arithmeticae y otros artículos sobre teoría de números) (traducción alemana, segunda edición) , traducido por Maser, H., Nueva York: Chelsea, ISBN 978-0-8284-0191-3
• Riesel, Hans (1994), Números primos y métodos informáticos de factorización (segunda edición) , Boston: Birkhäuser, ISBN 978-0-8176-3743-9
• Vinogradov, IM (2003), "§ VI Raíces e índices primitivos", Elementos de teoría de números , Mineola, Nueva York: 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". MundoMatemático .
• Herramienta basada en web para calcular interactivamente tablas de grupos de 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ás pequeño m tal que el módulo del grupo multiplicativo m es el producto directo de n grupos cíclicos)