NTIC Proofs and Reasons

Section 9.5 Proofs and Reasons

In this text, we try to strike a balance 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 a good proof, the techniques will not just prove that things are true, but lend insight into why they are true. The proofs here have this trait.

🔗

Subsection 9.5.1 Computing prime powers

🔗

With some effort above, you should have seen a pattern for

$\phi(p^e)\text{.}$ Let's prove this.

🔗

Fact 9.5.1.

$\begin{equation*} \phi(p^e)=p^e-p^{e-1}=\left[1-\frac{1}{p}\right]p^e \end{equation*}$

🔗

Proof.

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

\begin{equation*} p^e-p^{e-1} \end{equation*}

elements which are coprime.

🔗

Subsection 9.5.2 Multiplicativity

🔗

The most interesting proof is that of the following fact¹We use a standard proof such as in [C.2.4] or [C.2.1]; it is also possible to use Fact 9.5.4 and Proposition 23.4.11 as in [C.2.13] or [C.5.1], but for this particular function this strategy seems more illuminating. about

$\phi$ applied to certain products. Later (Definition 18.1.2) we will see this has proved that

$\phi$ is multiplicative.

🔗

Fact 9.5.2.

If $\gcd(m,n)=1\text{,}$ then $\phi(mn)=\phi(m)\cdot\phi(n)\text{.}$

🔗

Proof.

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*}

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, the 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!

🔗

Example 9.5.3.

It can be easier to see with an example, say $n=15\text{.}$ Try the following interact if you are online. The elements that are units modulo $mn$ are marked with exclamation points.

xxxxxxxxxx
 
@interact
def _(m=(5,[2..10]),n=(3,[2..10])):
    T = [['$[%s]$'%i for i in [1..m]]]
    for k in range(n):
        t = []
        for i in [1+k*m..m+k*m]:
            if gcd(i,m*n)==1:
                t.append('$%s$ !'%i)
            else:
                t.append('$%s$'%i)
        T.append(t)
    pretty_print(html(table(T, header_row=True, frame=True)))

Warning! 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 or the right places for the proof.

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

🔗

Subsection 9.5.3 Addition Formula

🔗

If you were diligent in your exploration, you will have discovered that

$\begin{equation*} \sum_{d\mid n} \phi(d)=n\text{.} \end{equation*}$

🔗

We will prove this carefully, using subsets. We will gain insight of a combinatorial nature – that there are two ways to count

$n\text{,}$ one of which is precisely about finding numbers coprime to divisors of

$n\text{.}$

🔗

To really understand this proof, it is best to follow along with

$n=15\text{.}$

🔗

Fact 9.5.4.

$\begin{equation*} \sum_{d\mid n} \phi(d)=n \end{equation*}$

🔗

Proof.

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

\begin{equation*} \{a\in\mathbb{Z}\mid 0\leq a\leq n-1,\; \gcd(a,n)=1=d_0\},\ldots \end{equation*}

\begin{equation*} \{a\in\mathbb{Z}\mid 0\leq a\leq n-1,\; \gcd(a,n)=1=d_k\}\text{.} \end{equation*}

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

\begin{equation*} \{a\in\mathbb{Z}\mid 0\leq a\leq n-1,\;\gcd(a,n)=d_i\} \end{equation*}

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 count 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, indexed starting at $1$ instead of $0$ for convenience:

\begin{equation*} \{b\in\mathbb{Z}\mid 1\leq b\leq n/1,\; \gcd(b,n/1)=1\},\ldots \end{equation*}

\begin{equation*} \{b\in\mathbb{Z}\mid 1\leq b\leq n/n,\; \gcd(b,n/n)=\gcd(b,1)=1\}\text{.} \end{equation*}

The old sets were all disjoint, so even though these new sets $\{b\in\mathbb{Z}\mid 1\leq b\leq n/d_i,\; \gcd(b,n/d_i)=1\}$ themselves are different (and possible not disjoint), 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)\text{.} \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\text{,}$ so we can rewrite the sum as desired!

\begin{equation*} n=\sum_{d\mid n} \phi(d) \end{equation*}

🔗

Some readers will want to know this will be revisited in a far more sophisticated way in Example 23.2.4.

🔗

Subsection 9.5.4 Even more questions

🔗

There are lots of other interesting questions to tackle. Go back to the beginning of Section 9.4 and look at some of the questions you didn't yet explore. You now have the tools you need to tackle such questions, and even to prove things about them. The structure of

$\phi$ is very regular!