- Primos, sobre la recta φ(p) = p − 1
- Otros números
- Tu n
Calculadora de la función φ de Euler
De los números del 1 al 12, solo 1, 5, 7 y 11 no tienen ningún factor común con 12, así que φ(12) = 4. La función φ de Euler cuenta estos números coprimos para cualquier n. Introduce un número hasta 10^18 para obtener φ(n) con sus factores primos y la fórmula del producto desarrollada, ver los números del 1 al n con los coprimos resaltados, comprobar el teorema de Euler, representar φ(k) para hasta 100.000 números a la vez o encontrar todos los n con un φ(n) dado. Introduce un número entero n hasta 10^18 o elige un ejemplo resuelto. Las fichas muestran φ(n), los factores primos de n, la proporción de los números del 1 al n que son coprimos con n y el número de divisores, y los pasos escriben la fórmula del producto con tus números. Hasta n = 500 se dibujan los números del 1 al n: los coprimos aparecen rellenos y los demás con el color del primo más pequeño que comparten con n. Señala un número para ver su mcd con n y haz clic en él para usarlo como a en el teorema de Euler. Gráfico muestra φ(k) para cada k hasta un límite; haz clic en un punto para abrir ese número. Inversa enumera cada n con φ(n) = m; haz clic en uno para abrirlo.
Cómo funciona
- Introduce un número entero n hasta 10^18 o elige un ejemplo resuelto como φ(60), un módulo RSA o el número de Carmichael 561.
- Lee φ(n), los factores primos y la fórmula del producto con tus números. Hasta 500, señala los números del 1 al n para ver su mcd con n y haz clic en uno para comprobar con él el teorema de Euler.
- Cambia a Gráfico para ver φ(k) para cada k hasta 100.000, o a Inversa para enumerar todos los n con φ(n) = m.
Cómo se calcula φ(n)
Descompón n en factores primos y multiplica n por (1 − 1/p) para cada primo p que lo divide. Para 60 = 2² × 3 × 5 se obtiene 60 × 1/2 × 2/3 × 4/5 = 16. Tachando se llega a la misma cuenta: de los 60 números, 30 son pares; de los 30 impares, 10 son múltiplos de 3; de los 20 restantes, 4 son múltiplos de 5, y quedan 16. Para una potencia de un primo la fórmula es φ(p^k) = p^(k−1)(p − 1), y los valores se multiplican: φ(60) = 2 × 2 × 4. Lo difícil es factorizar. La calculadora usa división de prueba, un test de primalidad de Miller-Rabin y el método rho de Pollard, de modo que incluso un producto de 18 cifras de dos primos de 9 cifras tarda una fracción de segundo.
Dónde se usa la función φ
φ(n) cuenta las fracciones k/n entre 0 y 1 que ya son irreducibles, los pasos que llevan una aguja por todas las horas de un reloj de n horas (1, 5, 7 y 11 en un reloj de 12 horas) y los números que tienen inverso módulo n. Euler demostró que a^φ(n) ≡ 1 (mod n) para todo a coprimo con n, y el cifrado RSA se basa en ello: con n = 3233 = 61 × 53, φ(n) = 60 × 52 = 3.120, y el exponente público 17 tiene como pareja privada 2.753, porque 17 × 2.753 = 15 × 3.120 + 1.
Preguntas frecuentes
¿Qué es la función φ de Euler?
φ(n) es la cantidad de números enteros del 1 al n que no tienen ningún factor común con n aparte del 1. φ(9) = 6, porque 1, 2, 4, 5, 7 y 8 son coprimos con 9, mientras que 3, 6 y 9 comparten el factor 3. Por convención, φ(1) = 1. Euler estudió la función en la década de 1760; Gauss le dio el símbolo φ en 1801 y James Joseph Sylvester el nombre inglés totient en 1879.
¿Cuánto vale φ de un número primo?
p − 1, porque todo número del 1 al p − 1 es coprimo con un primo p, así que φ(97) = 96. Para una potencia de un primo, φ(p^k) = p^k − p^(k−1), porque solo los múltiplos de p comparten un factor con ella: φ(81) = 81 − 27 = 54.
¿Qué dice el teorema de Euler?
Si a y n son coprimos, entonces a^φ(n) deja resto 1 al dividirlo entre n. Para n = 60 y a = 7: φ(60) = 16, y 7^16 ≡ 1 (mod 60). El pequeño teorema de Fermat es el caso de un n primo. A menudo ya basta un exponente menor: 7^4 = 2.401 = 40 × 60 + 1. El menor exponente que funciona para todo a coprimo con n es la función de Carmichael λ(n), que para 60 vale 4.
¿Pueden dos números tener la misma φ?
Sí, y normalmente son varios: φ(n) = 24 para n = 35, 39, 45, 52, 56, 70, 72, 78, 84 y 90. Algunos números pares nunca son un valor de φ, el menor es 14, y ningún número impar mayor que 1 lo es, porque φ(n) es par a partir de n = 3. Robert Carmichael afirmó en 1907 que ningún valor se toma exactamente una vez. Sigue sin demostrarse, y Kevin Ford mostró en 1998 que una excepción tendría que ser mayor que 10^(10^10).
¿Qué tamaño de número puedo introducir?
Cualquier entero hasta 10^18. La calculadora lo factoriza con aritmética entera exacta en tu navegador, de modo que φ(10^18) = 4 × 10^17 y φ(999.999.866.000.004.473) = 999.999.864.000.004.608 salen exactos hasta la última cifra. Los números del 1 al n se dibujan hasta 500, el gráfico llega hasta 100.000 y la inversa funciona para valores hasta 10^10.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor