Number Theory: In Context and Interactive

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

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\text{.}\) Likewise, any number divisible by \(p\) is not coprime to \(p^e\text{,}\) 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\text{,}\) 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\text{.}\)

Subtract; there are

elements which are coprime.

Take the integers from 1 to \(mn\) and arrange them in an array like so – \(n\) rows, \(m\) columns:

Notice that only some of the columns contain elements of \(U_m\text{,}\) namely, the columns with \(km+\ell\) where \(\gcd(\ell,m)=1\text{.}\) The others necessarily share nontrivial factors with \(m\text{,}\) so we focus on the \(\phi(m)\) columns like this where all elements are coprime to \(m\text{.}\)

Now within each such column, I claim there are all possible classes in \(\mathbb{Z}_n\text{.}\) Why?

• Suppose that two elements of the \(\ell\) column are the same equivalence class. Then \(km+\ell\equiv k'm+\ell\) (mod \(n\)).

• In that case we cancel \(\ell\) to get \(km\equiv k'm\text{,}\) and we can also cancel \(m\text{,}\) since we already know it is coprime to \(n\text{.}\) That leads to \(k\equiv k'\text{.}\)

In particular, each class is only represented once in each column.

That means that each relevant column has exactly \(\phi(n)\) elements in it which are coprime to \(n\) (though which rows these elements are in will depend upon the column). In total we have \(\phi(m)\phi(n)\) of them!

In order to show this, we will take the set \(\{1,2,3,\ldots,n\}\) and partition it into subsets of numbers that each have the same \(\gcd\) with \(n\text{.}\) If we can show there are \(\phi(d)\) numbers having each possible \(\gcd\text{,}\) then that totals up to \(n\text{.}\)

Indeed, the only possibilities for greatest common divisor with \(n\) are the \(k\) various divisors \(\{d_i\}_{i=1}^k\) of \(n\text{,}\) so that each subset corresponds to one of these divisors. Our subsets then look like

Let's look at these sets more carefully. Each one consists of numbers sharing divisor \(d_i\) with \(n\text{.}\) So, if we wanted to, we could divide all the numbers in the \(i\)th set

by their common factor \(d_i\text{.}\)

That new set will be the set of positive numbers \(b\leq \frac{n}{d_i}\) also coprime to \(\frac{n}{d_i}\text{.}\) So the size of the subset of numbers having gcd \(d_i\) with \(n\) is the same as the number of these \(b\) coprime to \(\frac{n}{d_i}\text{.}\)

More precisely, if we look at all the original subsets in question, they have the same sizes as the following sets:

These new sets \(\{b\in\mathbb{Z}\mid 1\leq b\leq n/d_i,\; \gcd(b,n/d_i)=1\}\) themselves are different from before (and possible not disjoint). But their sizes (or cardinalities) are the same as before, and the old sets were all disjoint, so we conclude that

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\text{,}\) so we can rewrite the sum as desired!