Función Phi de Euler

Aprende la herramienta que extiende Fermat a TODOS los módulos.

Estudiar en la plataforma interactiva
Modulo 5 · Teoría de Números

La Función Phi de Euler

φ(n)\varphi(n) cuenta los enteros entre 1 y nn que son coprimos con nn.

Visualizador de Coprimos

1
2
3
4
5
6
7
8
9
10
11
12

φ(12)=4\varphi(12) = 4

Hay 4 números menores que 12 coprimos con él

🧮 Fórmula de Euler

Si n=p1a1⋯pkakn = p_1^{a_1} \cdots p_k^{a_k}, entonces:

φ(n)=n∏p∣n(1−1p)\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)

Ejemplo: φ(60)

1

Factorizar

60=22×3×560 = 2^2 \times 3 \times 5
2

Aplicar fórmula

φ(60)=60(1−12)(1−13)(1−15)\varphi(60) = 60 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right)
3

Calcular

=60×12×23×45=16= 60 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 16

Concepto Clave

"φ(p) = p-1 para primo p. Por eso Fermat (exponente p-1) es caso particular de Euler (exponente φ(n))."

Teorema de Euler

📐 Teorema de Euler

Si gcd⁡(a,n)=1\gcd(a, n) = 1, entonces:

aφ(n)≡1(modn)a^{\varphi(n)} \equiv 1 \pmod{n}

Funciona para TODO módulo nn, no solo primos.

Ejemplo: 7^100 mod 10

1

Calcular φ(10)

φ(10)=10(1−1/2)(1−1/5)=4\varphi(10) = 10(1-1/2)(1-1/5) = 4
2

Euler dice

74≡1(mod10)7^4 \equiv 1 \pmod{10}
3

Reducir: 100 = 4 × 25

7100=(74)25≡125=1(mod10)7^{100} = (7^4)^{25} \equiv 1^{25} = 1 \pmod{10}

💡 Esto confirma que las últimas cifras de 71007^{100} terminan en 1.

Concepto Clave

"Euler generaliza Fermat: reduce exponente a^n módulo φ(m) cuando gcd(a,m)=1. Fundamental para RSA."

Problema de Olimpiada

Desafío

Encuentre los dos últimos dígitos de 320233^{2023}.

Ver Solución

Últimos dos dígitos = 32023 mod 1003^{2023} \bmod 100.

φ(100)=100(1−1/2)(1−1/5)=40\varphi(100) = 100(1-1/2)(1-1/5) = 40.

2023=40×50+232023 = 40 \times 50 + 23. Así 32023≡323(mod100)3^{2023} \equiv 3^{23} \pmod{100}.

310=59049≡493^{10} = 59049 \equiv 49, 320≡492=2401≡13^{20} \equiv 49^2 = 2401 \equiv 1, 323≡1⋅27=273^{23} \equiv 1 \cdot 27 = 27.

Últimos dos dígitos: 27.