En matemáticas , la aritmética modular es un sistema de aritmética para números enteros , donde los números se "envuelven" cuando alcanzan un cierto 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 son las 7:00 ahora, 8 horas después serán las 3:00. La suma simple daría como resultado 7 + 8 = 15 , pero los relojes se "envuelven" cada 12 horas. Debido a que el número de la hora comienza de nuevo después de llegar a 12, este es el módulo aritmético 12. En términos de la definición siguiente, 15 es congruente con 3 módulo 12, por lo que se muestra " 15:00" en un reloj de 24 horas "3:00 "en un reloj de 12 horas.
Congruencia
Dado un número entero n > 1 , llamado módulo , se dice que dos números enteros son módulo n congruentes , si n es un divisor de su diferencia (es decir, si hay un número entero k tal que a - b = kn ).
La congruencia módulo n 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 n se denota:
Los paréntesis significan que (mod n ) 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 n (sin paréntesis), que se refiere a la operación módulo . De hecho, b mod n denota el número entero único un tal que 0 ≤ un < n y (es decir, el resto de cuando se divide por [1] ).
La relación de congruencia puede reescribirse como
mostrando explícitamente su relación con la división euclidiana . Sin embargo, aquí no es necesario que b sea el resto de la división de a por n . En su lugar, lo que la declaración de un ≡ b (mod n ) afirma que es una y B tienen el mismo resto cuando se divide por n . Es decir,
donde 0 ≤ r < n es el resto común. Restando estas dos expresiones recuperamos la relación anterior:
estableciendo k = p - q .
Ejemplos de
En el módulo 12, se puede afirmar que:
porque 38 - 14 = 24 , que es un múltiplo de 12. Otra forma de expresar esto es decir que tanto 38 como 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:
Propiedades
La relación de congruencia satisface todas las condiciones de una relación de equivalencia :
- Reflexividad: a ≡ a (mod n )
- Simetría: a ≡ b (mod n ) si b ≡ a (mode n ) para todo a , b y n .
- Transitividad: Si a ≡ b (mod n ) y b ≡ c (mod n ) , entonces a ≡ c (mod n )
Si a 1 ≡ b 1 (mod n ) y a 2 ≡ b 2 (mode n ), o si a ≡ b (mod n ), entonces:
- a + k ≡ b + k (mod n ) para cualquier entero k (compatibilidad con traducción)
- ka ≡ kb (mod n ) para cualquier entero k (compatibilidad con escalado)
- a 1 + a 2 ≡ b 1 + b 2 (mod n ) (compatibilidad con la suma)
- a 1 - a 2 ≡ b 1 - b 2 (mod n ) (compatibilidad con la resta)
- a 1 a 2 ≡ b 1 b 2 (mod n ) (compatibilidad con la multiplicación)
- a k ≡ b k (mod n ) para cualquier entero no negativo k (compatibilidad con exponenciación)
- p ( a ) ≡ p ( b ) (mod n ) , para cualquier polinomio p ( x ) con coeficientes enteros (compatibilidad con evaluación polinomial)
Si a ≡ b (mod n ) , entonces generalmente es falso que k a ≡ k b (mod n ) . Sin embargo, lo siguiente es cierto:
- Si c ≡ d (mod φ ( n )), donde φ es la función totient de Euler , entonces a c ≡ a d (mod n ) - siempre que a sea coprime con n .
Para la cancelación de términos comunes, tenemos las siguientes reglas:
- Si a + k ≡ b + k (mod n ) , donde k es cualquier número entero, entonces a ≡ b (mod n )
- Si ka ≡ kb (mod n ) y k es primos entre sí con n , entonces un ≡ b (mod n )
- Si ka ≡ kb (mod kn ) , entonces a ≡ b (mod n )
El inverso multiplicativo modular se define mediante las siguientes reglas:
- Existencia: existe un número entero denotado a –1 tal que aa –1 ≡ 1 (mod n ) si y solo si a es coprime con n . Este entero a –1 se llama un inverso multiplicativo modular de un módulo n .
- Si un ≡ b (mod n ) y un -1 existe, entonces un -1 ≡ b -1 (mod n ) (compatibilidad con inverso multiplicativo, y, si es un = b , la singularidad de módulo n )
- Si ax ≡ b (mod n ) y una se primos entre sí a n , entonces la solución a esta congruencia lineal está dada por x ≡ un -1 b (mod n )
La inversa multiplicativa x ≡ a –1 (mod n ) se puede calcular de manera eficiente resolviendo la ecuación de Bézout por —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 es congruente con cero módulo p .
Algunas de las propiedades más avanzadas de las relaciones de congruencia son las siguientes:
- El pequeño teorema de Fermat : si p es primo y no divide a , entonces a p - 1 ≡ 1 (mod p ) .
- El teorema de Euler : Si una y n son primos entre sí, entonces un φ ( n ) ≡ 1 (mod n ) , donde φ es función totient de Euler
- Una consecuencia simple del pequeño teorema de Fermat es que si p es primo, entonces a −1 ≡ a p - 2 (mod p ) es el inverso multiplicativo de 0 < a < p . Más en general, desde el teorema de Euler, si una y n son primos entre sí, entonces un -1 ≡ un φ ( n ) - 1 (mod n ) .
- Otra consecuencia simple es que si a ≡ b (mod φ ( n )), donde φ es la función totient de Euler, entonces k a ≡ k b (mod n ) siempre que k sea coprime con n .
- Teorema de Wilson : ¡ p es primo si y solo si ( p - 1)! ≡ −1 (mod p ) .
- Teorema del residuo chino : Para cualquier a , by coprime m , n , existe una única x (mod mn ) tal que x ≡ a (mod m ) y x ≡ b (mod n ) . De hecho, x ≡ bm n –1 m + an m –1 n (mod mn ) donde m n −1 es la inversa de m módulo n y n m −1 es la inversa de n módulo m .
- Teorema de Lagrange : La congruencia f ( x ) ≡ 0 (mod p ) , donde p es primo, y f ( x ) = a 0 x n + ... + a n es un polinomio con coeficientes enteros tales que a 0 ≠ 0 (mod p ) , tiene como máximo n raíces.
- Raíz primitiva módulo n n : un número g es una raíz primitiva módulo n si, para cada número entero un primos entre sí a n , no es un número entero k tal que g k ≡ un (mod n ) . Existe una raíz primitiva módulo n si y solo si n es igual a 2, 4, p k o 2 p k , donde p es un número primo impar y k es un número entero positivo. Si existe una raíz primitiva módulo n , entonces existen exactamente φ ( φ ( n )) tales raíces primitivas, donde φ es la función totient de Euler.
- Residuo cuadrático : Un entero a es un residuo cuadrático módulo n , si existe un entero x tal que x 2 ≡ a (mod n ) . 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
Clases de congruencia
Como cualquier relación de congruencia, la congruencia módulo n es una relación de equivalencia , y la clase de equivalencia del entero a , denotado por a n , es el conjunto {…, a - 2 n , a - n , a , a + n , a + 2 n ,…} . Este conjunto, que consta de todos los números enteros congruentes con un módulo n , se denomina clase de congruencia , clase de residuo o simplemente residuo del entero a módulo n . Cuando el módulo n se conoce del contexto, ese residuo también se puede denotar [ a ] .
Sistemas de residuos
Cada clase de residuo módulo n puede estar representada por cualquiera de sus miembros, aunque normalmente 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 residuo propio que resulta de la división). Dos miembros cualesquiera de diferentes clases de residuos módulo n son módulo n incongruentes . Además, todo entero pertenece a una y solo una clase de residuo módulo n . [3]
El conjunto de números enteros {0, 1, 2,…, n - 1} se denomina sistema de mínimo residuo módulo n . Cualquier conjunto de n enteros, dos de los cuales no son congruentes módulo n , se denomina sistema de residuos completo módulo n .
El sistema de menor residuo 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 n . [4] Por ejemplo. el módulo 4 del sistema de menor residuo es {0, 1, 2, 3}. Algunos otros sistemas completos de residuos 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.
Sistemas de residuos reducidos
Dada la función totient de Euler φ ( n ) , cualquier conjunto de φ ( n ) números enteros que son relativamente primos para n y mutuamente incongruentes bajo módulo n se llama un reducido módulo sistema residuo n . [5] El conjunto {5,15} de arriba, por ejemplo, es un ejemplo de un sistema de residuo reducido módulo 4.
Enteros módulo n
El conjunto de todas las clases de congruencia de los enteros para un módulo n se llama anillo de números enteros módulo n , [6] y se denota, , o . [1] [7] La notaciónSin embargo, no se recomienda porque puede confundirse con el conjunto de enteros n -ádicos . El anilloes fundamental para varias ramas de las matemáticas (ver § Aplicaciones más abajo).
El conjunto se define para n > 0 como:
(Cuando n = 0 ,no es un conjunto vacío ; más bien, es isomorfo a, ya que a 0 = { a } .)
Definimos suma, resta y multiplicación en por las siguientes reglas:
La verificación de que esta es una definición adecuada utiliza las propiedades dadas anteriormente.
De este modo, se convierte en un anillo conmutativo . Por ejemplo, en el ring, tenemos
como en la aritmética para el reloj de 24 horas.
Usamos la notación porque este es el anillo cociente depor el ideal , un conjunto que contiene todos los enteros divisibles por n , dondees el conjunto de singleton {0} . Por lo tantoes un campo cuandoes un ideal máximo (es decir, cuando n es primo).
Esto también se puede construir a partir del grupo solo bajo la operación de adición. La clase de residuo a n es la clase lateral de grupo de a en el grupo del cociente , un grupo cíclico . [8]
En lugar de excluir el caso especial n = 0 , es más útil incluir (que, como se mencionó anteriormente, es isomorfo al anillo de enteros). De hecho, esta inclusión es útil cuando se habla de la característica de un anillo .
El anillo de números enteros módulo n es un campo finito si y solo si n es primo (esto asegura que cada elemento distinto de cero tenga un inverso multiplicativo ). Sies una potencia primaria con k > 1, existe un campo finito único (hasta isomorfismo)con n elementos, pero esto no es , que no es un campo porque tiene divisores cero .
El subgrupo multiplicativo de números enteros módulo n se denota por. Esto consiste en(donde una es primos entre sí a n ), que son precisamente las clases que poseen un inverso multiplicativo. Esto forma un grupo conmutativo bajo multiplicación, con orden.
Aplicaciones
En matemáticas teóricas, la aritmética modular es uno de los fundamentos de la teoría de números , toca casi todos los aspectos de su estudio, y también se usa 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 comprobación dentro de los identificadores de números de serie. Por ejemplo, International Standard Book Number (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 del 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 tomando el último dígito de las dos primeras partes del número de registro CAS multiplicado por 1, 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 las 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 de cifrado de datos internacional ( IDEA) y RC4 . RSA y Diffie-Hellman utilizan exponenciación modular .
En álgebra de computadora, 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 la factorización de polinomios , un problema para el que 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 los enteros y los números racionales. Como se publicó en Fidonet en la década de 1980 y se archivó en Rosetta Code , la aritmética modular se usó para refutar la conjetura de la suma de poderes 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 a través de una búsqueda de fuerza bruta . [9]
En ciencias de la computación, 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 de módulo , como se implementa en muchos lenguajes de programación y calculadoras , es una aplicación de aritmética modular que se usa a menudo en este contexto. El operador lógico XOR suma 2 bits, módulo 2.
En música, el módulo aritmético 12 se usa en la consideración del sistema de temperamento igual de doce tonos , donde ocurre la equivalencia de octava y enarmónico (es decir, los tonos en una proporción de 1∶2 o 2∶1 son equivalentes, y C- sostenido es considerado lo mismo que D- 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 módulo 7.
De manera más general, la aritmética modular también tiene aplicación en disciplinas como el derecho (p. Ej., Prorrateo ), 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.
Complejidad computacional
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, consulte el teorema de congruencia lineal . También existen algoritmos, como la reducción de Montgomery , que permiten realizar operaciones aritméticas sencillas, como la multiplicación y el módulo n de exponenciación , 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 intermedios .
Resolver un sistema de ecuaciones aritméticas modulares no lineales es NP-completo . [10]
Implementaciones de ejemplo
A continuación se muestran tres funciones C razonablemente rápidas, dos para realizar multiplicación modular y una para exponenciación modular en enteros sin signo no mayores de 63 bits, sin desbordamiento de las operaciones transitorias.
Una forma algorítmica de calcular : [11]
uint64_t mul_mod ( uint64_t a , uint64_t b , uint64_t m ) { if ( ! (( a | b ) & ( 0xFFFFFFFFULL << 32 ))) return a * b % m ; uint64_t d = 0 , mp2 = m >> 1 ; int i ; si ( a > = m ) a % = m ; si ( b > = m ) b % = m ; para ( i = 0 ; i < 64 ; ++ i ) { d = ( d > mp2 ) ? ( d << 1 ) - m : d << 1 ; si ( a & 0x8000000000000000ULL ) d + = b ; si ( d > = m ) d - = m ; a << = 1 ; } return d ; }
En arquitecturas de computadora donde está disponible un formato de precisión extendido con al menos 64 bits de mantisa (como el tipo doble largo de la mayoría de los compiladores x86 C), la siguiente rutina es [ aclaración necesaria ] , empleando el truco que, por hardware, flota -la multiplicación de puntos da como resultado los bits más significativos del producto que se mantienen, mientras que la multiplicación de enteros da como resultado los bits menos significativos que se mantienen: [ cita requerida ]
uint64_t mul_mod ( uint64_t a , uint64_t b , uint64_t m ) { long doble x ; uint64_t c ; int64_t r ; si ( a > = m ) a % = m ; si ( b > = m ) b % = m ; x = a ; c = x * b / m ; r = ( int64_t ) ( a * b - c * m ) % ( int64_t ) m ; devolver r < 0 ? r + m : r ; }
A continuación se muestra una función en C para realizar una exponenciación modular, que utiliza la función mul_mod implementada anteriormente.
Una forma algorítmica de calcular :
uint64_t pow_mod ( uint64_t a , uint64_t b , uint64_t m ) { uint64_t r = m == 1 ? 0 : 1 ; while ( b > 0 ) { if ( b & 1 ) r = mul_mod ( r , a , m ); b = b >> 1 ; a = mul_mod ( a , a , m ); } return r ; }
Sin embargo, para que funcionen todas las rutinas anteriores, m no debe exceder los 63 bits.
Ver también
- Anillo booleano
- Búfer circular
- División (matemáticas)
- Campo finito
- Símbolo de Legendre
- Exponenciación modular
- Modulo (matemáticas)
- Grupo multiplicativo de enteros módulo n
- Período Pisano (secuencias de Fibonacci módulo n )
- Raíz primitiva módulo n
- Reciprocidad cuadrática
- Residuo cuadrático
- Reconstrucción racional (matemáticas)
- Sistema de reducción de residuos
- Aritmética de números de serie (un caso especial de aritmética modular)
- Álgebra booleana de dos elementos
- Temas relacionados con la teoría de grupos detrás de la aritmética modular:
- Grupo cíclico
- Grupo multiplicativo de enteros módulo n
- Otros teoremas importantes relacionados con la aritmética modular:
- Teorema de carmichael
- Teorema del resto chino
- Teorema de euler
- El pequeño teorema de Fermat (un caso especial del teorema de Euler)
- Teorema de lagrange
- Lema de Thue
Notas
- ^ a b "Lista completa de símbolos de álgebra" . Bóveda de matemáticas . 2020-03-25 . Consultado el 12 de agosto de 2020 .
- ^ Weisstein, Eric W. "Aritmética modular" . mathworld.wolfram.com . Consultado el 12 de agosto de 2020 .
- ^ Pettofrezzo y Byrkit (1970 , p. 90)
- ↑ Long (1972 , p. 78)
- ↑ Long (1972 , p. 85)
- ^ Es un anillo , como se muestra a continuación.
- ^ "2.3: Enteros módulo n" . LibreTexts de Matemáticas . 2013-11-16 . Consultado el 12 de agosto de 2020 .
- ^ Sengadir T., Matemáticas discretas y combinatoria , p. 293, en Google Books
- ^ "Conjetura de la suma de poderes de Euler" . rosettacode.org . Consultado el 11 de noviembre de 2020 .
- ^ Garey, MR; Johnson, DS (1979). Las computadoras y la intratabilidad, una guía para la teoría de NP-Completeness . WH Freeman. ISBN 0716710447.
- ^ Este código usa la notación literal C para números hexadecimales largos sin signo, que terminan en
ULL
. Consulte también la sección 6.4.4 de la especificación de idioma n1570 .
Referencias
- John L. Berggren. "aritmética modular" . Encyclopædia Britannica .
- 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 0.335,10001. Ver 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 discusiones 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 reimpresión de introducció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 . Acantilados de Englewood: Prentice Hall . LCCN 71081766 .
- Sengadir, T. (2009). Matemática discreta y combinatoria . Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123 .
enlaces externos
- "Congruencia" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
- En este artículo de 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 el wiki de GIMPS
- Aritmética modular y patrones en tablas de suma y multiplicación