With some effort, you should have seen the pattern that \[\phi(p^e)=p^e-p^{e-1}=\left[1-\frac{1}{p}\right]p^e\; .\] Let's prove this:

• Remember, we want the number of positive numbers (!) coprime to \(p^e\) and less than \(p^e\).
• Any number which is not coprime to \(p^e\) must share a prime factor, which must be \(p\).
• Any number divisible by \(p\) is not coprime to \(p^e\), so this is a necessary and sufficient condition. Now we just need to count these.
• But all the numbers less than or equal to \(p^e\) which have a factor of \(p\) are just the multiples of \(p\), which occur every \(p\)th element.
• Since \(p^e\) itself is the \(p^{e-1}\)th such multiple, there are exactly \(p^{e-1}\) such integers not coprime to \(p^e\), so there are \[p^e-p^{e-1}\] which are coprime.

The most interesting proof will be the proof that \(\phi\) is multiplicative, a term which subsumes the fact that \[\phi(mn)=\phi(m)\cdot\phi(n)\text{ IF }\gcd(m,n)=1\; .\]

• Take the integers from 1 to \(mn\) and arrange them in an array like so – \(n\) rows, \(m\) columns: \[\begin{matrix}1 & 2 & 3 & \dots & m \\m+1 & m+2 & m+3 & \dots & 2m\\\vdots & \vdots & \vdots & \ddots & \vdots\\(n-1)m+1 & (n-1)m+2 & (n-1)m+3 & \dots & nm\end{matrix}\]
• Now notice that only some of the columns correspond to elements of \(U_m\). Namely, the columns with \(km+\ell\) where \(gcd(\ell,m)=1\) correspond. The others cannot have elements coprime to \(m\).
• Thus there are \(\phi(m)\) columns like this where all elements are coprime to \(m\); we focus on these.
• Now we look at the other direction, rows. Within each such column, there are all possible classes in \(\mathbb{Z}_n\).
  • Why? Suppose that two elements of the \(\ell\) column are the same equivalence class.
  • Then \(km+\ell\equiv k'm+\ell\) mod (\(n\)).
  • And then \(km\equiv k'm\) and we can cancel \(m\), since we already know it is coprime to \(n\).
  • That leads to \(k\equiv k'\), so they are in the same row as well as the same column (hence, the same element).
• That means that each relevant column has exactly \(\phi(n)\) elements in it which are coprime to \(n\), so that we get \(\phi(m)\phi(n)\) in total!

There are lots of other interesting questions to tackle.

• Given \(m\), for how many integers \(n\) is it true that \(\phi(n)=m\)? Are there infinitely many, for instance?
• Are there infinitely many \(n\) for which \(\phi(n)\) ends in zero?
• When does \(\phi(m)\) divide \(\phi(n)\)?

You now have the tools you need to tackle such questions. The structure of \(\phi\) is very regular!