Teorema de Euler de la aritmética modular: enunciado y ejemplos

Actualizado el
El teorema de Euler, también llamado de Euler-Fermat, dice que si un número a no comparte divisores con n, al elevar a a la potencia φ(n) y dividir entre n el resto es siempre 1. Sirve para reducir potencias enormes en aritmética modular: calcular las últimas cifras de 7222, hallar inversos modulares o entender por qué funciona el cifrado RSA.
Ojo: Euler tiene muchos teoremas con su nombre. Esta guía trata el de la aritmética modular. Si buscabas la fórmula de los poliedros (V − A + C = 2) u otro, mira la tabla del final.
Enunciado del teorema de Euler
Sean n ≥ 1 y a enteros con mcd(a, n) = 1. Entonces
aφ(n) ≡ 1 (mod n)
donde φ(n) es la función de Euler (o indicatriz): la cantidad de números entre 1 y n que son coprimos con n. «≡ 1 (mod n)» significa que aφ(n) − 1 es múltiplo de n.
Cómo se calcula φ(n)
Si la factorización de n en primos es n = p1k1 · … · prkr, entonces
φ(n) = n · (1 − 1/p1) · … · (1 − 1/pr)
Por ejemplo, 100 = 22 · 52, luego φ(100) = 100 · 1/2 · 4/5 = 40; y 36 = 22 · 32, luego φ(36) = 36 · 1/2 · 2/3 = 12. Si p es primo, φ(p) = p − 1, porque todos los números de 1 a p − 1 son coprimos con p.
| n | 7 | 9 | 10 | 12 | 15 | 20 | 36 | 40 | 100 |
|---|---|---|---|---|---|---|---|---|---|
| φ(n) | 6 | 6 | 4 | 4 | 8 | 8 | 12 | 16 | 40 |
Demostración
Sean r1, r2, …, rk los números entre 1 y n coprimos con n, con k = φ(n).
- Multiplicamos cada uno por a: a·r1, …, a·rk. Todos siguen siendo coprimos con n, porque a y ri lo son.
- Sus restos módulo n son distintos: si a·ri ≡ a·rj, como a tiene inverso módulo n, ri ≡ rj, y eso solo pasa si i = j.
- Así que los restos de a·r1, …, a·rk son los mismos r1, …, rk, en otro orden. Multiplicando todos: ak · r1 · … · rk ≡ r1 · … · rk (mod n).
- El producto r1 · … · rk es coprimo con n y se puede simplificar. Queda ak ≡ 1, es decir, aφ(n) ≡ 1 (mod n).
Caso particular: el pequeño teorema de Fermat
Si n = p es primo, φ(p) = p − 1 y el teorema dice ap−1 ≡ 1 (mod p) para todo a no múltiplo de p. Es el pequeño teorema de Fermat, que Fermat enunció sin demostración. Una prueba clásica de Fermat usa que los coeficientes del binomio de Newton C(p, k) son múltiplos de p para 0 < k < p.
Ejemplos del teorema de Euler
1. Comprobación directa
φ(10) = 4 y mcd(3, 10) = 1. En efecto, 34 = 81 = 8 · 10 + 1, así que 34 ≡ 1 (mod 10).
2. Última cifra de 7222
La última cifra es el resto módulo 10. Como φ(10) = 4 y 222 = 4 · 55 + 2, se tiene 7222 = (74)55 · 72 ≡ 1 · 49 ≡ 9. La última cifra es 9.
3. Últimas dos cifras de 32026
Ahora el módulo es 100 y φ(100) = 40. Como 2026 = 40 · 50 + 26, 32026 ≡ 326 (mod 100). Se calcula por cuadrados: 35 = 243 ≡ 43; 310 ≡ 432 = 1849 ≡ 49; 320 ≡ 492 = 2401 ≡ 1; y 326 = 320 · 36 ≡ 729 ≡ 29. Las dos últimas cifras son 29.
Fíjate en que 320 ya da 1: φ(n) es un exponente que siempre funciona, pero no tiene por qué ser el menor. El menor se llama orden de a módulo n y siempre divide a φ(n).
4. Resto de 2100 entre 15
φ(15) = 8 y 100 = 8 · 12 + 4, así que 2100 ≡ 24 = 16 ≡ 1 (mod 15).
5. Resto de 112026 entre 9
Primero se reduce la base: 11 ≡ 2 (mod 9). φ(9) = 6 y 2026 = 6 · 337 + 4, luego 112026 ≡ 24 = 16 ≡ 7 (mod 9).
6. Inverso de 7 módulo 40
De aφ(n) ≡ 1 se deduce que a · aφ(n)−1 ≡ 1, así que el inverso de a es aφ(n)−1. Con φ(40) = 16, el inverso de 7 es 715 ≡ 23 (mod 40). Comprobación: 7 · 23 = 161 = 4 · 40 + 1.
Cuándo no se cumple
La hipótesis mcd(a, n) = 1 es imprescindible. Con a = 2 y n = 4: φ(4) = 2 y 22 = 4 ≡ 0 (mod 4), no 1. Si a y n comparten un factor primo p, todas las potencias de a son múltiplos de p y nunca pueden dejar resto 1 al dividir por n.
Errores habituales: reducir el exponente módulo n en lugar de módulo φ(n); olvidar comprobar que a y n son coprimos; calcular φ(n) como n − 1 cuando n no es primo.
Aplicación: el cifrado RSA
RSA toma n = p · q con p y q primos grandes, de modo que φ(n) = (p − 1)(q − 1). Se elige un exponente público e coprimo con φ(n) y se calcula el privado d con e · d ≡ 1 (mod φ(n)). El teorema de Euler garantiza que (me)d ≡ m (mod n). Con números de juguete: p = 5, q = 11, n = 55, φ(55) = 40, e = 7 y d = 23 (el inverso del ejemplo 6). El mensaje m = 2 se cifra como 27 = 128 ≡ 18 (mod 55) y al descifrar 1823 ≡ 2 (mod 55). La seguridad depende de que factorizar n sea muy difícil cuando p y q son enormes.
La misma idea de trabajar con restos aparece en el teorema del resto de polinomios, aunque allí se divide entre x − a en lugar de entre un número.
Historia
Leonhard Euler publicó en 1736 una demostración del pequeño teorema de Fermat. En 1763, en «Theoremata arithmetica nova methodo demonstrata», lo generalizó a módulos compuestos: es el enunciado con φ(n) que se ha visto aquí.
Los otros «teoremas de Euler»
| Nombre | Enunciado | Área |
|---|---|---|
| Teorema de Euler (esta guía) | aφ(n) ≡ 1 (mod n) si mcd(a, n) = 1 | Teoría de números |
| Fórmula de Euler para poliedros | V − A + C = 2 en un poliedro convexo (cubo: 8 − 12 + 6 = 2) | Geometría y grafos planos |
| Fórmula e identidad de Euler | eiθ = cos θ + i sen θ; con θ = π, eiπ + 1 = 0 | Números complejos |
| Teorema de Euler de funciones homogéneas | Si f es homogénea de grado k, x · ∂f/∂x + y · ∂f/∂y = k · f | Cálculo en varias variables |
La fórmula eiθ es la que permite escribir en forma polar las raíces complejas de un polinomio, que existen siempre por el teorema fundamental del álgebra.
Preguntas frecuentes
¿Qué dice el teorema de Euler?
Que si a y n son coprimos, a elevado a φ(n) deja resto 1 al dividir entre n. φ(n) es el número de enteros entre 1 y n coprimos con n.
¿Qué relación tiene con el pequeño teorema de Fermat?
Fermat es el caso en que n es un número primo p: entonces φ(p) = p − 1 y queda a^(p−1) ≡ 1 (mod p).
¿Cómo se calcula la última cifra de una potencia con Euler?
Se trabaja módulo 10, con φ(10) = 4: se divide el exponente entre 4 y se usa el resto. Por ejemplo, 7^222 termina igual que 7^2 = 49, en 9. Si la base es par o múltiplo de 5 no se puede aplicar.
¿El teorema de Euler es la fórmula de los poliedros?
No. La fórmula de los poliedros, V − A + C = 2, es otro resultado de Euler. El teorema de Euler de la aritmética modular trata de restos de potencias.
RELACIONADOS