Enunciado del Teorema de Euler

Teoría

El Teorema de Euler (también conocido como el Teorema de Fermat-Euler) es un resultado fundamental en la teoría de números que generaliza el Pequeño Teorema de Fermat para módulos compuestos. Establece una relación entre las potencias de un entero y el módulo $n$, y usa específicamente la función phi de Euler, $\phi(n)$. El teorema dice que si un entero $a$ es coprimo con un entero positivo $n$ (o sea, $\gcd(a, n) = 1$), entonces al elevar $a$ a la potencia $\phi(n)$ obtienes un residuo de $1$ al dividirlo entre $n$.

Este teorema es una herramienta esencial en las matemáticas de competencia, sobre todo para problemas que tienen que ver con aritmética modular y el cálculo de potencias grandes. Su mayor utilidad es para reducir exponentes grandes. Como $a^{\phi(n)} \equiv 1 \pmod n$, los exponentes de $a$ se comportan de forma cíclica con un periodo que divide a $\phi(n)$. Esto te permite simplificar la expresión $a^k \pmod n$ reduciendo el exponente $k$ módulo $\phi(n)$, lo que transforma problemas que parecen imposibles de calcular en puros cálculos manejables.

De forma intuitiva, el Teorema de Euler describe la estructura del grupo multiplicativo de los enteros módulo $n$, que escribes como $(\mathbb{Z}/n\mathbb{Z})^\