¿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.
Más ejemplos resueltos
Ejemplo 1: un primo, φ(13)
13 es primo, así que su único factor primo es el propio 13:
\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. Esto coincide con el atajo para primos \(\varphi(p) = p-1\).
Ejemplo 2: una potencia de primo, φ(32)
Factorización: \(32 = 2^5\). El único primo distinto es 2.
\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.
Forma equivalente para potencias de primos: \(\varphi(p^k) = p^k - p^{k-1}\), así que \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). Estos son exactamente los números impares del 1 al 31.
Ejemplo 3: tres o más primos distintos, φ(210)
Factorización: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).
- Comenzar con \(210\).
- Multiplicar por \(1-\frac{1}{2} = \frac{1}{2}\): \(210 \cdot \frac{1}{2} = 105\).
- Multiplicar por \(1-\frac{1}{3} = \frac{2}{3}\): \(105 \cdot \frac{2}{3} = 70\).
- Multiplicar por \(1-\frac{1}{5} = \frac{4}{5}\): \(70 \cdot \frac{4}{5} = 56\).
- Multiplicar por \(1-\frac{1}{7} = \frac{6}{7}\): \(56 \cdot \frac{6}{7} = 48\).
Por tanto, \(\varphi(210) = \)48. Observa que la regla del producto usa cada primo distinto una sola vez. Por ejemplo, \(60 = 2^2 \cdot 3 \cdot 5\) da \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\).
Interpretación de φ(n) y sus usos
- Relación con la primalidad: para \(n \ge 2\), \(\varphi(n) = n-1\) si y solo si \(n\) es primo. Todo número menor que un primo es coprimo con él. Si \(n\) es compuesto, al menos un número menor que él comparte un factor, por lo que \(\varphi(n) < n-1\).
- Grupo de unidades: \(\varphi(n)\) es el número de elementos del grupo de unidades módulo \(n\), es decir, los residuos que tienen un inverso multiplicativo módulo \(n\). Para \(n = 15\) son 1, 2, 4, 7, 8, 11, 13, 14, lo que da 8 elementos.
- Teorema de Euler: si \(\gcd(a, n) = 1\), entonces \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Ejemplo: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, y \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). El pequeño teorema de Fermat es el caso especial \(n = p\) primo.
- RSA: cuando \(n = pq\) para primos distintos \(p\) y \(q\), \(\varphi(n) = (p-1)(q-1)\). Con \(n = 15 = 3 \cdot 5\): \(\varphi(15) = 2 \cdot 4 = 8\). El exponente público \(e\) debe ser coprimo con \(\varphi(n)\), y el exponente privado \(d\) cumple \(ed \equiv 1 \pmod{\varphi(n)}\). El RSA real usa primos de cientos de dígitos. Quien pueda factorizar \(n\) puede calcular \(\varphi(n)\), por eso la seguridad depende de que factorizar sea difícil.
- La razón depende solo de los primos distintos: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\). Los exponentes no importan. Por ejemplo, 6 y 12 tienen el mismo conjunto de primos {2, 3}, así que \(\varphi(6)/6 = 2/6 = 1/3\) y \(\varphi(12)/12 = 4/12 = 1/3\).
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.