Aritmética modular
![]() | Se ha sugerido que «Congruencia (teoría de números)» sea fusionado en este artículo o sección. Motivo: los argumentos están expuestos en la página de discusión. Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. Este aviso fue puesto el 14 de marzo de 2017. |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e3/Disqvisitiones-800.jpg/220px-Disqvisitiones-800.jpg)
En matemática, precisamente en teoría de números; la aritmética modular es un conjunto de métodos que permiten la resolución de problemas sobre números enteros. Estos métodos derivan del estudio del resto obtenido mediante una división euclídea. Fue introducida en 1801 por Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae.[1]
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 la hora es a las 7:00, entonces 8 horas más tarde serán las 3:00. La adición simple daría como resultado 7 + 8 = 15, pero a las 15:00 se lee como 3:00 en la esfera del reloj porque los relojes "se envuelven" 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 , de modo que . Del mismo modo, las 8:00 representa un período de 8 horas, y el doble de esto daría 16:00, que se lee como 4:00 en la esfera del reloj, escrito como .
Relación de congruencia
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Clock_group.svg/220px-Clock_group.svg.png)
La aritmética modular puede ser construida matemáticamente mediante la relación de congruencia entre enteros, que es compatible con las operaciones en el anillo de enteros: suma y multiplicación. Para un determinado módulo , ésta se define de la siguiente manera:[2]
|
Esta relación se puede expresar cómodamente utilizando la notación de Gauss:[2]
Así se tiene por ejemplo:
ya que ambos, 63 y 83 dejan el mismo resto (3) al dividir entre 10, o, equivalentemente, 63 − 83 es un múltiplo de 10. Se lee:[2]
«63 es congruente con 83, módulo 10», «en módulo 10, 63 y 83 son congruentes», o «63 y 83 son congruentes uno con otro, módulo 10».
«Módulo» a veces se abrevia con la palabra «mod» al hablar, de la misma manera que como está escrito y proviene de la palabra modulus del latín, la lengua de los escritos originales de Gauss. Así, el número , que en este ejemplo es 10, sería el modulus.
Otro ejemplo; cuando el módulo es 12, entonces cualesquiera dos números que divididos entre doce den el mismo resto son equivalentes (o "congruentes") uno con otro. Los números:
..., −34, −22, −10, 2, 14, 26,...
son todos "congruentes módulo 12" unos con otros, ya que cada uno deja el mismo resto (2) cuando los dividimos entre 12. La colección de todos esos números es una clase de congruencia.[3]
Propiedades principales
Clases de equivalencia módulo n
La aritmética modular se basa en una relación de equivalencia, y las clases de equivalencia de un entero se denota con (o simplemente si sobreentendemos el módulo.) Otras notaciones son por ejemplo o . El conjunto de todas las clases de equivalencia se denota con .[4]
Esta relación de equivalencia tiene importantes propiedades que se siguen inmediatamente de la definición:[4]
Si
y
entonces
y
Lo que muestra que la suma y la multiplicación son operaciones bien definidas sobre el conjunto de las clases de equivalencia. En otras palabras, la suma y la multiplicación están definidas sobre mediante las fórmulas siguientes:[4]
De este modo, se convierte en un anillo con elementos. Por ejemplo, en el anillo , se tiene:
El conjunto de enteros en forma un cuerpo finito si, y sólo si, es primo.[5]
Resolución de congruencias
Si y son enteros, la congruencia: tiene solución si, y sólo si, el máximo común divisor de divide a . Los detalles están recogidos en el teorema de congruencia lineal. Sistemas de congruencias más complicados con módulos diferentes se pueden resolver usando el teorema chino del resto o el método de sustitución sucesiva.[6]
En el anillo de enteros, si consideramos la ecuación , vemos que tiene un inverso multiplicativo si, y sólo si, y son coprimos (primos relativos). Por tanto, es un cuerpo si, y sólo si, es un primo.[7] Se puede probar que cada cuerpo finito es una extensión de para algún primo .
Pequeño teorema de Fermat y teorema de Euler
Un hecho importante sobre aritmética modular, cuando los módulos son números primos es el pequeño teorema de Fermat: si es un número primo, entonces:[8]
Si es un número natural:
Si es un número natural no divisible por :
Esto fue generalizado por Euler:
(Para todo entero positivo y todo entero relativamente primo a ):
donde denota función phi de Euler que cuenta el número de enteros entre 1 y que sean coprimos con respecto a .[9] El teorema de Euler es una consecuencia del teorema de Lagrange, aplicado al caso del grupo de las unidades del anillo .
Generalizaciones
Dos enteros , son congruentes módulo , escrito como: si su diferencia es divisible entre , esto es, si para algún entero .
Usando esta definición, podemos generalizar a módulos no enteros. Por ejemplo, podemos definir , si , para algún entero . Esta idea se desarrolla plenamente en el contexto de la teoría de los anillos y funciones trigonométricas.
En Álgebra abstracta se ve que la aritmética modular es un caso especial del proceso de crear un anillo cociente de un anillo módulo un ideal. Si es un anillo conmutativo, e es un ideal de , entonces dos elementos y de se dicen congruentes módulo si es un elemento de . Como pasaba con el anillo de enteros, esto se convierte en una relación de equivalencia, y la suma y la multiplicación se convierten en operaciones bien definidas sobre el anillo factorial .
Proposiciones básicas
Proposición 1
Sean . Entonces se cumplen las siguientes propiedades:
- Reflexividad:
- Simetría: Si , entonces .
- Transitividad: Si y , entonces .
Es decir, la congruencia () es una relación de equivalencia.
Demostración |
Se sabe que n|0 y 0=a−a. Por lo tanto; n|(a−a), que implica a≡a (mod n). Por hipótesis, se sabe que a≡b (mod n). Esto implica que n|(a−b). Por otro lado, si n|y entonces n|(−y) (con y∈ℤ). Bajo esta consideración, n|(b−a); lo que implica b≡a (mod n). Por hipótesis, se sabe que a≡b (mod n) y b≡c (mod n). Por lo tanto, existen únicos k,t∈ℤ tales que nk=a−b y nt=b−c. Sumando estas dos igualdades, se obtiene n(k+t)=a−c. Esto implica a≡c (mod n). |
Proposición 2.
Sean a,b,c,d,λ∈ℤ y n∈ℕ tales que a≡b (mod n) y c≡d (mod n). Entonces
- λa≡λb (mod n).
- a+c≡b+d (mod n).
- ac≡bd (mod n).
Demostración |
Como a≡b (mod n) y c≡d (mod n), entonces existen únicos k,t∈ℤ tales que nk=a−b y nt=c−d. Como nk=a−b, podemos multiplicar por λ (entero). Así, n(λk)=λa−λb. Esto implica λa≡λb (mod n). Por otro lado, sumando nk=a−b y nt=c−d, se obtiene n(k+t)=(a+c)−(b+d). Esto implica a+c≡b+d (mod n). Multiplicando por c, la expresión nk=a−b; se consigue nkc=ac−bc. Si se multiplica por b, la expresión nt=c−d; se consigue ntb=cb−db. Al sumar estas cantidades, se logra n(kc+tb)=ac−bd. Esto implica ac≡bd (mod n). |
Proposición 3.
Sean a,b∈ℤ y n,k∈ℕ, tales que a≡b (mod n). Entonces ak≡bk (mod n).
Demostración |
La demostración de esta proposición se realizará por Inducción. Considere la función proposicional p(k):ak≡bk (mod n), con k,n∈ℕ y a,b∈ℤ. p(1) es verdadero; pues por hipótesis, a≡b (mod n). Considere la hipótesis de inducción p(k):ak≡bk (mod n). Por demostrar p(k+1):a(k+1)≡b(k+1) (mod n) es verdadero. En efecto, a(k+1)≡ak⋅a≡bk⋅a≡bk⋅b≡b(k+1) (mod n), por hipótesis de inducción y transitividad de la congruencia. Por lo tanto, p(k)⇒p(k+1). Por principio de inducción, se verifica que si a≡b (mod n) entonces ak≡bk (mod n) para todo k∈ℕ. |
Proposición 4.
Sean a,b∈ℤ y m,n∈ℕ. Si a≡b (mod n) y m|n entonces a≡b (mod m).
Demostración |
Por hipótesis, se sabe que m|n. Además, a≡b (mod n) implica n|(a−b). Por transitividad de la divisibilidad (si a|b y b|c entonces a|c), se concluye que m|(a−b). Por lo tanto, a≡b (mod m). |
Proposición 5.
Sean a,b,c∈ℤ y n∈ℕ. Si ac≡bc (mod n) y (c,n)=1, entonces a≡b (mod n).
Demostración |
Como ac≡bc (mod n), entonces n|c(a−b). Adicionalmente, (c,n)=1 (es decir, n∤c) entonces n|(a−b). Por lo tanto, a≡b (mod n). |
Proposición 6.
Sean a,b,c∈ℤ y p∈ℕ. Si ac≡bc (mod p) y p es primo tal que p∤c, entonces a≡b (mod p).
Demostración |
Como ac≡bc (mod p), entonces p|c(a−b). Como p es primo, por el Lema de Euclides; p|c ∨ p|(a-b). Sin embargo; p∤c, por lo que p|(a−b). Esto implica que a≡b (mod p). |
Proposición 7.
Sean a,b,c∈ℤ, n∈ℕ y (c,n)=d. Entonces ac≡bc (mod n) si y sólo si a≡b (mod n/d).
Demostración |
Se supondrá que ac≡bc (mod n). Por lo tanto, n|c(a−b). Por propiedad de divisibilidad, n/d|(c/d)(a−b). Note que n/d,c/d∈ℤ, pues (c,n)=d implica (c/d,n/d)=1. De esto último, se consigue que n/d∤c/d. Por lo tanto, n/d|(a−b). Entonces a≡b (mod n/d). Nuestra hipótesis es a≡b (mod n/d). Por lo tanto, n/d|(a−b). Por propiedad de divisibilidad, n|d(a−b). Adicionalmente, ya que (c,n)=d entonces d|c. Esto implica que d(a−b)|c(a−b). Por transitividad de la divisibilidad, n|c(a−b). Por lo tanto, ac≡bc (mod n). |
División
Se sabe que si , entonces es el recíproco o inverso de y también es el inverso de .
- Por ejemplo, inverso de a = 4 es b = 0.25 porque 4 · 0.25 = 1. El inverso del entero 4 es el decimal (racional) 0.25.
- Esta es una anomalía que no queremos en ℤn. Quisíeramos que en ℤn los inversos de los elementos de ℤn estén en ℤn, como sucede con los negativos. Pero esto no siempre sucede. Por ejemplo en ℤ9 = {0, ..., 8}, ningún elemento es inverso de 3, porque ningún número multiplicado por 3 daría 1. Tendría que dar 10, para que al tomarlo módulo 9, dé 1, y ese entero no existe. Sin embargo 2 · 5 = 1. lo que revela que el 5 es el inverso del 2 y, simétricamente, el 2 es el inverso de 5. Podemos afirmar que en ℤ9, el 2 es invertible, es decir tiene inverso y su inverso es 2−1 = 5. Observa la notación: el inverso de a es a−1. Contar con inversos es importante porque nos permiten hacer divisiones y resolver ecuaciones. En efecto, la división a / b la entendemos como a · b−1, es decir multiplicamos a por el inverso del divisor b.
Teorema (Criterios de divisibilidad)
Sea en base 10. Entonces y por tanto,
- , luego es divisible entre 2 si y solo si lo es.
- , luego es divisible entre 3 si y solo si lo es.
- , luego es divisible entre 4 si y solo si lo es.
- , luego es divisible entre 5 si y solo si lo es.
- , luego es divisible entre 9 si y solo si lo es.
- , luego es divisible entre 11 si y solo si
Multiplicación
Las operaciones de suma y producto en ℤ se pueden trasladar a ℤm puesto que son compatibles con la estructura de este último conjunto.
Teorema
Sean m ∈ ℕ y a, b, c, d ∈ ℤ tales que a ≡ b (mod m) y c ≡ d (mod m). Entonces
i) a + c ≡ b + d (mod m),
ii) ac ≡ bd (mod m).
Demostración |
Supongamos que a ≡ b (mod m) y c ≡ d (mod m). Entonces a = b+k1m y c = d +k2m con k1, k2 ∈ ℤ y por tanto (a+c) = (b+d)+(k1+k2)m con k1 +k2 ∈ ℤ y ac = bd + (bk2 +ck1 +k1k2m)m con bk2 +ck1 +k1k2 ∈ ℤ |
Ecuaciones lineales de congruencia
Definición 1
Sean a,b∈ℤ; no nulos y n∈ℕ. Se denomina ecuación lineal de congruencia a la expresión ax≡b (mod n). El número entero x: corresponde a la solución de la ecuación.
Las soluciones de una Ecuación Lineal de Congruencia deben ser números enteros. ¿Existe algún criterio para determinar cuando una Ecuación Lineal de Congruencia tiene soluciones enteras? La respuesta es afirmativa.
Definición 2
Sean a,b∈ℤ no nulos y n∈ℕ. La ecuación ax≡b (mod n), tiene solución si y sólo si (a,n)|b.
Demostración |
La ecuación tiene solución si y sólo si n|(ax−b). Es decir, si existe un único entero y tal que ny=ax−b. Reordenando, se logra b=ax+nt con t=−y. Por una de las propiedades de la diofántica, la ecuación diofántica ax+nt=b tiene solución si y sólo si (a,n)|b. |
Sin embargo (y nuevamente, al igual que en las ecuaciones diofánticas lineales), una ecuación lineal de congruencia puede poseer más de una solución. Por lo tanto, consideremos el siguiente resultado (Definición 3).
Definición 3
Sean a,b∈ℤ no nulos, n∈ℕ, (a,n)=d y d|b. Entonces la congruencia ax≡b (mod n) tiene d soluciones. Adicionalmente x≡x0+ntd (mod n), es el conjunto solución de la ecuación, con t={1,2,3,...,d−1} y x0 es una solución particular de ax≡b (mod n). Los siguientes resultados permitirán resolver de manera más expedita una Ecuación Lineal de Congruencia (Definición 4 y 5).
Definición 4
Sean a,b∈ℤ y n,d∈ℕ. Si ad≡bd (mod nd), entonces a≡b (mod n).
Demostración |
Por definición, existe un único entero t tal que ndt=d(a−b). Reordenando y factorizando, se logra d[nt−(a−b)]=0. Como d≠0 y ℤ no tiene divisores de cero, entonces nt−(a−b)=0. Así, nt=a−b; por lo que a≡b (mod n). |
Definición 5
Sean a,b∈ℤ y n,d∈ℕ tales que (n,d)=1. Si ad≡bd (mod n), entonces a≡b (mod n).
Demostración |
Por definición, n|d(a−b). Como (n,d)=1, entonces n∤d. Por lo tanto, n|(a−b). Así, a≡b (mod n). |
¿Es posible relacionar la función φ de Euler con las ecuaciones lineales de congruencia? La Definición 6 tiene la respuesta.
Definición 6
Sean a,b∈ℤ no nulos, n∈ℕ y (a,n)=1. Entonces la única solución a la ecuación ax≡b (mod n) es x≡aφ(n)−1⋅b (mod n).
Demostración |
Por definición 3., la ecuación tiene solución única. Por consiguiente, basta probar que x≡aφ(n)−1⋅b (mod n) es solución. Sin embargo, esto es inmediato; pues a(aφ(n)−1⋅b)≡aφ(n)⋅b≡b (mod n), ya que (a,n)=1, por lo que el Teorema de Euler - Fermat establece que aφ(n)≡1 (mod n). |
Aritmética con números grandes
Casi todos los procesadores trabajan mucho más rápido con números pequeños que con números grandes. Este problema puede resolverse utilizando congruencias. Para ello consideramos un conjunto {m1, m2, . . . , mk } de números primos entre sí (esto es mcd(mi, mj) = 1 para todo i != j). Entonces cualquier número positivo S menor que m = m1m2 · · · mk se puede expresar mediante una n-tupla (r1,r2, . . . ,rk ) (con 0 ≤ ri < mi para todo i ∈ {1, 2, . . . , k}) donde
Además, por el teorema chino del resto existe un único x ∈ {0, 1, 2, . . . , m} satisfaciendo estas condiciones. Además, si
Por tanto, las operaciones aritméticas se pueden realizar entre las r-uplas – cuyas coordenadas son todas menores o iguales que max1≤i≤r mi –, pudiéndose realizar estas operaciones en paralelo. Esto es, para sumar n y n' se suman los vectores asociados (r1,r2, . . . ,rk ) y(r'1,r'2, . . . ,r'k ) y para multiplicar n y n' se multiplican escalarmente los vectores asociados.
Finalmente x + x' y xx' serán las soluciones (únicas en ℤm) de los sistemas anteriores.
Por ejemplo se pueden considerar m1 = 99, m2 = 98, m3 = 97 y m4 = 95 para trabajar con números menores o iguales que m = m1m2m3m4 = 89403930.
Otros enteros que pueden escogerse son los de la forma 2k − 1 con k ∈ ℕ puesto que es relativamente fácil encontrar conjuntos de estos enteros primos entre sí
(mcd(2a − 1, 2b −1) = 2mcd(a,b) − 1). Además con estos enteros es fácil trabajar en base 2. Por ejemplo, 235 − 1, 234 − 1, 233 − 1,231 −1, 229 −1 y 223 −1 son primos entre sí y el producto de ellos es mayor que 2184.
Ejemplo: Si tomamos m1 = 3, m2 = 4 se tiene que 0 = (0, 0), 1 = (1, 1), 2 = (2, 2), 3 = (0, 3), 4 = (1, 0), 5 = (2, 1), 6 = (0, 2), 7 = (1, 3), 8 = (2, 0), 9 = (0, 1), 10 = (1, 2) y 11 = (2, 3). Sendos ejemplos de suma y producto son: 5 + 6 ≡ (2, 1) + (0, 2) = (2, 3) ≡ 11 y 2 · 3 ≡ (2, 2) · (0, 3) = (0, 6) ≡ (0, 2) ≡ 6. Sin embargo 5 · 6 no se puede calcular mediante este procedimiento, puesto que el resultado 5 · 6 es mayor o igual que 12.
Aplicaciones de la aritmética modular
La aritmética modular, estudiada sistemáticamente en primer lugar por Carl Friedrich Gauss al final del siglo XVIII, se aplica en teoría de números, álgebra abstracta, criptografía, y en artes visuales y musicales.
En informática
Las operaciones aritméticas que hoy en día hacen la mayoría de las computadoras son aritmético modulares, donde el módulo es 2b (b es el número de bits de los valores sobre los que operamos). Esto se ve claro en la compilación de lenguajes de programación como el C; donde por ejemplo todas las operaciones aritméticas sobre "int", enteros, se toman módulo 232 en la mayoría de las computadoras.
En criptografía
La aritmética modular es una herramienta poderosa en criptografía. Permite la creación de sistemas de cifrado robustos como RSA, protegiendo la información y facilitando las comunicaciones seguras en el mundo digital.
En el arte
En música, debido a la equivalencia de octavas y equivalencia enarmónica (esto es, los pasos en razones de 1/2 o 2/1 son equivalentes, y Do# es lo mismo que Reb), la aritmética modular se usa cuando consideramos la escala de doce tonos igualmente temperada, especialmente en el dodecafonismo. En artes visuales esta aritmética puede usarse para crear patrones artísticos basados en las tablas de multiplicación módulo n (ver enlace abajo).
Véase también
- Residuo cuadrático
- Teorema chino del resto
- Teoría de números
- Números primos
- Clase de equivalencia potencial
- Pequeño teorema de Fermat
- Teorema de Euler
- Criterio de Euler
- Teorema de Lagrange (teoría de grupos)
- Aritmética de saturación
- Operación módulo
- Resto
- Teorema de congruencia lineal
- Principio de inducción
- Reflexividad
- Simetría
- Transitividad
- Ecuación diofántica
Referencias
- ↑ «Cap.1 Numbers congruences in general». Disquisitiones Arithmeticae. Yale University Press. 1965. ISBN 0-300-09473-6. . (Traducción al español) Archivado el 25 de noviembre de 2011 en Wayback Machine.
- ↑ a b c Gauss, Carl Friedrich (1965). «Sec.I art.1-3». Disquisitiones Arithmeticae. Yale University Press. ISBN 0-300-09473-6. . (Traducción al español) Archivado el 25 de noviembre de 2011 en Wayback Machine.
- ↑ Hortalá, María Teresa; Rodríguez, Mario; Leach, Javier (2001). Matemática discreta y lógica matemática. Madrid: Complutense S.A. p. 67. ISBN 84-7491-650-X.
- ↑ a b c Carmona Collado, Luis Miguel. «Congruencias» (HTML). Introducción a la aritmética entera y modular. Universidad politécnica de Madrid. Consultado el 19 de abril de 2011.
- ↑ Kostrikin: Introducción al álgebra, Mir, Moscú (1974)
- ↑ Santiago Zaragoza, Antonio Cipriano (2009). «2.4. Congruencias lineales». Teoría de números (1ª edición). Madrid: Visión libros. pp. 22-25. ISBN 978-84-9886-360-4.
|fechaacceso=
requiere|url=
(ayuda) - ↑
|fechaacceso=
requiere|url=
(ayuda) - ↑ Gauss, Carl Friedrich (1965). «Sec III, art. 50». Disquisitiones Arithmeticae. Yale University Press. ISBN 0-300-09473-6. . (Traducción al español) Archivado el 20 de septiembre de 2008 en Wayback Machine.
- ↑ Euler, Leonhard « Theoremata circa residua ex divisione potestatum relicta », en Novi Comment. acad. sc. Petrop., vol. 7, 1761, p. 49-82. Texto original del latín Dartmouth College (Euler archive) con número E262. Traducción al inglés : arΧiv:math/0608467
Enlaces externos
- Weisstein, Eric W. «Modular arithmetic». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- Perl arithmetic enhancements - explica las razones que se encuentran tras el operador de Perl %
Bibliografía
- http://www.matematicas.ciencias.uchile.cl/juaco/section-10.html
- http://serbal.pntic.mec.es/jpem0100/cesar/01.html
- https://www.cartagena99.com/recursos/alumnos/apuntes/Tema3%20Aritmetica%20Modular.pdf
Datos: Q319400
Multimedia: Modular arithmetic / Q319400