Función Phi de Euler

Módulo 5 · Teoría de Números

¿Cuántas fracciones no se pueden simplificar?

Escribe las fracciones $\frac{1}{36}, \frac{2}{36}, \ldots, \frac{36}{36}$ . Algunas se simplifican, como $\frac{2}{36} = \frac{1}{18}$ , y otras no, como $\frac{5}{36}$ . Las que no se simplifican son las que tienen el numerador coprimo con 36. ¿Cuántas son? Esa cuenta tiene nombre: $\varphi(36)$ , la función phi de Euler.

Momento animado

Lo que queda es φ

Del 1 al 36, tacha lo que comparte un primo con 36. Mira qué fracción queda en cada paso.

Avancetachando el 2

Etapas

Etapa 1 de 3 · Sin el 2

36 = 2² · 3². Para ser coprimo con 36, un número no puede ser múltiplo de 2 ni de 3. Primero se tachan los múltiplos de 2: uno de cada dos. Quedan 36 · ½ = 18.

La Función Phi de Euler

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

Laboratorio

Visualizador de coprimos

Mueve $n$ : los números rellenos son los coprimos con $n$ , y los cuenta $\varphi(n)$ .

123456789101112

$\varphi(12) = 12\left(1 - \tfrac{1}{2}\right)\left(1 - \tfrac{1}{3}\right) = 4$

Hay 4 números entre 1 y 12 sin factores primos en común con 12.

Valor de

n

n = 12

Los primos de 12 son 2 y 3: se quitan sus múltiplos y quedan 4.

Fórmula de Euler

Si $n = p_1^{a_1} \cdots p_k^{a_k}$ , entonces:

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

Ejemplo: φ(60)

Factorizar

60 = 2^2 \times 3 \times 5

Aplicar fórmula

\varphi(60) = 60 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right)

Calcular

= 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

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

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

Funciona para TODO módulo $n$ , no solo primos.

Ejemplo: 7¹⁰⁰ mod 10

Calcular φ(10)

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

Euler dice

7^4 \equiv 1 \pmod{10}

Reducir: 100 = 4 × 25

7^{100} = (7^4)^{25} \equiv 1^{25} = 1 \pmod{10}

Esto confirma que la última cifra de $7^{100}$ es 1.

Concepto Clave

"Euler generaliza Fermat: en aⁿ mod m, el exponente n se reduce módulo φ(m) cuando gcd(a, m) = 1. Es la base de RSA."

Problemas de Olimpiada

Dos últimos dígitos con el Teorema de Euler

Encuentre los dos últimos dígitos de $3^{2023}$ :

Práctica · φ(36)

¿Cuántas de las fracciones

\frac{1}{36}, \frac{2}{36}, \ldots, \frac{36}{36}

no se pueden simplificar?

Práctica · φ de un primo

¿Cuánto vale

\varphi(13)

Práctica · Con la fórmula

¿Cuánto vale

\varphi(100)