Question about proving $\phi(mn) = \phi(m)\phi(n)$

Question

The textbook I am reading (A Friendly Introduction to Number Theory) is proving that when $m$ and $n$ are coprime $ \phi(mn) = \phi(m)\phi(n)$ by defining two sets:

1. All of the numbers a where $a$ and $mn$ are coprime (where $1 \le a < mn$)
2. All pairs of numbers (b, c) where $b$ and $m$ are coprime and $c$ and $n$ are coprime ($1 \le b < m$ and $1 \le c < n$)

Image of textbook

Image of textbook

and then proving that their sizes are equal.

It does this in two steps:

1. "Different numbers in the first set get sent to different pairs in the second set."
2. "Every pair in the second set is hit by some number in the first set."

The second part is the one I don't understand. To prove it, the book just defines the Chinese Remainder Theorem and declares the proof complete. But as far as I understand, the Chinese Remainder Theorem defines a bijection between $\mathbb Z_{pq}$ and $\mathbb Z_p \times \mathbb Z_q$, and not the two sets they've defined above.

How is it proven that the number "hit" in the second set actually came from the first set and not some other element in $\mathbb Z_{pq}$ ?

Image of textbook

Answer 1

Elementary Proof

Let $p$ and $q$ be coprime. The Chinese remainder theorem defines a bijection $\psi:\mathbb{Z}_p\times\mathbb{Z}_q\rightarrow\mathbb{Z}_{pq}$ given by $\psi(a,b)=qa+pb\pmod{pq}$. The crux, and missing detail of the proof in your book is that (LEMMA) for any $(a,b)\in\mathbb{Z}_p\times\mathbb{Z}_q$, we have that $\gcd(qa+pb,pq)=1$ iff $\gcd(a,p)=\gcd(b,q)=1$. This lemma eqivalently tells us that $\psi$ restricts to a bijection between from the set $\{(a,b)\in\mathbb{Z}_a\times\mathbb{Z}_b:\gcd(a,q)=\gcd(b,p)=1\}$ to the set $\{c\in\mathbb{Z}_{pq}:\gcd(c,pq)=1\}$, and thus that $\varphi(p)\varphi(q)=\varphi(pq)$. We prove this lemma below.

First, we prove $(\Rightarrow)$. Let $\gcd(qa+pb,pq)=1$, then if $n$ is a divisor of both $a$ and $p$, it must also divide $qa+pb$ and $pq$, so $n$ would have to divide $\gcd(qa+pb,pq)=1$, meaning that $n=1$. Since the only natural $n$ that divides both $a$ and $p$ is $n=1$, then $\gcd(a,p)=1$. We can repeat this same argument to show that $\gcd(b,q)=1$.

We now prove $(\Leftarrow)$. Let $\gcd(a,p)=\gcd(b,q)=1$. Since $q,a$ are both coprime to $p$ and $p,b$ are both coprime to $q$, then $\gcd(qa,p)=\gcd(pb,q)=1$. Since $p,q$ are coprime, then \begin{equation} \begin{split} \gcd(qa+pb,pq)&=\gcd(qa+pb,p)\gcd(qa+pb,q)\\ &=\gcd(qa,p)\gcd(pb,q)\\ &=1 \end{split} \end{equation} by the properties of the $\gcd$. This completes our proof of the lemma.

More Abstract Proof

Let's first define a useful concept. For any ring $R$, we may define $R^\times$ to be the set of units (elements with an inverse) of $R$; this is in fact a group under the multiplication operator inherited from $R$, and is known as the unit group of $R$.

It is not hard to see that the units of $\mathbb{Z}_n$ are simply the elements $[k]\in\mathbb{Z}_n$ such that $k$ is coprime to $n$. In other words, $|\mathbb{Z}_n^\times|=\varphi(n)$.

Now, the Chinese remainder theorem tells us that if $p,q$ are coprime, then there exists a ring isomorphism $\psi:\mathbb{Z}_{pq}\rightarrow\mathbb{Z}_p\times\mathbb{Z}_q$. Since $\psi$ is a ring isomorphism, then it must also restrict to a group isomorphism $\mathbb{Z}_{pq}^\times\rightarrow(\mathbb{Z}_p\times\mathbb{Z}_q)^\times$. Combining this with the fact that $(\mathbb{Z}_p\times\mathbb{Z}_q)^\times\cong\mathbb{Z}_p^\times\times\mathbb{Z}_q^\times$, we have that $\mathbb{Z}_{pq}^\times\cong\mathbb{Z}_p^\times\times\mathbb{Z}_q^\times$, and thus \begin{equation} \varphi(pq)=|\mathbb{Z}_{pq}^\times|=|\mathbb{Z}_p^\times|\cdot|\mathbb{Z}_q^\times|=\varphi(p)\varphi(q) \end{equation} as desired.

Answer 2

Your critique is correct. Silverman's proof has a gap: it doesn't prove the bijection restricts to the sets of coprimes, i.e. that the coprimality constraints are preserved. But the gap is easily filled via

$\qquad\color{#c00}{\rm L1}\!:\ \ \ (a,mn)\! =\! 1\iff (a,m)\! =\! 1 \!=\! (a,n).\ $ Proof

$\qquad\color{#0a0}{\rm L2}\!:\ \ \ j\equiv k\pmod{\! n}\Rightarrow (j,n) = (k,n).\qquad $Proof

In step $1\!:\ $ $a\in {\rm set_1}\!\Rightarrow (a,mn)\!=\!1 \overset{\rm\color{#c00}{L1}}\Rightarrow 1\!=\!(a,m)\overset{\rm\color{#0a0}{L2}}=(a\bmod m,m);\;$ by $\,m\leftrightarrow n\,$ symmetry this also yields $\,(a\bmod n,n)\!=\!1,\,$ so $\,(a\bmod m,\,a\bmod n) \in {\rm set}_2$

In step $2\!:\ $ if $\,(b,c) \in {\rm set_2}$ then by CRT there is $\,1\le a < mn\,$ with $\,\begin{align}&a\equiv b\!\!\!\pmod{\! m}\\ &a\equiv c\!\!\!\pmod{\! n}\end{align}\,$ so $\,(a,m)\overset{\rm\color{#0a0}{L2}}=(b,m)\!=\!1\!=\!(c,n)\overset{\rm\color{#0a0}{L2}}=\!(a,n)\overset{\rm\color{#c00}{L1}}\Rightarrow (a,mn)\!=\!1\Rightarrow a \in {\rm set}_1$

Remark $ $ As explained in the linked proof, an arithmetically conceptual way to view Lemma $\rm\color{#c00}{L1}$ is via the obvious fact that units (invertibles) $\!\bmod n\,$ are clearly preserved under products and divisors (vs. the common brute-force computational Bezout-based proof that is - alas - usually unmotivated, i.e. pulled out of a hat like magic).

The innate arithmetical structure at the heart of the matter will be better understood structurally when one learns the ring-theoretic view of CRT in terms of product rings, where the above becomes $$(m,n)=1\Rightarrow \Bbb Z_{mn}\cong \Bbb Z_m\times \Bbb Z_n\,\Rightarrow\, U(\Bbb Z_{mn})\cong U(\Bbb Z_m)\times U(\Bbb Z_n)\qquad$$ where $U(R)$ denote the group of units (invertibles) of the ring $R.\,$ But this is far beyond the level of Silverman's book (which never uses any ring theory).