Proof of the formula for the totient of a prime power

Proof

1. Let $p$ be a prime number and let $k$ be a positive integer. By definition, Euler's totient function $\varphi(p^k)$ is the number of integers $x$ with $1 \le x \le p^k$ that are coprime to $p^k$.
2. We show that an integer $x$ is coprime to $p^k$ if and only if $p$ does not divide $x$.
3. Assume $p \mid x$. Since $k \ge 1$, $p$ also divides $p^k$. So $p$ is a common divisor, and $\gcd(x, p^k) \ge p > 1$.
4. Assume $p \nmid x$, and let $d = \gcd(x, p^k)$ be the greatest common divisor. Since $p^k \ne 0$, $d$ is positive. Suppose that $d > 1$.
5. By the existence of a prime divisor, there is a prime $q$ with $q \mid d$. Then $q$ divides $p^k = p \cdot p \cdots p$.
6. By Euclid's lemma, applied to the $k$ factors in turn, $q$ divides $p$. Since $q > 1$ and $p$ is prime, $q = p$.
7. Then $p = q$ divides $d$, and $d$ divides $x$, so $p \mid x$. This contradicts step 4. So $d = 1$.
8. By steps 3 and 7, the integers in $\{ 1, \dots, p^k \}$ that are not coprime to $p^k$ are exactly the multiples of $p$ in this set.
9. These multiples are $p j$ with $1 \le j \le p^{k-1}$, since $1 \le p j \le p^k$ is equivalent to $1 \le j \le p^{k-1}$ for an integer $j$. So there are $p^{k-1}$ of them.
10. Hence $\varphi(p^k) = p^k - p^{k-1} = p^{k-1} (p - 1)$.