Aritmética modular

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).

Congruencia

Dado un número entero $n \geq 1$ , llamado módulo , se dice que dos números enteros $a$ y $b$ son congruentes módulo $n$ , si $n$ es un divisor de su diferencia; es decir, si existe un número entero $k$ tal que

a - b = kn

El módulo de congruencia $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

a \equiv b (mod norte)

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 de módulo , el resto de $b$ cuando se divide por $n$ : es decir, $b mod n$ denota el entero único $r$ tal que $0 \leq r < n$ y $r \equiv b (mod n)$ .

La relación de congruencia puede reescribirse como

a = kn + 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 $n .$ Más bien, $a \equiv b (mod n)$ afirma que $a$ y $b$ tienen el mismo resto cuando se dividen por $n$ . Eso es,

a = pn + r

b = qn + r

donde $0 \leq r < n$ es el resto común. Recuperamos la relación anterior: $a - b = kn$ restando estas dos expresiones y estableciendo $k = p - q .$

Ejemplos

En el módulo 12 se puede afirmar que:

38 \equiv 14 (módulo 12)

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

{\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv 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 n)$
Simetría: $a \equiv b (mod n)$ si $b \equiv a (mod n)$ .
Transitividad: Si $a \equiv b (mod n)$ y $b \equiv c (mod n)$ , entonces $a \equiv c (mod n)$

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

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

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

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

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

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

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

El inverso multiplicativo modular se define mediante las siguientes reglas:

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

El inverso multiplicativo $x \equiv a -1 (mod n)$ se puede calcular eficientemente resolviendo la ecuación de Bézout $ax + ny = 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 lo tanto, existe un inverso multiplicativo para todo $a$ que no sea congruente con cero módulo $p$ .

Propiedades avanzadas

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$ , entonces $a p -1 \equiv 1 (mod p)$ .
Teorema de Euler : Si $a$ y $n$ son coprimos, entonces $a φ (n) \equiv 1 (mod n)$ , 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$ . De manera más general, según el teorema de Euler, si $a$ y $n$ son coprimos, entonces $a -1 \equiv a φ (n) -1 (mod n)$ .
Otra consecuencia simple es que si $a \equiv b (mod φ (n))$ , donde $φ$ es la función totiente de Euler, entonces $k a \equiv k b (mod n)$ siempre que $k$ sea coprimo con $n$ .
Teorema de Wilson : $p$ es primo si y sólo si $(p - 1)! \equiv -1 (mod p)$ .
Teorema del resto chino : para cualquier $a$ , $b$ y coprimo $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 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) \equiv 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 \neq 0 (mod p)$ , tiene como máximo $n$ raíces.
Módulo de raíz primitiva $n$ : Un número $g$ es un módulo de raíz primitiva $n$ si, para cada número entero $coprimo$ de $n$ , hay un número entero $k$ tal que $g k \equiv a (mod n)$ . Un módulo raíz primitivo $n$ existe si y sólo 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 entero positivo. Si existe un módulo de raíz primitiva $n$ , entonces hay exactamente $φ (φ (n))$ tales raíces primitivas, donde $φ$ es la función totiente de Euler.
Residuo cuadrático : Un número entero $a$ es un módulo de residuo cuadrático $n$ , si existe un número entero $x$ tal que $x 2 \equiv a (mod n)$ . 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 sólo 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 $n$ de un número entero $a$ es el conjunto de todos los números enteros de la forma $a + kn$ , donde $k$ es cualquier número entero. Se llama clase de congruencia o clase de residuo de $un$ módulo $n$ , y puede denotarse como $mod n)$ , o como $a$ o $[a]$ cuando el módulo $n$ $se$ conoce por el contexto.

Cada módulo de clase de residuo $n$ contiene exactamente un número entero en el rango $0, ..., n - 1$ . Por tanto, estos $n$ 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 n)$ denota generalmente el entero único $k$ tal que $0 \leq k < n$ y $k \equiv a (mod n)$ ; se llama residuo de $un$ módulo $n$ .

En particular, $(a mod n) = (b mod n)$ es equivalente a $a \equiv b (mod n)$ , 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 $n$ 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 $n$ son incongruentes módulo $n$ . Además, cada número entero pertenece a uno y sólo un módulo de clase de residuo $n$ . ^[3]

El conjunto de números enteros ${0, 1, 2, ..., n - 1}$ se denomina sistema de residuos mínimos módulo $n$ . Cualquier conjunto de $n$ números enteros, de los cuales no hay dos que sean congruentes módulo $n$ , se denomina sistema de residuos completo módulo $n$ .

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 $n$ . ^[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:

${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 $φ (n)$ , cualquier conjunto de enteros $φ (n) que sean$ primos relativos con $n$ y mutuamente incongruentes bajo el módulo $n$ se denomina sistema de residuos reducido módulo $n$ . ^[5] El conjunto ${5, 15}$ de arriba, por ejemplo, es un ejemplo de un sistema de residuos reducido módulo 4.

Sistemas de cobertura

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

Módulo de números enteros n

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

Para $n > 0$ se tiene

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

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

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

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

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

{\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 se utiliza porque este anillo es el anillo cociente de por el ideal , el conjunto formado por todos $los kn$ con $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z}$ $n\mathbb {Z}$ $k\in \mathbb {Z} .$

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

El anillo de números enteros módulo $n$ es un campo si y sólo si $n$ es primo (esto asegura que cada elemento distinto de cero tenga un inverso multiplicativo ). Si $n = p k$ es una potencia prima con $k > 1$ , existe un campo finito único (hasta el isomorfismo) con $n$ elementos, que no es isomorfo tp , que no es un campo porque tiene divisores cero . $\mathrm {GF} (n)=\mathbb {F} _{n}$ $\mathbb {Z} /n\mathbb {Z}$

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

Extensión a números reales

Aplicaciones

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 Estándar Internacional 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 polinómico , á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 de números enteros 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.

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 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 $n$ , 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]

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 de no más de 63 bits, sin desbordamiento de las operaciones transitorias.

Un algoritmo para calcular $a \cdot b (mod m)$ : ^[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 yo ; si ( a >= m ) a %= m ; si ( b >= m ) b %= m ; para ( i = 0 ; i < 64 ; ++ i ) { d = ( d > mp2 ) ? ( re << 1 ) - m : re << 1 ; si ( a & 0x8000000000000000ULL ) d += b ; si ( d >= m ) d -= m ; un <<= 1 ; } devolver d ; }

En arquitecturas de computadora donde está disponible un formato de precisión extendida con al menos 64 bits de mantisa (como el tipo doble largo de la mayoría de los compiladores C x86), la siguiente rutina es más rápida que una solución que utiliza un bucle, al emplear el truco que, al hardware, la multiplicación de punto flotante da como resultado que se mantengan los bits más significativos del producto, mientras que la multiplicación de enteros da como resultado que se mantengan los bits menos significativos: ^{[ cita necesaria ]}

uint64_t mul_mod ( uint64_t a , uint64_t b , uint64_t m ) { long double x ; uint64_tc ; _ int64_tr ; _ si ( a >= m ) a %= m ; si ( b >= m ) b %= m ; x = un ; 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 C para realizar exponenciación modular, que utiliza la función $mul_mod$ implementada anteriormente.

Una forma algorítmica de calcular $a b (mod m)$ :

uint64_t pow_mod ( uint64_t a , uint64_t b , uint64_t m ) { uint64_t r = m == 1 ? 0 : 1 ; mientras ( b > 0 ) { si ( b & 1 ) r = mul_mod ( r , a , m ); segundo = segundo >> 1 ; a = mul_mod ( a , a , m ); } devolver r ; }

Sin embargo, para que todas las rutinas anteriores funcionen, $m$ no debe exceder los 63 bits.

Ver también

anillo booleano
búfer circular
División (matemáticas)
campo finito
símbolo de leyenda
exponenciación modular
Módulo (matemáticas)
Grupo multiplicativo de números enteros módulo n
Período Pisano (secuencias de Fibonacci módulo n )
Módulo raíz primitivo 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 detrás de la aritmética modular:
- grupo cíclico
- Grupo multiplicativo de números 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
- El lema de Thue

Notas

^ Sándor Lehoczky; Richard Rusczky (2006). David Patricio (ed.). el arte de resolver problemas . vol. 1 (7 ed.). AoPS incorporado. pag. 44.ISBN _ 0977304566.
^ Weisstein, Eric W. "Aritmética modular". mathworld.wolfram.com . Consultado el 12 de agosto de 2020 .
^ Pettofrezzo y Byrkit (1970, pág.90)
^ Largo (1972, pág.78)
^ Largo (1972, pág.85)
^ Es un anillo , como se muestra a continuación.
^ "2.3: Módulo n de números enteros". Matemáticas LibreTexts . 2013-11-16 . Consultado el 12 de agosto de 2020 .
^ Sengadir T., Matemáticas discretas y combinatoria , p. 293, en libros de Google
^ "Conjetura de la suma de potencias de Euler". rosettacode.org . Consultado el 11 de noviembre de 2020 .
^ Garey, señor; Johnson, DS (1979). Computadoras e intratabilidad, una guía para la teoría de la integridad NP . WH Freeman. ISBN 0716710447.
^ Este código utiliza la notación literal C para números hexadecimales largos y sin signo, que terminan en ULL. Consulte también la sección 6.4.4 de la especificación de lenguaje n1570.

Referencias

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, SEÑOR 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 discusiones sobre problemas de restos 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, reimpresión de una introducción (2001) Dover. ISBN 0-486-41449-3 .
Largo, Calvin T. (1972). Introducción elemental a la teoría de números (2ª ed.). Lexington: DC Heath y compañía . LCCN 77171950.
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elementos de la teoría de números . Acantilados de Englewood: Prentice Hall . ISBN 9780132683005. 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 la wiki de GIMPS
Aritmética modular y patrones en tablas de suma y multiplicación.