Totient of a Prime Power

Counting the numbers below $p^k$ that are coprime to it is easier than the general totient because there is only one prime to avoid. Of the $p^k$ candidates, the ones sharing a factor are exactly the multiples of p, and there are $p^{k-1}$ of those. Subtract: $p^k - p^{k-1} = p^{k-1}(p-1)$. For $2^5 = 32$ that is $16 \times 1 = 16$, which is just the odd numbers — every odd number below 32 is coprime to it, and there are 16.

Set k = 1 and the formula reduces to $p - 1$, the fact that everything below a prime is coprime to it. That special case is used constantly: it is why the multiplicative group mod p has p−1 elements, and therefore why Fermat's little theorem has the exponent it does.

Like the sum-of-divisors formula, this is a building block rather than a destination, because φ is multiplicative across coprime parts. $\varphi(360) = \varphi(2^3)\varphi(3^2)\varphi(5) = 4 \times 6 \times 4 = 96$. Every factor there came from this one formula. And as always, p must actually be prime — the derivation counted "multiples of p" as the only numbers sharing a factor, which is false the moment p is composite.