Euler's Phi Function and the Chinese Remainder Theorem

$\phi(n)$ is defined to be the number of positive integers less than or equal to $n$ that are relatively prime to $n$.

Proving that for prime $p$, $\phi(p)=p-1$ is trivial, as every positive integer less than a prime is relatively prime to that prime.

Further experimentation suggests that it is also true that $\phi(p^k)=p^k-p^{k-1}$.

This, too, is easily verified by noticing that of the $p^k$ positive integers less than or equal to $p^k$, only the multiples of $p$ are not relatively prime to $p^k$. As there are $p^k/p = p^{k-1}$ of these, $\phi(p^k)$ must be the difference $p^k-p^{k-1}$.

With a little more investigation, we stumble upon a key behavior of $\phi(n)$ -- it is multiplicative in the sense that
$$\phi(mn)=\phi(m)\phi(n) \quad \textrm{ if $m$ and $n$ are relatively prime}$$
We need to prove this, of course. To do so, we apply a counting argument. Basically, our intent is to construct two sets of integers, one with $\phi(mn)$ elements, and another with $\phi(m)\phi(n)$ elements. If we can establish a one to one correspondence between the elements of the two sets, then we will have shown that $\phi(mn)=\phi(m)\phi(n)$.

To this end, consider set $S_1$ defined as follows:
$$S_1 = \{a: 1 \le a \le mn \textrm{ and } \gcd(a,mn) = 1\}$$
So, $S_1$ consists of precisely those positive values less than or equal to $mn$ and relatively prime to $mn$. This, of course, by definition, must have $\phi(mn)$ elements.

Let us also define set $S_2$ as
$$\begin{array}{rlcrcl}
S_2 = \{(b,c): &1 \le b \le m &\textrm{ and }& \gcd(b,m) &=& 1\\
\textrm{and} &1 \le c \le n &\textrm{ and }& \gcd(c,n) &=& 1\}
\end{array}$$

We can count the elements of $S_2$ by considering how the ordered pairs are constructed. We must first choose the first coordinate of the ordered pair, which we can do in $\phi(m)$ ways.
Then, we must choose the second coordinate of the ordered pair, which we can do in $\phi(n)$ ways.

Thus, the total number of ways we could construct an ordered pair in $S_2$ is the product of these two values, $\phi(m)\phi(n)$ ways. It remains to show that there is a one-to-one correspondence between these two sets.

Consider associating any value $(a \mod mn)$ from $S_1$ with the ordered pair $(a \mod m, a\mod n)$ in $S_2$.

For example, if $m=4$ and $n=5$, we have:
$$S_1 = \{1, 3, 7, 9, 11, 13, 17, 19\}$$
$$S_2 = \{(1,1),(1,2),(1,3),(1,4),(3,1),(3,2),(3,3),(3,4)\}$$
and we have the following associations:
$$\begin{array}{ccc}
1 &\rightarrow& (1,1)\\
3 &\rightarrow& (3,3)\\
7 &\rightarrow& (3,2)\\
9 &\rightarrow& (1,4)\\
11 &\rightarrow& (3,1)\\
13 &\rightarrow& (1,3)\\
17 &\rightarrow& (1,2)\\
19 &\rightarrow& (3,4)\\
\end{array}$$

To show these associations are one-to-one, we need to show:

  1. Different numbers in $S_1$ get sent to different pairs in $S_2$
  2. Every pair in $S_2$ is associated with some element of $S_1$

To show the first claim holds, we argue indirectly. Suppose $a_1$ and $a_2$ are distinct elements of $S_1$ and are mapped to the same pair in $S_2$. If this is the case, then $a_1 \equiv a_2 \pmod{m}$ and $a_1 \equiv a_2 \pmod{n}$. But then $m \mid (a_1 - a_2)$ and $n \mid (a_1 - a_2)$. So, recalling that $m$ and $n$ are relatively prime, it must then be the case that $mn \mid (a_1 - a_2)$. Thus $a_1 \equiv a_2\pmod{mn}$, which contradicts the assumption that $a_1$ and $a_2$ were distinct.

To show the second claim holds, we need to show for any $(b,c)$ seen in $S_2$, we can find an $a$ in $S_1$ so that
$$a \equiv b\pmod{m} \quad \textrm{and} \quad a \equiv c\pmod{n}$$
This is best argued by example. Suppose we wish to solve
$$x \equiv 8 \pmod{11} \quad \textrm{and} \quad x \equiv 3\pmod{9}$$
We know from the first congruence that $x=11y+8$. Substituting this into the second gives us
$$11y+8 \equiv 3\pmod{9}$$
or equivalently,
$$11y \equiv -5\pmod{9}$$
We have, of course, solved such things before. If a simpler method does not present itself, we can always solve this via the multiplicative inverse of $11\pmod{9}$ given through the Euclidean Algorithm. For this to work, however, we must have 11 and 9 relatively prime to each other (which they are), as otherwise, no multiplicative inverse exists. In general, however, 11 and 9 are the values $m$ and $n$. Thus we can only be assured we can do this if $\gcd(m,n)=1$.

Proceeding with the example, we find $y \equiv 2\pmod{9}$, which in turn gives as its solution for $x$ the following:
$$x = 11y + 8 = 11(9k+2) + 8 = (11 \cdot 9)k + 30$$
Generalized, this technique results in a proof of the following very important result in number theory:

The Chinese Remainder Theorem
Let m and n be integers where gcd(m,n)=1, and let b and c be any integers. Then the simultaneous congruences
$$x \equiv b\pmod{m} \quad \textrm{and} \quad x \equiv c\pmod{n}$$
have exactly one solution with $0 \le x \lt mn$
.

Armed with this theorem, showing the existence of the $a \in S_1$ previously discussed becomes trivial -- and this, of course, finishes the proof of the multiplicative nature of $\phi$.