Chinese Reminder Theorem and Euler's Totient Function

Chinese Remainder Theorem

Theorem (CRT).
If $n_1, n_2, \dots, n_k \in \mathbb{N}$ are pairwise coprime, then for any $a_1, a_2, \dots, a_k \in \mathbb{N}$, there exists an integer $x$ such that

$$\begin{aligned} x &\equiv a_1 \pmod{n_1}, \\ x &\equiv a_2 \pmod{n_2}, \\ &\;\;\vdots \\ x &\equiv a_k \pmod{n_k}. \end{aligned}$$

Proof One

For each $i \in [k]$, define

Clearly, $n_j \mid N_i$ for every $j \neq i$. Moreover, $\gcd(N_i, n_i) = 1$. Hence, there exists $M_i \in [1, n_i - 1]$ such that

It follows that

Therefore,

is a solution. In fact, for any $\ell \in \mathbb{Z}$,

is also a solution. ∎

Proof Two (More Intuitive)

Consider a simple example with moduli $2$ and $3$:

There is a one-to-one correspondence between numbers in $\{0,1,2,3,4,5\}$ and pairs in $\{0,1\} \times \{0,1,2\}$.

In general, if $n_1, n_2, \dots, n_k$ are pairwise coprime, then for any $x,y \in [0, \ldots, -1 + \prod_j n_j]$, if

then $x = y$.

To see this, since $n_j \mid (y-x)$ for all $j$. Therefore, $y - x$ is a common multiple of $n_j, j \in [k]$. Consider the set

It is easy to see each element in this set is a multiple of the minimum one in this set, which is the least common multiple of the $n_j$, $\forall j \in [k]$. Since the $n_j$’s are coprime, it follows that the least common multiple is $\prod_j n_j$ and

But since $x,y \in [0, \ldots, -1 + \prod_j n_j]$, we must have $x=y$.

Thus, there is a one-to-one correspondence between $[0, \ldots, -1 + \prod_j n_j]$ and the Cartesian product $[n_1] \times [n_2] \times \cdots \times [n_k]$.

$\square$

Corollary

There is a unique solution in $[0, \ldots, -1 + \prod_j n_j]$.

Proof. Suppose $x$ and $y$ are two solutions. Then for every $i \in [k]$,

Thus, $x-y$ is divisible by $\prod_{i=1}^k n_i$. Therefore,

for some $\ell$, so the difference between two solutions is at least $\prod_{i=1}^k n_i$. Hence there is exactly one solution modulo $\prod_{i=1}^k n_i$. ∎

Euler's Totient Function

The Chinese Remainder Theorem has many interesting applications. Here are a few:

Theorem 1.
Let $\varphi(n)$ denote Euler’s totient function, i.e., the number of integers in $[0, \ldots, n - 1]$ that are coprime to $n$. If $n = pq$ for primes $p$ and $q$, then

$$\varphi(n) = (p-1)(q-1).$$

Proof. By the CRT, there is a one-to-one correspondence between $[0, \ldots, n - 1]$ and $[0, \ldots, p - 1] \times [0, \ldots, q - 1]$. If $x \in [0, \ldots, n - 1]$ is not coprime to $n$, then either $p \mid x$ or $q \mid x$. Thus, $x$ corresponds to a pair of the form $(0,a)$ or $(b,0)$ for some $a \in [0, \ldots, q - 1]$, $b \in [0, \ldots, p - 1]$. The number of such pairs is

Hence,

∎

Theorem 2.
If $n = pq$ for coprime integers $p,q > 1$, then

$$\varphi(n) = \varphi(p)\varphi(q).$$

Proof. By Chinese Reminder Theorem, there is a one-to-one correspondence between $[0, \ldots, n - 1]$ and $[0, \ldots, p - 1] \times [0, \ldots, q - 1]$. An integer $x \in [0, \ldots, n - 1]$ is coprime to $n$ if and only if $\gcd(x,p)=1$ and $\gcd(x,q)=1$. Thus, $x$ corresponds to a pair $(x \bmod p, x \bmod q)$ where each component is coprime to its modulus. There are $\varphi(p)$ possibilities for the first component and $\varphi(q)$ for the second, so

∎

Theorem 3.
Let $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$ be the prime factorization of $n$. Then

$$\varphi(n) = n \prod_{i=1}^m \left(1 - \frac{1}{p_i}\right).$$

Proof. By multiplicativity (Theorem 2),

For $p^k$, the multiples of $p$ in $[p^k]$ are

a total of $p^{k-1}$ numbers. Thus,

Therefore,

∎