Aritmética modular

En matemáticas , la aritmética modular es un sistema de aritmética para números enteros , en el que los números "se enroscan" al alcanzar un valor determinado, llamado módulo . El enfoque moderno de la aritmética modular fue desarrollado por Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae , publicado en 1801.

Un uso familiar de la aritmética modular es en el reloj de 12 horas , en el que el día se divide en dos períodos de 12 horas. Si ahora son las 7:00, entonces 8 horas después serán las 3:00. La simple suma daría como resultado 7 + 8 = 15 , pero 15:00 se lee como 3:00 en la esfera del reloj porque los relojes "vuelven a la normalidad" cada 12 horas y el número de la hora comienza de nuevo en cero cuando llega a 12. Decimos que 15 es congruente con 3 módulo 12, escrito 15 ≡ 3 (mod 12), de modo que 7 + 8 ≡ 3 (mod 12). De manera similar, 8:00 representa un período de 8 horas, y dos veces esto daría 16:00, que se lee como 4:00 en la esfera del reloj, escrito como 2 × 8 ≡ 4 (mod 12).

Dado un entero m ≥ 1 , llamado módulo , se dice que dos enteros a y b son congruentes módulo m , si m es un divisor de su diferencia; es decir, si existe un entero k tal que

a − b = km .

La congruencia módulo m es una relación de congruencia , lo que significa que es una relación de equivalencia compatible con las operaciones de suma , resta y multiplicación . La congruencia módulo m se denota

a ≡ b (mód m ) .

Los paréntesis significan que (mod m ) se aplica a toda la ecuación, no solo al lado derecho (aquí, b ).

Esta notación no debe confundirse con la notación b mod m (sin paréntesis), que se refiere a la operación módulo , el resto de b cuando se divide por m : es decir, b mod m denota el único entero r tal que 0 ≤ r < m y r ≡ b (mod m ) .

La relación de congruencia puede reescribirse como

a = km + b ,

mostrando explícitamente su relación con la división euclidiana . Sin embargo, b aquí no tiene por qué ser el resto de la división de a por m . Más bien, a ≡ b (mod m ) afirma que a y b tienen el mismo resto cuando se dividen por m . Es decir,

a = pm + r ,

b = qm + r ,

donde 0 ≤ r < m es el resto común. Recuperamos la relación anterior ( a − b = km ) restando estas dos expresiones y haciendo k = p − q .

Como la congruencia módulo m se define por la divisibilidad por m y como -1 es una unidad en el anillo de los números enteros, un número es divisible por - m exactamente si es divisible por m . Esto significa que todo número entero distinto de cero m puede tomarse como módulo.

En el módulo 12, se puede afirmar que:

38 ≡ 14 (mód 12)

porque la diferencia es 38 − 14 = 24 = 2 × 12 , un múltiplo de 12 . De manera equivalente, 38 y 14 tienen el mismo resto 2 cuando se dividen por 12 .

La definición de congruencia también se aplica a valores negativos. Por ejemplo:

${\displaystyle {\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv 7{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}}$

La relación de congruencia satisface todas las condiciones de una relación de equivalencia :

• Reflexividad: a ≡ a (mod m )
• Simetría: a ≡ b (mod m ) si b ≡ a (mod m ) .
• Transitividad: Si a ≡ b (mod m ) y b ≡ c (mod m ) , entonces a ≡ c (mod m )

Si a ₁ ≡ b ₁ (mod m ) y a ₂ ≡ b ₂ (mod m ) , o si a ≡ b (mod m ) , entonces: ^[1]

• a + k ≡ b + k (mod m ) para cualquier entero k (compatibilidad con la traducción)
• ka ≡ kb (mod m ) para cualquier entero k (compatibilidad con escalamiento)
• ka ≡ kb (mod km ) para cualquier entero k
• a ₁ + a ₂ ≡ b ₁ + b ₂ (mod m ) (compatibilidad con la suma)
• a ₁ − a ₂ ≡ b ₁ − b ₂ (mod m ) (compatibilidad con la resta)
• a ₁ a ₂ ≡ b ₁ b ₂ (mod m ) (compatibilidad con la multiplicación)
• a ^k ≡ b ^k (mod m ) para cualquier entero no negativo k (compatibilidad con exponenciación)
• p ( a ) ≡ p ( b ) (mod m ) , para cualquier polinomio p ( x ) con coeficientes enteros (compatibilidad con la evaluación de polinomios)

Si a ≡ b (mod m ) , entonces generalmente es falso que k ^a ≡ k ^b (mod m ) . Sin embargo, lo siguiente es cierto:

• Si c ≡ d (mod φ ( m )), donde φ es la función totiente de Euler , entonces a ^c ≡ a ^d (mod m ) —siempre que a sea coprimo con m .

Para la cancelación de términos comunes, tenemos las siguientes reglas:

• Si a + k ≡ b + k (mod m ) , donde k es cualquier entero, entonces a ≡ b (mod m ) .
• Si ka ≡ kb (mod m ) y k es coprimo con m , entonces a ≡ b (mod m ) .
• Si ka ≡ kb (mod km ) y k ≠ 0 , entonces a ≡ b (mod m ) .

La última regla se puede utilizar para trasladar la aritmética modular a la división. Si b divide a a , entonces ( a / b ) mod m = ( a mod bm ) / b .

El inverso multiplicativo modular se define por las siguientes reglas:

• Existencia: Existe un entero denotado a ⁻¹ tal que aa ⁻¹ ≡ 1 (mód m ) si y solo si a es coprimo con m . Este entero a ⁻¹ se llama inverso multiplicativo modular de a módulo m .
• Si a ≡ b (mod m ) y a ⁻¹ existe, entonces a ⁻¹ ≡ b ⁻¹ (mod m ) (compatibilidad con inverso multiplicativo y, si a = b , unicidad módulo m ).
• Si ax ≡ b (mod m ) y a es coprimo de m , entonces la solución de esta congruencia lineal está dada por x ≡ a ⁻¹ b (mod m ) .

La inversa multiplicativa x ≡ a ⁻¹ (mod m ) se puede calcular de manera eficiente resolviendo la ecuación de Bézout a x + my = 1 para x , y , utilizando el algoritmo euclidiano extendido .

En particular, si p es un número primo, entonces a es coprimo con p para todo a tal que 0 < a < p ; por lo tanto existe un inverso multiplicativo para todo a que no sea congruente con cero módulo p .

Algunas de las propiedades más avanzadas de las relaciones de congruencia son las siguientes:

• Pequeño teorema de Fermat : Si p es primo y no divide a a , entonces a ^{p −1} ≡ 1 (mod p ) .
• Teorema de Euler : Si a y m son coprimos, entonces a ^{φ ( m )} ≡ 1 (mod m ) , donde φ es la función totiente de Euler .
• Una consecuencia simple del pequeño teorema de Fermat es que si p es primo, entonces a ⁻¹ ≡ a ^{p −2} (mod p ) es el inverso multiplicativo de 0 < a < p . De manera más general, a partir del teorema de Euler, si a y m son coprimos, entonces a ⁻¹ ≡ a ^{φ ( m )−1} (mod m ) . Por lo tanto, si ax ≡ 1 (mod m ) , entonces x ≡ a ^{φ ( m )−1} (mod m ) .
• Otra consecuencia simple es que si a ≡ b (mod φ ( m )) , donde φ es la función totiente de Euler, entonces k ^a ≡ k ^b (mod m ) siempre que k sea coprimo con m .
• Teorema de Wilson : p es primo si y sólo si ( p − 1)! ≡ −1 (mod p ) .
• Teorema del resto chino : para cualquier a , b y coprimo m , n , existe un único x (mod mn ) tal que x ≡ a (mod m ) y x ≡ b (mod n ) . De hecho, x ≡ bm _n ⁻¹ m + an _m ⁻¹ n (mod mn ) donde m _n ⁻¹ es el inverso de m módulo n y n _m ⁻¹ es el inverso de n módulo m .
• Teorema de Lagrange : Si p es primo y f ( x ) = a ₀ x ^d + ... + a _d es un polinomio con coeficientes enteros tales que p no es divisor de a ₀ , entonces la congruencia f ( x ) ≡ 0 (mod p ) tiene como máximo d soluciones no congruentes.
• Raíz primitiva módulo m : Un número g es una raíz primitiva módulo m si, para cada entero a coprimo con m , existe un entero k tal que g ^k ≡ a (mod m ) . Existe una raíz primitiva módulo m si y solo si m es igual a 2, 4, p ^k o 2 p ^k , donde p es un número primo impar y k es un entero positivo. Si existe una raíz primitiva módulo m , entonces existen exactamente φ ( φ ( m )) raíces primitivas de este tipo, donde φ es la función totiente de Euler.
• Residuos cuadráticos : Un entero a es un residuo cuadrático módulo m si existe un entero x tal que x ² ≡ a (mod m ) . El criterio de Euler afirma que, si p es un primo impar y a no es un múltiplo de p , entonces a es un residuo cuadrático módulo p si y solo si

  a ^{( p −1)/2} ≡ 1 (mód p ) .

La relación de congruencia es una relación de equivalencia . La clase de equivalencia módulo m de un entero a es el conjunto de todos los enteros de la forma a + km , donde k es cualquier entero. Se denomina clase de congruencia o clase de residuo de a módulo  m , y puede denotarse como ( a mod m ) , o como a o [ a ] ​​cuando el módulo m se conoce a partir del contexto.

Cada clase de residuo módulo  m contiene exactamente un entero en el rango . Por lo tanto, estos enteros son representantes de sus respectivas clases de residuo. ${\displaystyle 0,...,|m|-1}$${\displaystyle |m|}$

Generalmente es más fácil trabajar con números enteros que con conjuntos de números enteros; es decir, los representantes que se consideran con mayor frecuencia, en lugar de sus clases de residuos.

En consecuencia, ( a mod m ) denota generalmente el único entero k tal que 0 ≤ k < m y k ≡ a (mod m ) ; se llama residuo de a módulo  m .

En particular, ( a mod m ) = ( b mod m ) es equivalente a a ≡ b (mod m ) , y esto explica por qué a menudo se utiliza " = " en lugar de " ≡ " en este contexto.

Cada clase de residuo módulo m puede ser representada por cualquiera de sus miembros, aunque usualmente representamos cada clase de residuo por el entero no negativo más pequeño que pertenece a esa clase ^[2] (ya que este es el resto propio que resulta de la división). Cualesquiera dos miembros de diferentes clases de residuo módulo m son incongruentes módulo m . Además, cada entero pertenece a una y sólo una clase de residuo módulo m . ^[3]

El conjunto de números enteros {0, 1, 2, ..., m − 1} se denomina sistema de mínimo residuo módulo m . Cualquier conjunto de m números enteros, de los cuales ninguno de ellos es congruente módulo m , se denomina sistema de residuo completo módulo m .

El sistema de residuo mínimo es un sistema de residuo completo, y un sistema de residuo completo es simplemente un conjunto que contiene precisamente un representante de cada clase de residuo módulo m . ^[4] Por ejemplo, el sistema de residuo mínimo módulo 4 es {0, 1, 2, 3} . Algunos otros sistemas de residuo completo módulo 4 incluyen:

• {1, 2, 3, 4}
• {13, 14, 15, 16}
• {−2, −1, 0, 1}
• {−13, 4, 17, 18}
• {−5, 0, 6, 21}
• {27, 32, 37, 42}

Algunos conjuntos que no son sistemas de residuos completos módulo 4 son:

• {−5, 0, 6, 22} , ya que 6 es congruente con 22 módulo 4 .
• {5, 15} , ya que un sistema de residuos completo módulo 4 debe tener exactamente 4 clases de residuos incongruentes.

Dada la función totiente de Euler φ ( m ) , cualquier conjunto de números enteros φ ( m ) que sean primos entre sí con m y mutuamente incongruentes bajo el módulo m se denomina sistema de residuos reducidos módulo m . ^[5] El conjunto {5, 15} de arriba, por ejemplo, es una instancia de un sistema de residuos reducidos módulo 4.

Los sistemas de cobertura representan otro tipo de sistema de residuos que puede contener residuos con módulos variables.

Observación: En el contexto de este párrafo, el módulo m casi siempre se toma como positivo.

El conjunto de todas las clases de congruencia módulo m se denomina anillo de números enteros módulo m , ^[6] y se denota como , , o . ^[7] Sin embargo, la notación no se recomienda porque puede confundirse con el conjunto de números enteros m -ádicos . El anillo es fundamental para varias ramas de las matemáticas (véase § Aplicaciones más abajo).${\textstyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m}$${\displaystyle \mathbb {Z} _{m}}$${\displaystyle \mathbb {Z} _{m}}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

Para m > 0 se tiene

${\displaystyle \mathbb {Z} /m\mathbb {Z} =\left\{{\overline {a}}_{m}\mid a\in \mathbb {Z} \right\}=\left\{{\overline {0}}_{m},{\overline {1}}_{m},{\overline {2}}_{m},\ldots ,{\overline {m{-}1}}_{m}\right\}.}$

Cuando m = 1 , es el anillo cero ; cuando m = 0 , no es un conjunto vacío , sino que es isomorfo a , ya que a ₀ = { a } .${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} }$

La suma, la resta y la multiplicación se definen mediante las siguientes reglas:${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

• ${\displaystyle {\overline {a}}_{m}+{\overline {b}}_{m}={\overline {(a+b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}-{\overline {b}}_{m}={\overline {(a-b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}{\overline {b}}_{m}={\overline {(ab)}}_{m}.}$

Las propiedades dadas anteriormente implican que, con estas operaciones, es un anillo conmutativo . Por ejemplo, en el anillo , se tiene${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /24\mathbb {Z} }$

${\displaystyle {\overline {12}}_{24}+{\overline {21}}_{24}={\overline {33}}_{24}={\overline {9}}_{24}}$

como en la aritmética del reloj de 24 horas.

Se utiliza la notación porque este anillo es el anillo cociente de por el ideal , el conjunto formado por todos los km con${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} }$ ${\displaystyle m\mathbb {Z} }$${\displaystyle k\in \mathbb {Z} .}$

Considerado como un grupo bajo adición, es un grupo cíclico , y todos los grupos cíclicos son isomorfos con para algún m . ^[8]${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

El anillo de números enteros módulo m es un cuerpo si y solo si m es primo (esto garantiza que cada elemento distinto de cero tiene un inverso multiplicativo ). Si m = p ^k es una potencia prima con k > 1 , existe un cuerpo finito único (salvo isomorfismo) con m elementos, que no es isomorfo a , que no puede ser un cuerpo porque tiene divisores de cero .${\displaystyle \mathrm {GF} (m)=\mathbb {F} _{m}}$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

Si m > 1 , denota el grupo multiplicativo de los números enteros módulo m que son invertibles. Consiste en las clases de congruencia a _m , donde a es coprimo de m ; éstas son precisamente las clases que poseen un inverso multiplicativo. Forman un grupo abeliano bajo la multiplicación; su orden es φ ( m ) , donde φ es la función totiente de Euler${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}$

En matemáticas puras, la aritmética modular es uno de los fundamentos de la teoría de números y afecta a casi todos los aspectos de su estudio. También se utiliza ampliamente en la teoría de grupos , la teoría de anillos , la teoría de nudos y el álgebra abstracta . En matemáticas aplicadas, se utiliza en el álgebra computacional , la criptografía , la informática , la química y las artes visuales y musicales .

Una aplicación muy práctica es calcular sumas de comprobación dentro de identificadores de números de serie. Por ejemplo, el Número Internacional Normalizado de Libros (ISBN) utiliza la aritmética módulo 11 (para ISBN de 10 dígitos) o módulo 10 (para ISBN de 13 dígitos) para la detección de errores. Del mismo modo, los Números Internacionales de Cuentas Bancarias (IBAN), por ejemplo, utilizan la aritmética módulo 97 para detectar errores de entrada del usuario en números de cuentas bancarias. En química, el último dígito del número de registro CAS (un número de identificación único para cada compuesto químico) es un dígito de control , que se calcula tomando el último dígito de las dos primeras partes del número de registro CAS por 1, el dígito anterior por 2, el dígito anterior por 3, etc., sumando todos estos y calculando la suma módulo 10.

En criptografía, la aritmética modular sustenta directamente los sistemas de clave pública como RSA y Diffie–Hellman , y proporciona campos finitos que subyacen a las curvas elípticas , y se utiliza en una variedad de algoritmos de clave simétrica , incluidos el Estándar de cifrado avanzado (AES), el Algoritmo internacional de cifrado de datos (IDEA) y RC4 . RSA y Diffie–Hellman utilizan la exponenciación modular .

En álgebra computacional, la aritmética modular se utiliza comúnmente para limitar el tamaño de los coeficientes enteros en cálculos y datos intermedios. Se utiliza en la factorización polinómica , un problema para el cual todos los algoritmos eficientes conocidos utilizan aritmética modular. Se utiliza en las implementaciones más eficientes de máximo común divisor polinómico , álgebra lineal exacta y algoritmos de base de Gröbner sobre los números enteros y racionales. Como se publicó en Fidonet en la década de 1980 y se archivó en Rosetta Code , la aritmética modular se utilizó para refutar la conjetura de la suma de potencias de Euler en una microcomputadora Sinclair QL usando solo una cuarta parte de la precisión entera utilizada por una supercomputadora CDC 6600 para refutarla dos décadas antes mediante una búsqueda de fuerza bruta . ^[9]

En informática, la aritmética modular se aplica a menudo en operaciones bit a bit y otras operaciones que involucran estructuras de datos cíclicas de ancho fijo . La operación módulo, tal como se implementa en muchos lenguajes de programación y calculadoras , es una aplicación de la aritmética modular que se utiliza a menudo en este contexto. El operador lógico XOR suma 2 bits, módulo 2.

El uso de la división larga para convertir una fracción en un decimal periódico en cualquier base b es equivalente a la multiplicación modular de b módulo el denominador. Por ejemplo, para un decimal, b = 10.

En música, el módulo aritmético 12 se utiliza en la consideración del sistema de temperamento igual de doce tonos , donde se produce equivalencia de octava y enarmónica (es decir, los tonos en una proporción de 1:2 o 2:1 son equivalentes, y do sostenido se considera igual que re bemol ).

El método de eliminación de nueves ofrece una comprobación rápida de los cálculos aritméticos decimales realizados a mano. Se basa en la aritmética modular módulo 9 y, específicamente, en la propiedad crucial de que 10 ≡ 1 (mod 9).

La aritmética módulo 7 se utiliza en algoritmos que determinan el día de la semana de una fecha determinada. En particular, la congruencia de Zeller y el algoritmo Doomsday hacen un uso intensivo de la aritmética módulo 7.

De manera más general, la aritmética modular también tiene aplicación en disciplinas como el derecho (por ejemplo, la distribución proporcional ), la economía (por ejemplo, la teoría de juegos ) y otras áreas de las ciencias sociales , donde la división proporcional y la asignación de recursos juegan un papel central en el análisis.

Dado que la aritmética modular tiene una amplia gama de aplicaciones, es importante saber lo difícil que es resolver un sistema de congruencias. Un sistema lineal de congruencias se puede resolver en tiempo polinomial con una forma de eliminación gaussiana ; para obtener más detalles, consulte el teorema de congruencia lineal . También existen algoritmos, como la reducción de Montgomery , que permiten realizar operaciones aritméticas simples, como la multiplicación y la exponenciación módulo  m , de manera eficiente con números grandes.

Algunas operaciones, como hallar un logaritmo discreto o una congruencia cuadrática, parecen ser tan difíciles como la factorización de números enteros y, por lo tanto, son un punto de partida para algoritmos criptográficos y cifrado . Estos problemas podrían ser NP-intermedios .

La resolución de un sistema de ecuaciones aritméticas modulares no lineales es NP-completo . ^[10]

• John L. Berggren. "aritmética modular". Enciclopedia Británica .
• Apostol, Tom M. (1976), Introducción a la teoría analítica de números , Textos de pregrado en matemáticas, Nueva York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR  0434929, Zbl  0335.10001. Véanse en particular los capítulos 5 y 6 para una revisión de la aritmética modular básica.
• Maarten Bullynck "Aritmética modular antes de CF Gauss. Sistematizaciones y debates sobre problemas de resto en la Alemania del siglo XVIII"
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sección 31.3: Aritmética modular, págs. 862–868. 
• Anthony Gioia, Teoría de números, una introducción Reimpresión (2001) Dover. ISBN 0-486-41449-3 . 
• Long, Calvin T. (1972). Introducción elemental a la teoría de números (2.ª ed.). Lexington: DC Heath and Company . LCCN  77171950.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elementos de la teoría de números . Englewood Cliffs: Prentice Hall . ISBN 9780132683005. Código LCCN  71081766.
• Sengadir, T. (2009). Matemática discreta y combinatoria . Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8.OCLC 778356123  .

• "Congruencia", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• En este artículo sobre arte modular se puede aprender más sobre las aplicaciones de la aritmética modular en el arte.
• Un artículo sobre aritmética modular en la wiki de GIMPS
• Aritmética modular y patrones en las tablas de suma y multiplicación