Números coprimos

Esta definición también se puede extender a un conjunto de números, siendo estos coprimos dos a dos.

Aritmética modular

Los números enteros se pueden representar en la recta real:

Pero si tomamos una estructura como la siguiente:

Los números regresan al 0 cuando se llega a un valor en concreto, llamado módulo. Por este motivo, algunas veces también se le llama aritmética del reloj. Veamos un reloj como ejemplo, que es de módulo 12. Si son las 10 y pasan 4 horas, podemos decir que son las 2, porque $14 \text{ mod } 12 = 2$.

Por tanto, la aritmética modular consiste en encontrar el resto.

Además, también se pueden tomar números negativos:

Esta es la definición intuitiva. A continuación de describe la notación y algunos teoremas fundamentales.

Teoremas fundamentales y propiedades de la aritmética modular

La aritmética modular fue introducida en 1801 por Carl Friedrich Gauss¹, y consiste en una relación de equivalencia llamada congruencia. Esta es la notación que utilizó Gauss:

$a \equiv b \pmod{m}$ se lee como $a$ y $b$ son congruentes módulo $m$, lo que quiere decir que su resta es un múltiplo de $m$.

Otra notación puede ser $[a]_m = [b]_m$.

Alternativamente, la congruencia se da cuando los restos de dividir entre $m$ son iguales.

La congruencia es una relación de equivalencia, por lo que sigue funcionando lo de sumar y multiplicar por ambos lados valores congruentes. Esto quiere decir que es compatible con las operaciones del anillo de enteros (suma y multiplicación).

Y este corolario resulta particularmente interesante cuando se trabaja con enteros grandes en módulos pequeños, porque en lugar de sumar dichas cantidades, se pueden sumar los restos, que serán cantidades más pequeñas.

Tipos de números en aritmética modular

Un problema de la aritmética modular es el producto de dos enteros no nulos, puede ser 0 (si el resultado es múltiplo del módulo). Por este motivo, la resolución de ecuaciones se complica.

Por este motivo, es importante distingir los casos donde se puede dar esta situación.

• Divisores de 0: $\exists \, b \, / \, ab \equiv 0 \pmod{m}$.
• Unidades en $\Z_{/m\Z}$: $\exists \, b \, / \, ab \equiv 1 \pmod{m}$.
  • $a$ es una unidad si y solo si $\gcd(a, m) = 1$, es decir, $a$ y $m$ son coprimos.
  • Caso particular: si $m$ es primo, entonces todos son unidades.

Donde $a$ y $b$ son enteros no nulos.

Resolución de congruencias lineales

En los números enteros, la ecuación lineal de una variable $ax = b$ tiene solución si solo si $a \, | \, b$.

En $\Z_{/m\Z}$, una ecuación lineal es de la forma $ax \equiv b \pmod{m}$ y se puede resolver con el siguiente algoritmo:

1. Calcula $\gcd(a, m) = d$.
2. Si $d$ no divide a $b$, entonces no hay soluciones.
3. Si $d \, | \, b$ podemos distinguir dos casos:

   • Si $d = 1$, es decir, si $a$ y $m$ con coprimos:

     1. Calcular los coeficientes $s$ y $t$ de Bézout.
     2. $\gcd(a, m) = d = 1 \equiv sa + \xcancel{tm} \equiv sa \pmod{m}$.
     3. $sa \equiv 1 \implies asx \equiv bs \implies x \equiv bs \pmod{m}$
     4. La solución es $x \equiv bs \pmod{m}$ y es única.

   • Si $d \not= 1$: Resolver como en el caso anterior: $\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}}$, dado que $\gcd(\frac{a}{d}, \frac{m}{d}) = 1$.

$$ \gcd(a, m) := d \implies \begin{cases} d \not | \,\, b \implies \textbf{No hay soluciones} \\ d \, | \, b \implies \begin{cases} d = 1 \implies 1 \equiv sa + \xcancel{tm} \equiv sa \pmod{m} \implies x \equiv bs \pmod{m} \textbf{ Solución única} \\ d \ne 1 \implies \frac{a}{d} x \equiv \frac{b}{d} \pmod{\frac{m}{d}} \implies \gcd(\frac{a}{d}, \frac{m}{d}) = 1 = s\frac{a}{d} + \xcancel{t\frac{m}{d}} \equiv s\frac{a}{d} \pmod{\frac{m}{d}} \implies \textbf{$d$ soluciones de la forma: } x_0 + k\frac{m}{d}, k \in [0, d) \end{cases} \\ \end{cases} $$

Función $\Phi$ de Euler

Esta función permite conocer cuantas unidades hay en $\Z_{/m\Z}$, o cuantos números tienen inverso multiplicativo.

Pequeño teorema de Fermat

Extensión: Teorema de Euler

Teorema chino de los restos

Con este teorema se pueden resolver sistemas de congruencias lineales.

Exponenciación modular

Por ejemplo, para el criptosistema RSA es necesario realizar potencias con números grandes en aritmética modular, por ejemplo $b^e \text{ mod } n$.

Utilizando la representación de enteros, se puede obtener lo siguiente:

$$ e = \sum_{i = 0}^{k} e_i 2^i = e_0 + e_1 2 + e_2 2^2 + \ldots + e_k 2^k $$

Y aplicando propiedades de las potencias:

$$ \begin{align*} b^e &= b^e_0 \; b^{e_1 2} \; b^{e_2 2^2} \ldots \; b^{e_k 2^k} = b^{2^0} \\ &= (b^{2^0})^{e_0} \; (b^{2^1})^{e_1} \ldots \; (b^{2^k})^{e_k} \end{align*} $$

Por lo que finalmente se puede obtener el siguiente algoritmo:

1def mod_exp(b, e, m):
2    exp = b
3    for bit in e.bits():
4        if bit == 1:
5            exp *= exp
6            exp %= m
7    return exp

Lo que resulta bastante más eficiente que calcular la potencia y después el módulo.

Curiosidades

Aunque este video se centra en otros números, guarda bastante relación, y además, hay una buena explicación sobre la aritmética modular en el 15:52.