Section9.5Proofs and reasons

We try to strike a balance here between exploration and proof. The point is that number theory is both of these things. Exploration is wonderful, but we will see a number of times where we really do need the proof to avoid error. Nonetheless, do not start this section before really trying things!

In particular, the techniques will not just prove that things are true, but lend insight into why they are true. The proofs here have this trait.

Subsection9.5.1Computing prime powers

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.

Subsection9.5.2Multiplicativity

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!

Example9.5.1

It can be easier to see with an example, say \(n=15\).

The actual units modulo \(mn\) are marked with exclamation points. If you pick an \(m\) and \(n\) which aren't coprime, you'll see how the exclamation points don't come in the right amounts.

Again, since there are \(\phi(m)\) columns with \(\phi(n)\) elements in them, all coprime to both \(m\) and \(n\), that means there are \(\phi(m)\phi(n)\) elements coprime to \(mn\), which proves what we wanted.

Subsection9.5.3Even more questions

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)\)?
We can try them out.

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