Saltar al contenido
Omnikalc

Función φ de Euler: ¿cuántos enteros son primos con n?

Introduce los factores primos de n y sus exponentes para obtener la función φ de Euler φ(n), la proporción de enteros primos con n y la fórmula del producto.

Actualizado el
Tus datos

Valor fuera de rango

Valor fuera de rango

Valor fuera de rango

Valor fuera de rango

Valor fuera de rango

Valor fuera de rango

Resultados

Función φ de Euler φ(n)

96

El número n
360
Proporción de enteros de 1 a n primos con n
26,67 %
Enteros de 1 a n que tienen un factor común con n
264
Producto de los (1 − 1/p) sobre los factores primos
0,2667

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.

Preguntas frecuentes

¿Qué es la función φ de Euler?

φ(n) cuenta los enteros de 1 a n que son primos con n, es decir, que no tienen ningún factor primo en común con él. Para un número primo p, todos los enteros menores sirven, de modo que φ(p) = p − 1. Para n = 12, sirven los enteros 1, 5, 7 y 11, de modo que φ(12) = 4.

¿Cómo se calcula a partir de los factores primos?

Si n = p₁^a₁ × p₂^a₂ × …, entonces φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …, lo que equivale al producto de los p^(a−1)(p−1) sobre los factores primos. Primero hace falta la descomposición de n en factores primos.

¿Para qué sirve?

La función φ está en el corazón del cifrado RSA, donde las claves pública y privada están ligadas por φ(n) = (p − 1)(q − 1) para dos números primos, y del teorema de Euler, que dice que a^φ(n) ≡ 1 (mod n) cuando a y n son primos entre sí.

¿Comprueba la calculadora que mis factores son primos?

No. Los factores primos los introduces tú, y el resultado solo es válido si son realmente primos y distintos. Descompón primero el número con una herramienta de factorización.

¿Te ha resultado útil esta calculadora?

¡Gracias por tu opinión!

Resultados orientativos con fines informativos. No sustituyen el consejo de un profesional.