La función φ de Euler φ(n) cuenta cuántos enteros de 1 a n son primos con n, es decir, no tienen ningún factor primo en común con él. Es una herramienta básica de la teoría de números y el motor del cifrado RSA. Introduce la descomposición en factores primos de n (hasta tres números primos distintos con sus exponentes) y la calculadora da φ(n), la proporción de enteros primos con n y la fórmula del producto.
Cómo se hace el cálculo
Para n = p₁^a₁ × p₂^a₂ × p₃^a₃, con números primos distintos:
- φ(n) = Π p^(a−1) × (p − 1) sobre los factores primos
- De forma equivalente φ(n) = n × Π (1 − 1/p)
- Proporción de enteros primos con n = φ(n) ÷ n
- Enteros con un factor común = n − φ(n)
Un factor con exponente 0 se omite. La calculadora no comprueba que tus factores sean primos.
Ejemplo
Tomemos n = 2³ × 3² × 5 = 360. Los factores dan (2² × 1) × (3 × 2) × (1 × 4) = 4 × 6 × 4 = 96. Por tanto, φ(360) = 96: hay 96 enteros de 1 a 360 primos con 360, es decir, el 26,67 % de ellos, y 264 tienen un factor común con él. El producto (1 − ½)(1 − ⅓)(1 − ⅕) vale 0,2667.
Por qué es importante
En RSA, un módulo n = p × q es el producto de dos números primos grandes, y φ(n) = (p − 1)(q − 1) sirve para hallar la clave privada. El teorema de Euler usa φ(n) para calcular potencias módulo n, y la función φ da también el número de generadores de un grupo cíclico y el número de fracciones irreducibles de denominador n. Es un contenido habitual de las asignaturas de Álgebra y de Teoría de números en los grados de Matemáticas e Informática.
Conviene saber
φ(n) es siempre par para n mayor que 2. Para una potencia de un número primo, φ(pᵃ) = pᵃ − pᵃ⁻¹. Para dos enteros primos entre sí, φ(mn) = φ(m) × φ(n). Los factores introducidos deben ser números primos distintos: un número compuesto o un número primo repetido da un resultado falso. Esta herramienta es pedagógica.
En la práctica
Descompón primero n a mano o con una herramienta, introduce cada número primo con su exponente, y comprueba el resultado con un ejemplo pequeño como 12, donde φ(12) = 4.
Herramientas relacionadas
La calculadora del máximo común divisor y el mínimo común múltiplo relaciona dos enteros, la de la ecuación de segundo grado resuelve el grado dos, y la de la ecuación de tercer grado halla las raíces de un polinomio de grado tres.