La función totiente de Euler, escrita φ(n), cuenta cuántos enteros positivos hasta n no comparten ningún factor común con n. Parece un simple ejercicio de conteo, pero sustenta la aritmética modular, la generalización de Euler del pequeño teorema de Fermat, y el paso de generación de claves de la criptografía RSA. Esta calculadora calcula φ(n) mediante factorización prima, muestra la derivación paso a paso, y — para n pequeños — lista directamente cada entero coprimo.
Qué cuenta realmente φ(n)
φ(n) cuenta los enteros positivos k en el rango 1 ≤ k ≤ n para los cuales gcd(k, n) = 1 — es decir, k y n son coprimos. Para n = 1, φ(1) = 1 por convención. Para un primo p, todo entero por debajo de él es automáticamente coprimo, así que φ(p) = p − 1. La pestaña Lista de Coprimos de esta calculadora lista estos enteros directamente siempre que n sea lo suficientemente pequeño (hasta 2,000) para mostrarlos todos.
Cómo la factorización prima da la fórmula
La forma más rápida de calcular φ(n) para un n grande no es verificar cada entero por coprimalidad — es factorizar n primero en números primos. El totiente de Euler es una función multiplicativa, lo que significa que φ(mn) = φ(m)φ(n) siempre que gcd(m, n) = 1. Combinado con el hecho de que φ(p^k) = p^k − p^(k-1) = p^k(1 − 1/p) para cualquier potencia prima, esto da la fórmula general φ(n) = n·Π(1 − 1/p) sobre cada factor primo distinto p de n — los exponentes en sí desaparecen por completo de la fórmula. La pestaña Factorización Prima de esta calculadora muestra exactamente esta derivación, término por término, para cualquier n que ingreses.
Por qué a la criptografía le importa φ(n)
El cifrado RSA genera un par de claves pública/privada a partir de dos primos grandes distintos p y q, dejando que n = pq sea el módulo público. El exponente privado se deriva usando φ(n) = (p−1)(q−1) — la misma fórmula que resalta la línea de interpretación de esta calculadora siempre que n se factoriza en exactamente dos primos distintos. En implementaciones reales de RSA, p y q tienen cientos de dígitos de longitud, pero el cálculo del totiente subyacente es idéntico al que se muestra aquí para ejemplos pequeños. Herramientas relacionadas como la Calculadora de Factorización Prima y la Calculadora de Módulo son útiles para explorar los otros bloques de construcción de teoría de números detrás de la aritmética modular y la criptografía.