What we want is the number of positive numbers (!) coprime to \(p^e\) and less than \(p^e\).

The most important point is that any number which is not coprime to \(p^e\) must share a prime factor with it, which must be \(p\). Likewise, 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 numbers. 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\).

Subtract; there are \begin{equation*}p^e-p^{e-1}\end{equation*} element which are coprime.

Take the integers from 1 to \(mn\) and arrange them in an array like so – \(n\) rows, \(m\) columns: \begin{equation*}\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}\end{equation*}

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!

In order to show this, we will take \(\{1,2,3,\ldots,n\}\) and divide it up into subsets with different \(\gcd\) with \(n\). This will total up to \(n\) different possibilities, and there will be \(\phi(d)\) different possibilities for each possibly \(\gcd\).

Indeed, the only possibilities for greatest common divisor with \(n\) are the various divisors \(d\) of \(n\), which we will call \(\{d\mid n\}\), so each subset corresponds to one of these. So our sets look like \begin{equation*}\{a\mid \gcd(a,n)=1=d_0\},\;\{a\mid \gcd(a,n)=d_1\},\ldots,\{a\mid \gcd(a,n)=n=d_k\}\, .\end{equation*}

Let's look at these sets more carefully.

• Each one consists of numbers sharing divisor \(d_i\) with \(n\). So, if we wanted to, we could divide all the numbers in the \(i\)th set by \(d_i\).

• That new set will be the set of numbers \(1\leq b\leq \frac{n}{d_i}\) coprime to \(\frac{n}{d_i}\).

• So the size of the set of numbers with gcd \(d_i\) with \(n\) is the same as the number of things coprime to \(\frac{n}{d_i}\).

More precisely, if we look at all the sets in question, they are the same in size as these sets: \begin{equation*}\{b\mid \gcd(b,n/1)=1\},\;\{b\mid \gcd(b,n/d_1)=1\},\ldots,\{b\mid \gcd(b,1)=1\}\, .\end{equation*} The old sets were all disjoint, so even though these new sets themselves are different, their sizes (or cardinalities) are the same as before. So \begin{equation*}n=\phi(n)+\phi(n/d_1)+\phi(n/d_2)+\cdots+\phi(1)\, .\end{equation*}

But the set of numbers \(\frac{n}{d_i}\) for all divisors \(d_i\) of \(n\) is also the set of all divisors of \(n\)! So we can rewrite the sum as desired, \begin{equation*}n=\sum_{d\mid n} \phi(d)\end{equation*}