Aritmética modular

En matemática, la aritmética modular es un sistema aritmético para clases de equivalencia de números enteros llamadas clases de congruencia. La aritmética modular fue introducida en 1801 por Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae.^[1]​

Algunas veces se le llama, sugerentemente, aritmética del reloj, ya que los números «dan la vuelta» tras alcanzar cierto valor llamado módulo.^[2]​

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 n, ésta se define de la siguiente manera:^[3]​

a y b se encuentran en la misma "clase de congruencia" módulo n, si ambos dejan el mismo resto si los dividimos entre n, o, equivalentemente, si a − b es un múltiplo de n.

Esta relación se puede expresar cómodamente utilizando la notación de Gauss:^[3]​

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:^[3]​

«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 n, 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

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.^[4]​

La aritmética modular se basa en una relación de equivalencia, y las clases de equivalencia de un entero a se denota con [a]_n (o simplemente [a] si sobreentendemos el módulo.) Otras notaciones son por ejemplo a + nZ o a mod n. El conjunto de todas las clases de equivalencia se denota con Z/nZ = { [0]_n, [1]_n, [2]_n,..., [n-1]_n }.^[5]​

Esta relación de equivalencia tiene importantes propiedades que se siguen inmediatamente de la definición:^[5]​

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 Z/nZ mediante las fórmulas siguientes:^[5]​

De este modo, Z/nZ se convierte en un anillo con n elementos. Por ejemplo, en el anillo Z/12Z, se tiene :[8]₁₂[3]₁₂ + [6]₁₂ = [30]₁₂ = [6]₁₂.

El conjunto de enteros en Z/pZ forma un cuerpo finito si y sólo si p es primo.^[6]​

Si a y b son enteros, la congruencia: ax ≡ b (mod n) tiene solución x si y solo si el máximo común divisor (a, n) divide a b. 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.^[7]​

En el anillo de enteros, si consideramos la ecuación ax ≡ 1 (mod n), vemos que a tiene un inverso multiplicativo si y solo si a y n son coprimos. Por tanto, Z/nZ es un cuerpo si y sólo si n es un primo.^[8]​ Se puede probar que cada cuerpo finito es una extensión de Z/pZ para algún primo p.

Un hecho importante sobre aritmética modular, cuando los módulos son números primos es el pequeño teorema de Fermat: si p es un número primo, entonces:^[9]​

Si a es cualquier entero:

Si a es un entero no divisible entre p:

Esto fue generalizado por Euler: para todo entero positivo n y todo entero a relativamente primo a n, :a^φ(n) ≡ 1 (mod n), donde φ(n) denota función phi de Euler que cuenta el número de enteros entre 1 y n que sean coprimos con respecto a n.^[10]​ El teorema de Euler es una consecuencia del teorema de Lagrange, aplicado al caso del grupo de las unidades del anillo Z/nZ.

Dos enteros a, b son congruentes módulo n, escrito como:a ≡ b (mod n) si su diferencia a − b es divisible entre n, esto es, si a − b = kn para algún entero k.

Usando esta definición, podemos generalizar a módulos no enteros. Por ejemplo, podemos definir a ≡ b (mod 2π) si a − b = k2π para algún entero k. 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 factorial de un anillo módulo un ideal. Si R es un anillo conmutativo, e I es un ideal de R, entonces dos elementos a y b de R se dicen congruentes módulo I si a − b es un elemento de I. 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 R/I.

Sean a,b,c∈Z. Entonces

Es decir, la congruencia ≡ es una relación de equivalencia.

2. 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∈Z). Bajo esta consideración, n|(b−a); lo que implica b≡a (mod n).

3. Por hipótesis, se sabe que a≡b (mod n) y b≡c (mod n). Por lo tanto, existen únicos k,t∈Z 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).

Sean a,b,c,d,λ∈Z y n∈N tales que a≡b (mod n) y c≡d (mod n). Entonces

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

Sean a,b∈Z y n,k∈N, tales que a≡b (mod n). Entonces ak≡bk (mod n).

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∈N.

Sean a,b∈Z y m,n∈N. Si a≡b (mod n) y m|n entonces a≡b (mod m).

Sean a,b,c∈Z y n∈N. Si ac≡bc (mod n) y (c,n)=1, entonces a≡b (mod n).

Sean a,b,c∈Z y p∈N. Si ac≡bc (mod p) y p es primo tal que p∤ c, entonces a≡b (mod p).

Sean a,b,c∈Z, n∈N y (c,n)=d. Entonces ac≡bc (mod n) si y sólo si a≡b (mod nd).

Nuestra hipótesis es a≡b (mod nd). Por lo tanto, nd|(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).

Tú sabes que si a × b = 1, entonces b es el recíproco o inverso de a y también a es el inverso de b.

Sea n = (a_p . . . a₀)10 ∈ N en base 10. Entonces n = a_p10^p + a_p−110^p−1 + a_p−210^p−2 + · · · + a₂10² + a₁10 + a₀ y por tanto,

i) n ≡ a₀ (mod 2), luego n es divisible por 2 ⇔ a₀ lo es,

ii) n ≡ ${displaystyle sum _{i=0}^{p}}$ a_i (mod 3), luego n es divisible por 3 ⇔ ${displaystyle sum _{i=0}^{p}}$a_i lo es,

iii) n ≡ 10a₁+a₀ ≡ 2a₁+a₀ (mod 4), luego n es divisible por 4 ⇔ (a₁a₀)₁₀ lo es,

iv) n ≡ a₀ (mod 5), luego n es divisible por 5 ⇔ a₀ lo es,

v) n ≡ ${displaystyle sum _{i=0}^{p}}$ a_i (mod 9), luego n es divisible por 9 ⇔ ${displaystyle sum _{i=0}^{p}}$ a_i lo es,

vi) n ≡ ${displaystyle sum _{i=0}^{p}}$(−1)ⁱ a_i (mod 11), luego n es divisible por 11 ⇔ ${displaystyle sum _{i=0}^{p}}$(−1)ⁱ a_i

Las operaciones de suma y producto en Z se pueden trasladar a Zm puesto que son compatibles con la estructura de este último conjunto.

Sean n ∈ N y a, b, c, d ∈ Z tales que a ≡ b (mod m) y c ≡ d (mod m). Entonces

i) a + c ≡ b + d (mod m),

ii) ac ≡ bd (mod m).

Sean a,b∈Z; no nulos y n∈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.

Sean a,b∈Z no nulos y n∈N. La ecuación ax≡b (mod n), 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).

Sean a,b∈Z no nulos, n∈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).

Sean a,b∈Z y n,d∈N. Si ad≡bd (mod nd), entonces a≡b (mod n).

Sean a,b∈Z y n,d∈N tales que (n,d)=1. Si ad≡bd (mod n), entonces 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.

Sean a,b∈Z no nulos, n∈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).

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

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 {m₁, m₂, . . . , m_k } de números primos entre sí (esto es mcd(m_i, m_j) = 1 para todo i != j). Entonces cualquier número positivo S menor que m = m₁m₂ · · · m_k se puede expresar mediante una n-upla (r₁,r₂, . . . ,r_k ) (con 0 ≤ r_i < m_i para todo i ∈ {1, 2, . . . , k}) donde

${displaystyle {displaystyle {egin{cases}xequiv r_{1}mod(m_{1})\.\.\.\xequiv r_{k}mod(m_{k})end{cases}}}}$

Ademas, por el teorema del resto chino existe un único x ∈ {0, 1, 2, . . . , m} satisfaciendo estas condiciones. Además, si

${displaystyle {displaystyle {egin{cases}xequiv r_{1}mod(m_{1})\.\.\.\xequiv r_{k}mod(m_{k})end{cases}}}y{displaystyle {egin{cases}x'equiv r'_{1}mod(m_{1})\.\.\.\x'equiv r'_{k}mod(m_{k})end{cases}}}}$

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 (r₁,r₂, . . . ,r_k ) y(r'₁,r'₂, . . . ,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 Z_m) de los sistemas anteriores.

Por ejemplo se pueden considerar m₁ = 99, m₂ = 98, m₃ = 97 y m₄ = 95 para trabajar con números menores o iguales que m = m₁m₂m₃m₄ = 89403930.

Otros enteros que pueden escogerse son los de la forma 2^k − 1 con k ∈ N puesto que es relativamente fácil encontrar conjuntos de estos enteros primos entre sí

(mcd(2^a − 1, 2^b −1) = 2^mcd(a,b) − 1). Además con estos enteros es fácil trabajar en base 2. Por ejemplo, 2³⁵ − 1, 2³⁴ − 1, 2³³ − 1,2³¹ −1, 2²⁹ −1 y 2²³ −1 son primos entre sí y el producto de ellos es mayor que 2¹⁸⁴.

Ejemplo: Si tomamos m₁ = 3, m₂ = 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) 11 = (2, 3) y 5 + 6 ≡ (2, 1) + (0, 2) = (2, 3) ≡ 11.

Por otra parte y 2 · 3 ≡ (2, 2) · (0, 3) = (0, 6) ≡ (0, 2) ≡ 6. Sin embargo 5 · 6 no es calculable, puesto que el resultado es mayor o igual que 12.

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.

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 2^b (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 2³² en la mayoría de las computadoras.

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

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

---