Teorema de Euler

Teoría

El teorema de Euler es una generalización del Pequeño Teorema de Fermat para módulos compuestos. Dice que si $a$ y $n$ son enteros positivos primos relativos, entonces $a$ elevado a la potencia de la función totiente de Euler $\varphi(n)$ es congruente a 1 módulo $n$.

Este teorema es fundamental en teoría de números y tiene aplicaciones importantes para:

• Calcular inversos modulares
• Simplificar cálculos de potencias grandes mod $n$
• Criptografía RSA
• Probar propiedades del orden multiplicativo

La idea clave es que $\varphi(n)$ cuenta cuántos elementos hay en el grupo multiplicativo $(\mathbb{Z}/n\mathbb{Z})^*$, y por teoría de grupos, cualquier elemento elevado al orden del grupo te da la identidad.

Fórmulas Clave

Teorema de Euler:

Si $\gcd(a, n) = 1$, entonces: $$a^{\varphi(n)} \equiv 1 \pmod{n}$$

Función Totiente de Euler:

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

Para un primo $p$: $\varphi(p) = p - 1$

Para la potencia de un primo: $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$

Para $m, n$ primos relativos: $\varphi(mn) = \varphi(m)\varphi(n)$

Reducción de Exponentes:

Si $\gcd(a, n) = 1$: $$a^k \equiv a^{k \mod \varphi(n)} \pmod{n}$$

Inverso Modular:

Si $\gcd(a, n) = 1$: $$a^{-1} \equiv a^{\varphi(n)-1} \pmod{n}$$

Demostración

Demostración (Análoga al Pequeño Teorema de Fermat):

Toma ${r_1, r_2, \ldots, r_{\varphi(n)}}$ como el sistema reducido de residuos módulo $n$ (todos los enteros del 1 al $n-1$ que son primos relativos con $n$).

Afirmación: El conjunto ${ar_1, ar_2, \ldots, ar_{\varphi(n)}}$ módulo $n$ es una permutación de ${r_1, r_2, \ldots, r_{\varphi(n)}}$.

Demostración de la afirmación:

1. Cada $ar_i$ es primo relativo con $n$ (ya que $\gcd(a,n) = \gcd(r_i, n) = 1$)
2. Los $ar_i$ son distintos mod $n$: si $ar_i \equiv ar_j \pmod{n}$, entonces $r_i \equiv r_j \pmod{n}$ (porque $\gcd(a,n) = 1$)
3. Hay $\varphi(n)$ de estos elementos y todos son primos relativos con $n$, así que forman el sistema reducido de residuos.

Para terminar la demostración:

Multiplica todos los elementos: $$\prod_{i=1}^{\varphi(n)} (ar_i) \equiv \prod_{i=1}^{\varphi(n)} r_i \pmod{n}$$

$$a^{\varphi(n)} \prod_{i=1}^{\varphi(n)} r_i \equiv \prod_{i=1}^{\varphi(n)} r_i \pmod{n}$$

Toma $R = \prod_{i=1}^{\varphi(n)} r_i$. Como cada $r_i$ es primo relativo con $n$, $R$ también lo es.

Si divides entre $R$ (que se puede porque $\gcd(R, n) = 1$): $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ $\square$

Demostración Alternativa (Teoría de Grupos):

El conjunto $(\mathbb{Z}/n\mathbb{Z})^* = {[a] : \gcd(a,n) = 1}$ forma un grupo bajo la multiplicación.

El orden de este grupo es $|(\mathbb{Z}/n\mathbb{Z})^*| = \varphi(n)$.

Por el teorema de Lagrange, para cualquier elemento $[a]$ en el grupo: $$[a]^{|G|} = [a]^{\varphi(n)} = [1]$$

Por lo tanto, $a^{\varphi(n)} \equiv 1 \pmod{n}$. $\square$