En matemáticas , la aritmética modular es un sistema de aritmética para números enteros , donde los números "da vuelta" al alcanzar un determinado valor, 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 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, 8 horas más tarde serán las 3:00. Una 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 "giran" cada 12 horas y el número de hora comienza de nuevo en cero cuando llega a las 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, las 8:00 representan un período de 8 horas, y el doble daría 16:00, que se lee como 4:00 en la esfera del reloj, escrito como 2 × 8 ≡ 4 (mod 12).
Dado un número entero m ≥ 1 , llamado módulo , se dice que dos números enteros a y b son congruentes módulo m , si m es un divisor de su diferencia; es decir, si existe un número entero k tal que
El módulo de congruencia m es una relación de congruencia , lo que significa que es una relación de equivalencia que es compatible con las operaciones de suma , resta y multiplicación . El módulo de congruencia m se denota
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 de módulo , el resto de b cuando se divide por m : es decir, b mod m denota el entero único r tal que 0 ≤ r < metro y r ≡ b (mod m ) .
La relación de congruencia puede reescribirse como
mostrando explícitamente su relación con la división euclidiana . Sin embargo, aquí la b 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 . Eso es,
donde 0 ≤ r < m es el resto común. Recuperamos la relación anterior ( a − b = km ) restando estas dos expresiones y estableciendo k = p − q .
Debido a que el módulo de congruencia m está definido por la divisibilidad entre m y debido a que -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 entero m distinto de cero puede tomarse como módulo.
En el módulo 12 se puede afirmar que:
porque la diferencia es 38 − 14 = 24 = 2 × 12 , 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 los valores negativos. Por ejemplo:
La relación de congruencia satisface todas las condiciones de una relación de equivalencia :
Si a 1 ≡ b 1 (mod m ) y a 2 ≡ b 2 (mod m ) , o si a ≡ b (mod m ) , entonces: [1]
Si a ≡ b (mod m ) , entonces generalmente es falso que k a ≡ k b (mod m ) . Sin embargo, lo siguiente es cierto:
Para la cancelación de términos comunes, tenemos las siguientes reglas:
La última regla se puede utilizar para trasladar la aritmética modular a la división. Si b divide a , entonces ( a / b ) mod m = ( a mod bm )/ b .
El inverso multiplicativo modular se define mediante las siguientes reglas:
El inverso multiplicativo x ≡ a −1 (mod m ) se puede calcular eficientemente 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 cada a tal que 0 < a < p ; por 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:
La relación de congruencia es una relación de equivalencia . La clase de equivalencia módulo m de un número entero a es el conjunto de todos los números enteros de la forma a + km , donde k es cualquier número entero. Se llama clase de congruencia o clase de residuo de un módulo m , y puede denotarse como ( a mod m ) , o como a o [ a ] cuando el módulo m se conoce por el contexto.
Cada módulo m de clase de residuo contiene exactamente un número entero en el rango . Por tanto, estos números enteros son representantes de sus respectivas clases de residuos.
Generalmente es más fácil trabajar con números enteros que con conjuntos de números enteros; es decir, los representantes considerados 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 < my k ≡ a ( mod m ) ; se llama residuo de un módulo m .
En particular, ( a mod m ) = ( b mod m ) es equivalente a a ≡ b (mod m ) , y esto explica por qué " = " se usa a menudo en lugar de " ≡ " en este contexto.
Cada clase de residuo módulo m puede representarse por cualquiera de sus miembros, aunque generalmente 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 adecuado que resulta de la división). Dos miembros cualesquiera de diferentes clases de residuos módulo m son incongruentes módulo m . Además, cada número 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 no hay dos que sean congruentes módulo m , se denomina sistema de residuos completo módulo m .
El sistema de residuos mínimos es un sistema de residuos completo, y un sistema de residuos completo es simplemente un conjunto que contiene precisamente un representante de cada clase de residuo módulo m . [4] Por ejemplo, el módulo 4 del sistema de residuos mínimos es {0, 1, 2, 3} . Algunos otros sistemas completos de residuos módulo 4 incluyen:
Algunos conjuntos que no son sistemas de residuos completos módulo 4 son:
Dada la función totiente de Euler φ ( m ) , cualquier conjunto de enteros φ ( m ) que sean primos relativos con my mutuamente incongruentes bajo el módulo m se denomina sistema de residuos reducido módulo m . [5] El conjunto {5, 15} de arriba, por ejemplo, es un ejemplo de un sistema de residuos reducido módulo 4.
Los sistemas de cobertura representan otro tipo de sistema de residuos que puede contener residuos con diferentes módulos.
Observación: En el contexto de este párrafo, el módulo m casi siempre se considera positivo.
El conjunto de todas las clases de congruencia módulo m se llama anillo de números enteros módulo m , [6] y se denota , o . [7] Sin embargo, no se recomienda la notación porque puede confundirse con el conjunto de enteros m -ádicos . El anillo es fundamental para varias ramas de las matemáticas (ver § Aplicaciones a continuación).
Para m > 0 se tiene
Cuando m = 1 , es el anillo cero ; cuando m = 0 , no es un conjunto vacío ; más bien, es isomorfo a , ya que a 0 = { a } .
La suma, la resta y la multiplicación se definen mediante las siguientes reglas:
Las propiedades dadas antes implican que, con estas operaciones, es un anillo conmutativo . Por ejemplo, en el ring , uno tiene
como en la aritmética del reloj de 24 horas.
La notación se utiliza porque este anillo es el anillo cociente de por el ideal , el conjunto formado por todos los km con
Considerado como un grupo bajo suma, es un grupo cíclico , y todos los grupos cíclicos son isomorfos para algunos m . [8]
El anillo de números enteros módulo m es un campo si y solo si m es primo (esto asegura que cada elemento distinto de cero tenga un inverso multiplicativo ). Si m = p k es una potencia prima con k > 1 , existe un campo finito único (hasta el isomorfismo) con m elementos, que no es isomorfo a , que no es un campo porque tiene divisores cero .
Si m > 1 , denota el grupo multiplicativo de los enteros módulo m que son invertibles. Consiste en las clases de congruencia a m , donde a es coprimo de m ; estas son precisamente las clases que poseen un inverso multiplicativo. Forman un grupo abeliano bajo multiplicación; su orden es φ ( m ) , donde φ es la función totiente de Euler
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, y también se utiliza ampliamente en teoría de grupos , teoría de anillos , teoría de nudos y álgebra abstracta . En matemáticas aplicadas, se utiliza en álgebra informática , criptografía , informática , química y artes visuales y musicales .
Una aplicación muy práctica es calcular sumas de verificación dentro de identificadores de números de serie. Por ejemplo, el Número Internacional Estándar de Libros (ISBN) utiliza aritmética de 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 de cuentas bancarias internacionales (IBAN), por ejemplo, utilizan la aritmética de módulo 97 para detectar errores de entrada del usuario en los 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 multiplicando por 1 el último dígito de las dos primeras partes del número de registro CAS, el dígito anterior. multiplicado por 2, el dígito anterior multiplicado 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 curvas elípticas , y se utiliza en una variedad de algoritmos de clave simétrica , incluido el Estándar de cifrado avanzado (AES), el Algoritmo internacional de cifrado de datos ( IDEA) y RC4 . RSA y Diffie-Hellman utilizan exponenciación modular .
En álgebra informática, la aritmética modular se usa comúnmente para limitar el tamaño de los coeficientes enteros en cálculos y datos intermedios. Se utiliza en factorización de polinomios , problema para el cual todos los algoritmos eficientes conocidos utilizan aritmética modular. Es utilizado por las implementaciones más eficientes del máximo común divisor polinomial , álgebra lineal exacta y algoritmos de base de Gröbner sobre números enteros y racionales. Como se publicó en Fidonet en la década de 1980 y se archivó en Rosetta Code , se usó aritmética modular para refutar la conjetura de la suma de potencias de Euler en una microcomputadora Sinclair QL usando solo un cuarto 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 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 una 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 decimal, b = 10.
En música, el módulo aritmético 12 se utiliza al considerar el sistema de temperamento igual de doce tonos , donde se produce equivalencia de octava y enarmónico (es decir, los tonos en una proporción de 1:2 o 2:1 son equivalentes, y el do sostenido es considerado lo mismo que re bemol ).
El método de sacar 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).
El módulo aritmético 7 se utiliza en algoritmos que determinan el día de la semana para una fecha determinada. En particular, la congruencia de Zeller y el algoritmo Doomsday hacen un uso intensivo de la aritmética de módulo 7.
De manera más general, la aritmética modular también tiene aplicación en disciplinas como el derecho (p. ej., reparto ), la economía (p. ej., teoría de juegos ) y otras áreas de las ciencias sociales , donde la división proporcional y la asignación de recursos juega una parte central del análisis.
Dado que la aritmética modular tiene una gama tan amplia de aplicaciones, es importante saber qué tan difícil 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 más detalles ver teorema de congruencia lineal . Los algoritmos, como la reducción de Montgomery , también existen para permitir que operaciones aritméticas simples, como la multiplicación y el módulo de exponenciación m , se realicen de manera eficiente en números grandes.
Algunas operaciones, como encontrar 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 los algoritmos criptográficos y el cifrado . Estos problemas pueden ser NP-intermedio .
Resolver un sistema de ecuaciones aritméticas modulares no lineales es NP-completo . [10]