¿Qué es la función φ de Euler?
La función indicatriz de Euler, que se escribe \(\varphi(n)\), cuenta cuántos enteros positivos del 1 al n no comparten ningún factor común con n salvo el 1; es decir, los enteros que son coprimos con n. Por ejemplo, \(\varphi(9) = 6\), porque 1, 2, 4, 5, 7 y 8 son todos coprimos con 9. Se trata de una función esencial en teoría de números y aparece por todas partes en criptografía, sobre todo en el algoritmo RSA, donde \(\varphi(n)\) determina el inverso modular que se emplea para generar las claves.
Cómo usar esta calculadora
Introduce cualquier entero positivo n y pulsa calcular. La herramienta descompone n en sus divisores primos distintos y aplica la fórmula del producto para devolverte \(\varphi(n)\) al instante, junto con la lista de primos distintos que ha encontrado. Funciona tanto con números pequeños como con cifras muy grandes, hasta mil millones.
La fórmula, paso a paso
La forma eficiente de calcular la indicatriz es la fórmula del producto:
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$ donde el producto recorre todos los primos distintos \(p\) que dividen a n.
Solo necesitas los primos distintos, no sus multiplicidades. Cada factor \(\left(1 - \frac{1}{p}\right)\) elimina la proporción de números divisibles por ese primo.
Ejemplo resuelto
Tomemos n = 36. Su factorización en primos es \(2^2 \times 3^2\), así que los primos distintos son 2 y 3. Entonces:
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$
Por tanto, hay exactamente 12 enteros entre 1 y 36 que son coprimos con 36.
Preguntas frecuentes
¿Cuánto vale \(\varphi(1)\)? Por convención, \(\varphi(1) = 1\), ya que el 1 es coprimo consigo mismo.
¿Cuánto vale φ de un primo p? Para cualquier primo \(p\), \(\varphi(p) = p - 1\), porque todos los enteros del 1 al p−1 son coprimos con p.
¿Es φ multiplicativa? Sí. Si \(\gcd(a, b) = 1\), entonces \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\), y esa es precisamente la razón por la que funciona el producto sobre los primos distintos.
