Exercise 1127Number theory › PrimesL1Added 3 Nov 2026

Euler's totient of a prime power

#Euler totient#prime power#formula

Statement

Show that $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$ for $p$ prime and $k\ge1$ .

Hint

Count integers in $\{1,\ldots,p^k\}$ coprime to $p^k$ .

Show solutionHide solution

Counting. An integer is not coprime to $p^k$ iff it is divisible by $p$ . Among $1,\ldots,p^k$ , there are $p^{k-1}$ multiples of $p$ .

Subtract. $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$ .

Check. $\varphi(8)=4$ (coprimes: $1,3,5,7$ ), matching $2^2\cdot1=4$ .

Conclusion. The formula holds.