Teoría de números y aritmética modular

Para qué sirve esto

Si son las $10$ de la noche, ¿qué hora será dentro de $5$ horas? No dices "las $15$ ": dices "las $3$ ". Sin darte cuenta, has hecho aritmética modular: sumar y quedarte solo con el resto al dar la vuelta del reloj ( $15 \bmod 12 = 3$ ).

Esta aritmética "circular" está detrás de:

El calendario: ¿qué día de la semana será dentro de $100$ días? (módulo $7$ ).
Los dígitos de control: la letra del DNI, el último dígito de un ISBN o de una tarjeta.
La criptografía: RSA, la que protege tus pagos y contraseñas, usa aritmética modular con números gigantes.
La informática: tablas hash, generadores de números aleatorios.

Necesitas: divisibilidad y mcd/mcm (N0), ecuaciones (N2).

Divisibilidad y resto

Congruencias

Aritmética con restos

Lo mejor de las congruencias: se puede sumar, restar y multiplicar trabajando con los restos, reduciendo en cualquier momento: $a \equiv a',\ b \equiv b' \pmod n \ \Rightarrow\ a + b \equiv a' + b',\quad a\,b \equiv a'\,b' \pmod n$

Potencias módulo n

Para calcular $a^k \bmod n$ con $k$ grande, se buscan las potencias sucesivas hasta que se repitan.

Es un atajo enorme: $2^{10} \equiv 1 \pmod{11}$ , luego $2^{100} = (2^{10})^{10} \equiv 1 \pmod{11}$ .

El algoritmo de Euclides

Halla el máximo común divisor por divisiones sucesivas: $\gcd(a, b) = \gcd(b,\ a \bmod b)$ , hasta que el resto sea $0$ ; el último resto no nulo es el mcd.

Identidad de Bézout: existen enteros $x, y$ con $a\,x + b\,y = \gcd(a, b)$ . Se hallan deshaciendo el algoritmo de Euclides.

Inversos y congruencias lineales

Cómo hallarlo: con Euclides/Bézout, o probando con $n$ pequeño. Ejemplo: el inverso de $3$ módulo $7$ es $5$ , porque $3\cdot 5 = 15 \equiv 1$ .

El teorema chino del resto

Aplicaciones

Días de la semana: dentro de $100$ días, si hoy es lunes: $100 \bmod 7 = 2$ , luego será miércoles.
Letra del DNI: se divide el número entre $23$ y el resto indica la letra.
Criptografía RSA: se basa en que multiplicar dos primos enormes es fácil, pero factorizar el resultado es prácticamente imposible; el cifrado y descifrado usan potencias e inversos módulo $n$ .

Errores típicos

En resumen

$a = bq + r$ , $0 \leq r < b$ ; $a \bmod b = r$ .
$a \equiv b \pmod n \iff n \mid a - b \iff$ mismo resto. Se puede sumar y multiplicar reduciendo.
Potencias: ciclos; Fermat: $a^{p-1} \equiv 1 \pmod p$ ( $p$ primo, $p \nmid a$ ).
Euclides: $\gcd(a, b) = \gcd(b, a \bmod b)$ ; Bézout: $ax + by = \gcd$ .
Inverso de $a$ mod $n$ existe $\iff \gcd(a, n) = 1$ ; $ax \equiv b \Rightarrow x \equiv a^{-1}b$ .
Teorema chino: módulos primos entre sí $\Rightarrow$ solución única módulo el producto.