φ(n) = n × ∏(1 - 1/p).
La Euler's totient function, que escribimos como $\phi(n)$, cuenta cuántos enteros positivos menores o iguales a $n$ son primos relativos con $n$. Aunque puedes calcular $\phi(n)$ enlistando y contando los números cuando $n$ es pequeño, esto se vuelve imposible cuando $n$ es muy grande. La fórmula general para la función totiente te da una forma muy potente de calcular este valor directamente usando la factorización en primos de $n$. Esta fórmula se basa en el Fundamental Theorem of Arithmetic, que dice que cualquier entero $n > 1$ tiene una única factorización en primos.
Lo importante de esta fórmula es que la función totiente es multiplicativa. Específicamente, $\phi$ es una función multiplicativa, lo que significa que si $\gcd(m, n) = 1$, entonces $\phi(mn) = \phi(m)\phi(n)$. Esta propiedad te permite descomponer un número en sus componentes de potencias de primos, calcular el totiente de cada parte y luego multiplicar los resultados. Esta técnica es fundamental en teoría de números, sobre todo en aplicaciones de aritmética modular, como el Euler's Theorem ($a^{\phi(n)} \equiv 1 \pmod n$) y el algoritmo de cifrado RSA.
De forma intuitiva, puedes entender la fórmula $\phi(n) = n \prod (1 - 1/p)$ desde una perspectiva probabilística o usando el Principle of Inclusion-Exclusion. Si tomas un