Prove that for all primes p: $φ(p^i)$= $p^i$ - $p^{i-1}$
I found a proof on the wikipedia article of the Euler's totient function. But I cannot understand it, as it's been many years since I dealed with math and proves. Is there maybe a longer explanation somewhere, or can you explain it in detail?
On
This is the simplest way that I can think of.
The numbers which are not coprime to $p^i$ are $\{p,2p,...,(p-1)p,p^2,2p^2,...,(p-1)p^2,p^3,2p^3,...,p^{i-1},2p^{i-1},...,(p-1)p^{i-1},p^i\}$.
Now, since $p=p\cdot 1$ and $p^i=p\cdot p^{i-1}$ we have $p^{i-1}$ numbers which are not coprime to $p^i$.
The number of numbers which are coprime to $p^i$ is the number of all numbers in the set $\{1,2,...,p^i\}$ minus the number of numbers which are not coprime to $p^i$ so the number is $\phi(p^i)=p^i-p^{i-1}$.
A number is coprime to $p^i$ iff it is coprime to $p$: that is, not a multiple of $p$.
How many things are not multiples of $p$, below $p^i$? It's $p^i - k$ where $k$ is the number of things less than or equal to $p^i$ which are multiples of $p$.
What is $k$, then? $p$ is a multiple of $p$; $2p$ is also; …; $p^i-p$ is, and so is $p^i$. How many of these things were there? If we divide every member of the set $\{ p, 2p, \dots, p^i - p, p^i \}$ by $p$, we get $\{ 1, 2, \dots, p^{i-1} \}$. So there are clearly $p^{i-1}$ things less than or equal to $p^i$ which are multiples of $p$.
Therefore $k = p^{i-1}$, so the number we seek is $p^i - p^{i-1}$.
More compactly stated, we seek $\mid \{ n \leq p^i : (p, n) = 1 \} \mid$, which we calculate as $\mid \{ n : 1 \leq n \leq p^i \} \setminus \{ n \leq p^i : (p, n) = p \} \mid$.