Lección 3.3: Residuos y clases de residuos — Espinoza Olimpiadas

Sistema completo de residuos

Un **sistema completo de residuos módulo $m$ ** es un conjunto de $m$ enteros, uno por cada clase de residuo. El más natural es $\{0, 1, 2, \ldots, m-1\}$ , pero también $\{1, 2, \ldots, m\}$ o cualquier conjunto de $m$ enteros no congruentes entre sí módulo $m$ .

Propiedad clave: si $\{r_1, r_2, \ldots, r_m\}$ es un sistema completo de residuos módulo $m$ y $\gcd(a, m) = 1$ , entonces $\{ar_1, ar_2, \ldots, ar_m\}$ también es un sistema completo de residuos. Esto se debe a que multiplicar por $a$ (coprimo con $m$ ) permuta las clases de residuos. Esta propiedad será fundamental cuando estudiemos el Teorema de Euler.

La suma de todos los elementos de $\{0, 1, \ldots, m-1\}$ es $m(m-1)/2$ . Para $m$ impar esto es divisible por $m$ , y para $m$ par lo es por $m/2$ .

\{0, 1, 2, \ldots, m-1\} \text{ es un sistema completo de residuos módulo } m

Residuos invertibles y la función de Euler

Un residuo $a$ tiene inverso multiplicativo módulo $m$ si existe $b$ con $ab \equiv 1 \pmod m$ . Por la identidad de Bézout, esto ocurre exactamente cuando $\gcd(a, m) = 1$ . Los residuos con inverso se llaman invertibles o unidades módulo $m$ .

La función de Euler $\phi(m)$ cuenta cuántos enteros en $\{1, 2, \ldots, m\}$ son coprimos con $m$ , es decir, cuántas clases de residuos tienen inverso. Para $m = p$ primo, todos los residuos $1, 2, \ldots, p-1$ son invertibles, así que $\phi(p) = p - 1$ .

Para $m = p^k$ con $p$ primo: $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$ , pues los únicos no invertibles son los múltiplos de $p$ en $\{1, \ldots, p^k\}$ , que son $p^{k-1}$ en total. Para $m$ general, $\phi$ es multiplicativa: si $\gcd(a,b)=1$ entonces $\phi(ab)=\phi(a)\phi(b)$ .

\phi(p_1^{a_1} \cdots p_k^{a_k}) = m \prod_{p \mid m} \left(1 - \frac{1}{p}\right)

Sistema reducido de residuos

Un **sistema reducido de residuos módulo $m$ ** es un conjunto de $\phi(m)$ enteros, uno por cada clase de residuos invertibles. El conjunto $\{a \in \{1, \ldots, m\} : \gcd(a,m)=1\}$ es el sistema reducido canónico.

Análoga a la propiedad del sistema completo: si $\{r_1, \ldots, r_{\phi(m)}\}$ es un sistema reducido y $\gcd(a,m)=1$ , entonces $\{ar_1, \ldots, ar_{\phi(m)}\}$ también es un sistema reducido (módulo $m$ , claro). Esta permutación de las unidades es el corazón de la demostración del Teorema de Euler.

Ejemplo: módulo $12$ , los invertibles son $\{1, 5, 7, 11\}$ (los coprimos con $12$ ). Efectivamente $\phi(12) = \phi(4)\phi(3) = 2 \cdot 2 = 4$ .

Pequeño Teorema de Fermat como aperitivo

Usando lo anterior podemos probar el Pequeño Teorema de Fermat: si $p$ es primo y $p \nmid a$ , entonces $a^{p-1} \equiv 1 \pmod p$ .

Demostración rápida: considera el sistema reducido $\{1, 2, \ldots, p-1\}$ . Multiplica por $a$ : obtienes $\{a, 2a, \ldots, (p-1)a\}$ , que también es un sistema reducido (mismos elementos en otro orden). Al multiplicar todos los elementos de ambos conjuntos: $a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod p$ , es decir $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod p$ . Como $(p-1)!$ es invertible módulo $p$ , se cancela y queda $a^{p-1} \equiv 1 \pmod p$ .

Este resultado reducirá enormemente el trabajo al calcular potencias módulo un primo.

p \text{ primo},\; p \nmid a \implies a^{p-1} \equiv 1 \pmod{p}

Residuos y clases de residuos

Objetivo de la lección

Sistema completo de residuos

Residuos invertibles y la función de Euler

Sistema reducido de residuos

Pequeño Teorema de Fermat como aperitivo

Problemas del Capítulo 3 — con solución