φ(p^k) = p^k - p^(k-1).
La función totiente de Euler, que escribimos como $\phi(n)$, cuenta cuántos enteros positivos menores o iguales a $n$ son primos relativos con $n$. Calcular $\phi(n)$ para un entero cualquiera depende mucho del teorema fundamental de la aritmética y de la propiedad multiplicativa de la función. Sin embargo, la pieza clave para este cálculo es determinar el totiente de una potencia de primo, $n = p^k$. A diferencia de los números compuestos normales, las potencias de primos tienen un conjunto de factores muy estructurado, lo que hace que calcular su totiente sea sencillo usando el conteo por complemento.
Este concepto es crucial en las olimpiadas de matemáticas porque es el primer paso para sacar la fórmula general de $\phi(n)$. Una vez que conoces el valor de $\phi(p^k)$, puedes calcular $\phi(n)$ para cualquier entero factorizando $n$ en potencias de primos. Además, conocer $\phi(p^k)$ es esencial para aplicar el Teorema de Euler al resolver problemas de exponenciación modular con módulos que son potencias de primos, algo muy común en problemas de teoría de números de AIME y USAMO.
La idea detrás de la fórmula es identificar qué números no son coprimos con $p^k$. Como $p$ es un número primo, el único factor primo de $p^k$ es $p$. Por lo tanto, un entero $x$ comparte un factor común con $p^k$