aritmética modular

En matemáticas , la aritmética modular es un sistema de operaciones aritméticas para números enteros , que se diferencia de las habituales en que los números se "redondean" al alcanzar o superar un cierto valor, llamado módulo . El enfoque moderno de la teoría de números mediante la aritmética modular fue desarrollado por Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae , publicado en 1801. ^{[ 1 ]}

La aritmética modular módulo $m$ consiste en reemplazar sistemáticamente los resultados de sumas, multiplicaciones y restas por el resto de la división por $m$ . Una propiedad notable de la aritmética modular es que el resultado de un cálculo no depende de si la división por $m$ se realiza después de cada operación, solo una vez al final del cálculo, o al final del cálculo y después de algunos resultados intermedios , generalmente cuando un resultado intermedio se vuelve demasiado grande.

Ejemplo motivador

Un ejemplo común de aritmética modular es la manecilla de las horas en un reloj de 12 horas . Si la manecilla marca las 7 ahora, 8 horas después marcará las 3. La suma ordinaria daría como resultado 7 + 8 = 15 , pero 15 se lee como 3 en la esfera del reloj. Esto se debe a que la manecilla de las horas da una vuelta completa cada 12 horas y la numeración de las horas se reinicia cuando la manecilla pasa las 12. Decimos que 15 es congruente con 3 módulo 12, y escribimos 15 ≡ 3 (mod 12), por lo que 7 + 8 ≡ 3 (mod 12).

De forma similar, si se esperan 8 horas y luego otras 8 (un total de 16 horas), el reloj mostrará el mismo cambio de hora que si se esperaran 4 horas. Esto se refleja en la identidad 2 × 8 ≡ 4 (mod 12). Tras una espera de exactamente 12 horas, la manecilla de las horas estará en la misma posición que al principio, por lo que 12 actúa como 0; se escribe 12 ≡ 0 (mod 12).

Congruencia

Dado un entero $m \geq 1$ , llamado módulo , se dice que dos enteros $a$ y $b$ son congruentes módulo $m$ , si su diferencia $a - b$ es un múltiplo entero de $m$ ; 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 la suma , la resta y la multiplicación . La congruencia módulo $m$ se denota por

a\equiv b{\pmod {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$ o $(b mod m)$ (sin paréntesis inmediatamente antes de "mod"), que se refiere al resto de $b$ cuando se divide por $m$ , conocido como la operación módulo ; es decir, $b mod m$ denota el único entero $r$ tal que $0 \leq r < m$ y $r \equiv b (mod m)$ . Por lo tanto, la relación $a\equiv b{\pmod {m}}$ debe ser leído $(a\equiv b){\bmod {m}},$ y es equivalente a $a{\bmod {m}}=b{\bmod {m}}.$

La relación de congruencia $a \equiv b (mod m)$ puede reescribirse como $\exists k\in \mathbb {Z} \quad a=km+b,$ mostrando explícitamente su relación con la división euclidiana . Sin embargo, aquí $b$ no tiene por qué ser el resto de la división de $a$ por $m .$ Más bien, $a \equiv 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 \leq r < m$ es el resto común. Recuperamos la relación anterior ( $a - b = km$ ) restando estas dos expresiones y estableciendo $k = p - q .$

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

Ejemplos

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

38 \equiv 14 (mod 12)

porque la diferencia es $38 - 14 = 24 = 2 \times 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:

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

Propiedades básicas

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

Reflexividad: $a \equiv a (mod m)$
Simetría: $a \equiv b (mod m)$ si y solo si $b \equiv a (mod m)$ .
Transitividad: Si $a \equiv b (mod m)$ y $b \equiv c (mod m)$ , entonces $a \equiv c (mod m).$

Si $a 1 \equiv b 1 (mod m)$ y $a 2 \equiv b 2 (mod m)$ , o si $a \equiv b (mod m)$ , entonces: ^{[ 2 ]}

$a + k \equiv b + k (mod m)$ para cualquier entero $k$ (compatibilidad con la traslación)
$ka \equiv kb (mod m)$ para cualquier entero $k$ (compatibilidad con escalado)
$ka \equiv kb (mod km)$ para cualquier entero $k$
$a 1 + a 2 \equiv b 1 + b 2 (mod m)$ (compatibilidad con la suma)
$a 1 - a 2 \equiv b 1 - b 2 (mod m)$ (compatibilidad con la resta)
$a 1 a 2 \equiv b 1 b 2 (mod m)$ (compatibilidad con la multiplicación)
$a k \equiv b k (mod m)$ para cualquier entero no negativo $k$ (compatibilidad con la exponenciación)
$p (a) \equiv p (b) (mod m)$ , para cualquier polinomio $p (x)$ con coeficientes enteros (compatibilidad con la evaluación de polinomios)

Si $a \equiv b (mod m)$ , entonces generalmente es falso que $k a \equiv k b (mod m)$ . Sin embargo, lo siguiente es verdadero:

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

Si $a \equiv b (mod mn)$ , entonces $a \equiv b (mod m)$ y $a \equiv b (mod n)$ .

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

Si $a + k \equiv b + k (mod m)$ , donde $k$ es cualquier entero, entonces $a \equiv b (mod m)$ .
Si $ka \equiv kb (mod m)$ y $k$ es coprimo con $m$ , entonces $a \equiv b (mod m)$ .
Si $ka \equiv kb (mod km)$ y $k \neq 0$ , entonces $a \equiv b (mod m)$ .

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:

Existencia: Existe un entero denotado $a -1$ tal que $aa -1 \equiv 1 (mod m)$ si y solo si $a$ es coprimo con $m$ . Este entero $a -1$ se llama inverso multiplicativo modular de $a$ módulo $m$ .
Si $a \equiv b (mod m)$ y existe $a -1 , entonces$ $a -1 \equiv b -1 (mod m)$ (compatibilidad con el inverso multiplicativo y, si $a = b$ , unicidad módulo $m$ ).
Si $ax \equiv b (mod m)$ y $a$ es coprimo con $m$ , entonces la solución a esta congruencia lineal viene dada por $x \equiv a -1 b (mod m)$ .

El inverso multiplicativo $x \equiv a -1 (mod m)$ puede calcularse 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 todo $a$ tal que $0 < a < p$ ; por lo tanto, existe un inverso multiplicativo para todo $a$ que no es congruente con cero módulo $p$ .

Propiedades avanzadas

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 \equiv 1 (mod p)$ .
Teorema de Euler : Si $a$ y $m$ son coprimos, entonces $a φ (m) \equiv 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 -1 \equiv a p -2 (mod p)$ es el inverso multiplicativo de $0 < a < p$ . Más generalmente, del teorema de Euler, si $a$ y $m$ son coprimos, entonces $a -1 \equiv a φ (m)-1 (mod m)$ . Por lo tanto, si $ax \equiv 1 (mod m)$ , entonces $x \equiv a φ (m)-1 (mod m)$ .
Otra consecuencia simple es que si $a \equiv b (mod φ (m))$ , donde $φ$ es la función totiente de Euler, entonces $k a \equiv k b (mod m)$ siempre que $k$ sea coprimo con $m$ .
Teorema de Wilson : $p$ es primo si y solo si $(p - 1)! \equiv -1 (mod p)$ .
Teorema chino del resto : Para cualesquiera $a$ , $b$ y coprimos $m$ , $n$ , existe un único $x (mod mn)$ tal que $x \equiv a (mod m)$ y $x \equiv b (mod n)$ . De hecho, $x \equiv bm n -1 m + an m -1 n (mod mn)$ donde $m n -1$ es el inverso de $m$ módulo $n$ y $n m -1$ es el inverso de $n$ módulo $m$ .
Teorema de Lagrange : Si $p$ es primo y $f (x) = a 0 x d + ... + a d$ es un polinomio con coeficientes enteros tal que $p$ no es un divisor de $a 0$ , entonces la congruencia $f (x) \equiv 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 \equiv a (mod m)$ . Una raíz primitiva módulo $m$ existe 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 hay exactamente $φ (φ (m))$ de tales raíces primitivas, donde $φ$ es la función totiente de Euler.
Residuo cuadrático : Un entero $a$ es un residuo cuadrático módulo $m$ si existe un entero $x$ tal que $x²$ $\equiv a (mod m)$ . El criterio de Euler afirma que, si $p$ es un primo impar y $a$ no es múltiplo de $p$ , entonces $a$ es un residuo cuadrático módulo $p$ si y solo si
$a (p -1)/2 \equiv 1 (mod p)$ .

Clases de congruencia

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 residual de $a$ 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 clase de residuo módulo $m$ contiene exactamente un entero en el rango $0,...,|m|-1$ Por lo tanto, estos $|m|$ Los números enteros son representantes de sus respectivas clases de residuos.

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

En consecuencia, $(a mod m)$ denota generalmente el único entero $r$ tal que $0 \leq r < m$ y $r \equiv a (mod m)$ ; se le llama el residuo de $a$ módulo $m$ .

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

Sistemas de residuos

Cada clase de residuo módulo $m$ puede representarse mediante cualquiera de sus miembros, aunque generalmente representamos cada clase de residuo mediante el entero no negativo más pequeño que pertenece a esa clase ^{[ 3 ]} (ya que este es el resto propio que resulta de la división). Dos miembros cualesquiera de clases de residuo diferentes módulo $m$ son incongruentes módulo $m$ . Además, cada entero pertenece a una y solo una clase de residuo módulo $m$ . ^{[ 4 ]}

El conjunto de enteros ${0, 1, 2, ..., m - 1}$ se denomina sistema de residuos mínimos módulo $m$ . Cualquier conjunto de $m$ enteros, de los cuales no hay dos congruentes módulo $m$ , se denomina sistema de residuos completos 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$ . ^{[ 5 ]} Por ejemplo, el sistema de residuos mínimos módulo $4$ es ${0, 1, 2, 3}$ . Algunos otros sistemas de residuos completos 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 totiente de Euler $φ (m)$ , cualquier conjunto de enteros $φ (m) que sean$ primos relativos con $m$ y mutuamente incongruentes bajo el módulo $m$ se denomina sistema de residuos reducidos módulo $m$ . ^{[ 6 ]} El conjunto ${5, 15}$ de arriba, por ejemplo, es una instancia de un sistema de residuos reducidos módulo 4.

Sistemas de cobertura

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

Enteros módulo m

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$ es un anillo llamado anillo de enteros módulo $m$ , y se denota ${\textstyle \mathbb {Z} /m\mathbb {Z} }$ , $\mathbb {Z} /(m)$ , $\mathbb {Z} /m$ , o $\mathbb {Z} _ {m}$ . ^{[ 7 ]} El anillo $\mathbb {Z} /m\mathbb {Z}$ es fundamental para varias ramas de las matemáticas (véase § Aplicaciones más abajo). (En algunas partes de la teoría de números la notación $\mathbb {Z} _ {m}$ se evita porque puede confundirse con el conjunto de enteros $m$ -ádicos .

Para $m > 0$ se tiene

\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$ , $\mathbb {Z} /m\mathbb {Z}$ es el anillo cero ; cuando $m = 0$ , $\mathbb {Z} /m\mathbb {Z}$ no es un conjunto vacío ; más bien, es isomorfo a $\mathbb {Z}$ , ya que $a 0 = {a}$ .

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

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

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

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

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

La notación $\mathbb {Z} /m\mathbb {Z}$ se utiliza porque este anillo es el anillo cociente de $\mathbb {Z}$ por el ideal $m\mathbb {Z}$ , el conjunto formado por todos los múltiplos de $m$ , es decir, todos los números $km$ con $k\in \mathbb {Z} .$

Además, $\mathbb {Z} /m\mathbb {Z}$ es un grupo cíclico . Todos los grupos cíclicos finitos son isomorfos con $\mathbb {Z} /m\mathbb {Z}$ para algún $m$ . ^{[ 8 ]}

El anillo de enteros módulo $m$ es un cuerpo ; es decir, todo elemento no nulo tiene un inverso multiplicativo si y solo si $m$ es primo . Si $m = p k$ es una potencia prima con $k > 1$ , existe un único cuerpo finito (salvo isomorfismo). $\mathrm {GF} (m)=\mathbb {F} _{m}$ con $m$ elementos, que no es isomorfo a $\mathbb {Z} /m\mathbb {Z}$ , que no es un campo porque tiene divisores de cero .

Si $m > 1$ , $(\mathbb {Z} /m\mathbb {Z} )^{\times }$ 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 con $m$ ; estas 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 .

Aplicaciones

En matemáticas puras, la aritmética modular es uno de los fundamentos de la teoría de números , presente en 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 emplea en álgebra computacional , criptografía , informática , química y artes visuales y musicales .

Una aplicación muy práctica es el cálculo de sumas de verificación dentro de los identificadores de números de serie. Por ejemplo, el Número Internacional Normalizado de Libros (ISBN) utiliza 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 Cuenta Bancaria (IBAN) utilizan aritmética módulo 97 para detectar errores de entrada del usuario en los números de cuenta bancaria. 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, por 2 el dígito anterior, por 3 el dígito anterior, etc., sumando todos estos resultados 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 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 cual todos los algoritmos eficientes conocidos utilizan aritmética modular. Se utiliza en las implementaciones más eficientes del máximo común divisor de polinomios , á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 Euler sobre la suma de potencias en una microcomputadora Sinclair QL, utilizando solo una cuarta parte de la precisión entera que una supercomputadora CDC 6600 utilizó para refutarla dos décadas antes mediante una búsqueda por fuerza bruta . ^[⁹^]

En informática, la aritmética modular se aplica frecuentemente 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 decimal, b = 10.

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

El método de extracción de nueves permite comprobar rápidamente 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 fundamental de que 10 ≡ 1 (mod 9).

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

En términos más generales, la aritmética modular también tiene aplicaciones en disciplinas como la política (por ejemplo, la distribución de escaños ), la economía (por ejemplo, la teoría de juegos ) y otras áreas de las ciencias sociales , donde la división y asignación proporcional de recursos juega un papel central en el análisis.

Complejidad computacional

Dado que la aritmética modular tiene una amplia gama de aplicaciones, es importante conocer la dificultad de resolver un sistema de congruencias. Un sistema lineal de congruencias puede resolverse en tiempo polinomial mediante una forma de eliminación gaussiana ; para más detalles, véase el teorema de congruencia lineal . También existen algoritmos, como la reducción de Montgomery , que permiten realizar de forma eficiente operaciones aritméticas sencillas, como la multiplicación y la exponenciación módulo $m , 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 enteros y, por lo tanto, constituyen un punto de partida para algoritmos criptográficos y cifrado . Estos problemas podrían ser NP-intermedios .

Resolver un sistema de ecuaciones aritméticas modulares no lineales es NP-completo . ^{[ 10 ]}

Véase también

Anillo booleano
Búfer circular
División (matemáticas)
Campo finito
Símbolo de Legendre
exponenciación modular
Módulo (matemáticas)
Grupo multiplicativo de enteros módulo n
Periodo de 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 residuos reducidos
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 que subyace a 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 chino del resto
- Teorema de Euler
- El pequeño teorema de Fermat (un caso especial del teorema de Euler)
- Teorema de Lagrange
- El lema de Thue

Notas

↑ Gray, Jeremy . Historia del álgebra abstracta: de las ecuaciones algebraicas al álgebra moderna . Alemania, Springer International Publishing, 2018. 143.
↑ Lehoczky y Rusczky 2006 .
↑ Weisstein .
↑ Pettofrezzo y Byrkit 1970 , pág. 90.
↑ Long 1972 , pág. 78.
↑ Long 1972 , pág. 85.
↑ Dentón 2013 .
↑ Sengadir T., Matemáticas discretas y combinatoria , pág. 293, en Google Libros
↑ "Conjetura de Euler sobre la suma de potencias" . rosettacode.org . Archivado del original el 26 de marzo de 2023. Consultado el 11 de noviembre de 2020 .
↑ Garey y Johnson 1979 .

Referencias

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 Consulte en particular los capítulos 5 y 6 para un repaso de la aritmética modular básica.

Berggren, John L. "Aritmética modular" . Encyclopædia Britannica .

Bullynck, Maarten. «Aritmética modular antes de C.F. Gauss: sistematizaciones y debates sobre problemas de resto en la Alemania del siglo XVIII» (PDF) . Archivado del original (PDF) el 2 de noviembre de 2013. Recuperado el 3 de febrero de 2018 .

Cormen, Thomas H.; Leiserson , Charles E.; Rivest , Ronald L .; Stein, Clifford (2001). «31.3: Aritmética modular». Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. págs. 862–868 . ISBN 0-262-03293-7.

Denton, Tom (16 de noviembre de 2013). "2.3: Enteros módulo n" . Mathematics LibreTexts . Archivado del original el 19 de abril de 2021. Recuperado el 12 de agosto de 2020 .

Garey, MR; Johnson, DS (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . WH Freeman. ISBN 0716710447.

Gioia, Anthony (2001). Teoría de números: Una introducción ( Edición reimpresa). Dover. ISBN 0-486-41449-3.

Lehoczky, Sandor; Rusczky, Richard (2006). Patrick, David (ed.). El arte de resolver problemas . Vol. 1 (7.ª ed.). AoPS Incorporated. pág. 44. ISBN 0977304566.

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. LCCN 71081766 .

Sengadir, T. (2009). Matemáticas discretas y combinatoria . Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8OCLC 778356123

Weisstein, Eric W. "Aritmética modular" . Wolfram MathWorld . Archivado del original el 14 de julio de 2023. Consultado el 12 de agosto de 2020 .

Enlaces externos

"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

[1] Gray, Jeremy . Historia del álgebra abstracta: de las ecuaciones algebraicas al álgebra moderna . Alemania, Springer International Publishing, 2018. 143.

[FOOTNOTELehoczkyRusczky2006-2] Lehoczky y Rusczky 2006 .

[FOOTNOTEWeisstein-3] Weisstein .

[FOOTNOTEPettofrezzoByrkit197090-4] Pettofrezzo y Byrkit 1970 , pág. 90.

[FOOTNOTELong197278-5] Long 1972 , pág. 78.

[FOOTNOTELong197285-6] Long 1972 , pág. 85.

[FOOTNOTEDenton2013-7] Dentón 2013 .

[8] Sengadir T., Matemáticas discretas y combinatoria , pág. 293, en Google Libros

[9] "Conjetura de Euler sobre la suma de potencias" . rosettacode.org . Archivado del original el 26 de marzo de 2023. Consultado el 11 de noviembre de 2020 .

[FOOTNOTEGareyJohnson1979-10] Garey y Johnson 1979 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[

[ 10 ]