Is there a better way to explain why $\phi \left ( p^k \right ) = p^k - p^{k-1}$?

Question

Let $p$ be a prime number and $k$ be some positive integer, and $\phi(n)$ be the Euler Phi Function, which counts the cardinality of the set of integers coprime and less than $n$. We wish to find $\phi \left (p^k \right )$.

My approach:

First have the naive answer $p^k-1$, and then take away the multiples of $p$. There must be $p^{k-1}-1$ multiples of $p$ from $0$ to $p^k-1$. We show this below.

We have $p, 2p, 3p, ... , p^{k-1}p$, which yields $p^{k-1}$ multiples of $p$. But since the last one $p^{k-1}p$ is greater than $p^k-1$, we manually take that case away, leaving us with $p^{k-1}-1$ multiples of $p$, which is what we wanted.

Hence, $\phi \left (p^k \right ) = (p^k-1) - \left (p^{k-1} - 1 \right ) = p^k - p^{k-1}.$

But this seems like a roundabout way of acquiring the result, given how neat it is. This leads me to believe that there is a simpler explanation that yields the same result.

If it exists, what is that 'simpler explanation'?

Answer 1

I think your explanation is the simplest. Here's another way to look at it that may provide a different kind of intuition. Factor out $p^k$ to get $$ \phi(p^k) = p^k \left( 1 - \frac{1}{p} \right) $$ which tells you to throw out the fraction of the numbers less than $p^k$ that are divisible by $p$.

Answer 2

It might be tough to exactly know what "simpler" may mean here... and for whom, anyway you can argue as follows:

There are exactly $\;p\;$ multiples of $\;p\;$ such that $\;mp^s\le m<(m+1)p^s\;$ , for any two consecutive multiples of $\;p\;$ between $\;1\;$ and $\;p^k\;$ , which are:

$$mp^s,\,mp^s+p,\,mp^2+2p,\,\ldots,\,mp^2+(p-1)p=(m+1)p^2-p$$

with the rightmost number being the maximal such multiple that still is less than $\;(m+1)p^s\;$

Thus: strictly between $\;1\;$ and $\;p^k\;$ there are$\;k-1\;$ powers of $\;p\,:\;p,\, p^2,...,p^{k-1}\;$ , and between each two consecutive such powers there are $\;p\;$ multiples (counting only left endpoints in each interval).

All in all, we have $\;p^{k-1}\;$ numbers as above, which are exactly all the numbers between $\;1\;$ and $\;p^k\;$ that are not coprime with $\;p^k\;$ , and thus there are $\;p^k-p^{k-1}=p^{k-1}(p-1)\;$ coprime numbers between $\;1\;$ and $\;p^k\;$ .

Answer 3

Maybe not "simpler" but a little bit cleaner:

We know that $\varphi(p^k) = |\Bbb Z_{p^k}^*|=|\{a \in \Bbb Z_{p^k} \mid \gcd(p^k,a)=1\}|$. But we can rewrite this as:

$$\varphi(p^k) = |\Bbb Z_{p^k}| - |\Bbb Z_{p^k} \setminus \Bbb Z_{p^k}^*| = p^k - |\{a \in \Bbb Z_{p^k} \mid \gcd(p^k,a) \neq 1 \iff p \mid a\}|$$

How many elements are contained in $|\Bbb Z_{p^k} \setminus \Bbb Z_{p^k}^*|$? These are the elements $a \in \Bbb Z_{p^k}$, so $1\leq a \leq p^k$, which are divided by $p$, so $a = q \cdot p$ for some $q \in \Bbb Z\setminus\{0\}$. This implies

$$p \leq q \cdot p \leq p^k \iff 1 \leq q \leq p^{k-1}$$

So there are $p^{k-1}$ elements in $|\Bbb Z_{p^k} \setminus \Bbb Z_{p^k}^*|$, namely all the multiples of $p$ smaller or equal to $p^k$. Hence we obtain

$$\varphi(p^k) = |\Bbb Z_{p^k}| - |\Bbb Z_{p^k} \setminus \Bbb Z_{p^k}^*| = p^k - p^{k-1}.$$

Note that I choose $p^k$ to be the representative of the remainder class $\bar{0}$ in $\Bbb Z_{p^k}$.