La función φ de Euler explicada

Escribe los números del 1 al 10 y tacha cada uno que comparta un factor con 10. Quedan cuatro: 1, 3, 7 y 9. Esa cuenta, φ(10) = 4, es la función φ de Euler, una de las funciones más usadas de la teoría de números, desde las fracciones y los relojes hasta el cifrado que protege los pagos en línea.

Los números del 1 al 30 en una cuadrícula con rellenos los ocho coprimos con 30, la fórmula φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 y un gráfico de φ(k) con los primos sobre una recta
Los números del 1 al 30 en una cuadrícula con rellenos los ocho coprimos con 30, la fórmula φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 y un gráfico de φ(k) con los primos sobre una recta

Contar números coprimos

Dos números son coprimos cuando su máximo común divisor es 1. φ(n) cuenta los k del 1 al n con mcd(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 y φ(1) = 1. La misma cuenta aparece en muchos lugares. Es el número de fracciones k/n entre 0 y 1 que ya son irreducibles, el número de pasos que llevan una aguja por todas las horas de un reloj de n horas y el número de k que tienen inverso módulo n, de modo que k × x ≡ 1 (mod n) tiene solución.

La fórmula del producto

Si los primos que dividen a n son p₁, p₂ …, entonces φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. La razón es una criba. La mitad de los números son pares, así que quitar los múltiplos de 2 deja la fracción 1 − 1/2; de los números que quedan, uno de cada tres es múltiplo de 3, y así sucesivamente. Por el teorema chino del resto, las condiciones para primos distintos son independientes, así que las fracciones simplemente se multiplican. Para 100 = 2² × 5² se obtiene 100 × 1/2 × 4/5 = 40. Dos propiedades dan el mismo resultado de otra forma: φ(p^k) = p^(k−1)(p − 1), y φ(mn) = φ(m) φ(n) cuando m y n son coprimos, así que φ(100) = φ(4) × φ(25) = 2 × 20 = 40.

El teorema de Euler

Fermat observó en 1640 que a^(p−1) ≡ 1 (mod p) para un primo p y cualquier a que p no divida. Euler demostró la versión general, publicada en 1763: a^φ(n) ≡ 1 (mod n) siempre que mcd(a, n) = 1. La demostración es breve. Multiplica por a los φ(n) números coprimos con n; los productos vuelven a ser coprimos con n y todos distintos módulo n, así que son los mismos números en otro orden, y al comparar los dos productos queda a^φ(n) ≡ 1. El menor exponente que funciona para un a dado es su orden, que siempre divide a φ(n); el menor que funciona para todos los a a la vez es la función de Carmichael λ(n). Para 561 = 3 × 11 × 17, λ(561) = 80 divide a 560, así que a^560 ≡ 1 (mod 561) para todo a coprimo con 561, aunque 561 no es primo. Es el menor número de Carmichael y la razón por la que el test de Fermat por sí solo no puede demostrar que un número es primo.

Leonhard Euler, en un retrato de Jakob Emanuel Handmann. En 1763 publicó la forma general de la observación de Fermat: a^φ(n) ≡ 1 (mod n) cuando a y n son coprimos.
Leonhard Euler, en un retrato de Jakob Emanuel Handmann. En 1763 publicó la forma general de la observación de Fermat: a^φ(n) ≡ 1 (mod n) cuando a y n son coprimos.

La suma sobre divisores de Gauss y la media

Suma φ(d) sobre los divisores d de n y siempre vuelves a obtener n: para 12, φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss lo demostró en sus Disquisitiones Arithmeticae de 1801; se ve al simplificar las fracciones 1/12, 2/12 … 12/12 y ordenarlas por su denominador. En promedio, φ(k) es alrededor de 0,61 k: la media de φ(k)/k tiende a 6/π² ≈ 0,6079, que es también la probabilidad de que dos enteros al azar sean coprimos, y φ(1) + … + φ(N) se acerca a 3N²/π². Para N = 1.000 la suma es 304.192, frente a 3N²/π² ≈ 303.964.

Carl Friedrich Gauss, en un retrato de Christian Albrecht Jensen de 1840. Introdujo la notación de congruencia a ≡ b (mod n) en sus Disquisitiones Arithmeticae de 1801.
Carl Friedrich Gauss, en un retrato de Christian Albrecht Jensen de 1840. Introdujo la notación de congruencia a ≡ b (mod n) en sus Disquisitiones Arithmeticae de 1801.

Valores que nunca aparecen

φ(n) es par para todo n a partir de 3, porque los números coprimos con n van por parejas k y n − k. Tampoco todo número par es un valor: 14, 26, 34, 38 y 50 son los primeros que nunca aparecen, mientras que 24 es el valor de diez números distintos, del 35 al 90. Encontrarlos es una búsqueda finita, porque para cada primo p que divide a n, p − 1 tiene que dividir a φ(n). En 1907 Robert Carmichael afirmó que ningún valor se toma exactamente una vez. Su demostración era errónea, la afirmación sigue abierta y cualquier excepción tendría que ser mayor que 10^(10^10). D. H. Lehmer preguntó en 1932 si φ(n) puede dividir a n − 1 para un n compuesto; no se conoce ningún ejemplo.

La función φ en RSA

RSA elige dos primos grandes p y q y publica n = pq y un exponente e. Como φ(n) = (p − 1)(q − 1), quien sepa factorizar n puede calcular φ(n) y, a partir de él, el exponente privado d con e × d ≡ 1 (mod φ(n)); el teorema de Euler garantiza entonces que (m^e)^d ≡ m (mod n). En el ejemplo de manual n = 3233 = 61 × 53, φ(n) = 3.120, e = 17 y d = 2.753. Muchas implementaciones usan en su lugar λ(n) = mcm(p − 1, q − 1), aquí 780, lo que da el d menor 413. Calcular φ(n) para un módulo RSA de 600 cifras es tan difícil como factorizarlo: a partir de n y φ(n), los dos primos salen con una sola raíz cuadrada.

Ron Rivest, Adi Shamir y Len Adleman (de izquierda a derecha)
Ron Rivest, Adi Shamir y Len Adleman (de izquierda a derecha)

Explóralo

Abre la calculadora e introduce cualquier n hasta 10^18 para ver φ(n) con sus factores primos y la fórmula. Hasta 500 se dibujan los números del 1 al n, los coprimos rellenos y los demás coloreados según el primo más pequeño que comparten con n, de modo que la fórmula del producto se convierte en una criba que se puede contar. Elige un número a para comprobar el teorema de Euler, cambia a Gráfico para ver φ(k) hasta 100.000 con los primos sobre la recta φ(p) = p − 1, o a Inversa para encontrar todos los n con φ(n) = m.

Preguntas frecuentes

¿Por qué φ(1) = 1?

Porque mcd(1, 1) = 1: el único número del 1 al 1 es coprimo con 1. La convención además mantiene válidas las fórmulas, por ejemplo la suma de Gauss sobre los divisores de n, que para n = 1 es simplemente φ(1) = 1.

¿Es φ lo mismo que la función contadora de primos?

No. π(n) cuenta los primos hasta n, φ(n) los números hasta n que son coprimos con n. φ(10) = 4 cuenta 1, 3, 7 y 9, mientras que π(10) = 4 cuenta 2, 3, 5 y 7. Aquí coinciden por casualidad: φ(12) = 4, pero π(12) = 5.

¿Con qué rapidez se calcula φ(n)?

Con la misma rapidez con que se pueda factorizar n. Con los factores primos conocidos bastan unas pocas multiplicaciones; sin ellos no se conoce ningún método rápido, y en eso se basa RSA. Para números hasta 10^18 la factorización tarda milisegundos en un navegador; para números de cientos de cifras puede tardar años.

¿Qué números tienen la φ(n) más pequeña en relación con n?

Los números con muchos factores primos pequeños. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… solo depende de qué primos dividen a n, no de sus potencias: para cualquier potencia de 2 es exactamente 1/2, y para 30 = 2 × 3 × 5 es 8/30, alrededor del 27 %. El producto de los 15 primeros primos, 614.889.782.588.491.410, tiene φ(n)/n ≈ 14 %, el valor más bajo de todos los números hasta 10^18.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Abrir la calculadora