φ(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 coprimos con $n$. Aunque contar estos números a mano es posible cuando son números chiquitos, la Fórmula de la Función Totiente te permite calcular $\phi(n)$ de forma eficiente para cualquier entero, siempre que conozcas su factorización en primos. Esta fórmula es una pieza clave en la teoría de números y es básica para resolver problemas de aritmética modular, orden de elementos y el Euler's Theorem (que dice que $a^{\phi(n)} \equiv 1 \pmod n$ si $a$ y $n$ son coprimos).
La idea detrás de la fórmula es que la divisibilidad por primos distintos es independiente. Si un primo $p$ divide a $n$, exactamente $\frac{1}{p}$ de los enteros del $1$ al $n$ son múltiplos de $p$. Por lo tanto, la fracción de enteros que no son divisibles entre $p$ es $(1 - \frac{1}{p})$. Como las restricciones que ponen los distintos factores primos son independientes (un concepto que el Chinese Remainder Theorem formaliza), puedes aplicar este proceso de "filtrado" para cada factor primo distinto de $n$. Al multiplicar $n$ por estas probabilidades, obtienes la cantidad de números que no comparten factores primos con $n$.
Si tienes la factorización en primos de $n$: