Definitions of the Chinese Remainder Theorem

Question

The Chinese Remainder Theorem can be stated in a few ways:

(i) If $N = N_1N_2\cdots N_k$ and the $N_i$ are pairwise coprime we have a canonical isomorphism $$\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/N_1\mathbb{Z} \oplus \cdots \oplus \mathbb{Z}/N_k\mathbb{Z}$$ (ii) For any $a_i \bmod N_i, \quad i = 1,\ldots, k$ there exists an $a$ such that $a \equiv a_i \bmod N_i$ for all $i$.

My question is how are these definitions equivalent and how is the isomorphism in the first definition true?

Also, the value of $a$ can be found via the Euclidean Algorithm. That is, put $M_i = N/N_i$. By assumption $M_i$ and $N_i$ are relatively prime. Then find $X_i$ with $X_iM_i \equiv 1 \bmod N_i$ and put $$a = \sum_{i=1}^k a_iX_iM_i$$

I am also confused how this uses the euclidean algorithm and finds the value of $a$.

Answer 1

Very simple if you observe $M_i\equiv 0\mod N_j$ for all $j\ne i$. So this value for $a$ satisfies $$a\bmod N_j =\sum_{i+1}^k (a_i X_iM_i \bmod N_j)=a_jX_jM_j\bmod N_j=a_j\bmod N_j.$$

Finding the inverse $X_i$ of $M_i$ modulo $N_i$ is done through the Extended Euclidean algorithm, which yields the coefficients $X_i$ and $Y_i$ of a Bézout's relation between $M_i$ and $N_i$: $$X_iM_i+Y_iN_i=1.$$My answer to this question shows how it works in practice.

Why the isomorphism?

There's a natural map: \begin{align*} \varphi\colon \mathbf Z&\longrightarrow \mathbf Z/N_1\mathbf Z\times\dots\times\mathbf Z/N_k\mathbf Z\\x&\longmapsto(x\bmod N_1,\dots, x\bmod N_k)\end{align*} and its kernel is $N_1\mathbf Z\cap\dots\cap N_k\mathbf Z=N\mathbf Z\;$ because the $N_i$s are pairwise coprime. So we have an injective map $$\overline\varphi\colon \mathbf Z/N\mathbf Z\longrightarrow \mathbf Z/N_1\mathbf Z\times\dots\times \mathbf Z/N_k\mathbf Z.$$ Now, condition (ii) says $\varphi$, hence $\overline \varphi$, is surjective, hence an isomorphism.

Answer 2

To get a decent proof, we need to be a bit more formal.

Suppose $N_0 = \prod_{i=1}^k N_i$ where the $N_i$ are pairwise coprime.

Notationally, we will define $a..b$ to be the set $\{a, a+1, a+2, \dots, b\}$

Define $[n]_i = \{x \in \mathbb Z : x \equiv n \pmod{N_i} \}$. Then $\mathbb{Z}_{N_i} = \{ [n]_i : n \in \mathbb Z\}$.

Theorem. Define $f:\mathbb{Z}_{N_0} \to \bigoplus_{i=1}^k \mathbb{Z}_{N_i}$ by $f([x]_0) = ([x]_1, [x]_2, \dots, [x]_k)$. Then $f$ is an isomorphism.

Proof.

The proof that $f$ is a well-defined homomorphism can be found in just about any good group theory text. We will skip that because I am too lazy to type the whole thing out.

For $i = 1..k$, define $e_k \in \prod_{i=1}^k N_i$ by
$e_1 = ([1]_1, [0]_2, \dots, [0]_k)$
$e_2 = ([0]_1, [1]_2, \dots, [0]_k)$
$\phantom{e_8}\;\;\vdots$
$e_k = ([0]_1, [0]_2, \dots, [1]_k)$

We will show that, for $i \in 1..k$, there exists an $m_i \in \mathbb Z$ such that $f([m_i]_0) = e_i$.

We start by defining $M_1 = \dfrac{N_0}{N_1}$ Note that, for $i \in 2..k$, $M_i \equiv 0 \pmod{N_i}$. This means that $f([M_1]_0) = ([M_1]_1, [0]_2, \dots, [0]_k)$.

Also, since the $N_i$ are relatively prime, $\gcd(M_1,N_1) = 1$. So there exists an $X_1 \in \mathbb Z$ such that $X_1 M_1 \equiv 1 \pmod{N_1}$. Let $m_1 = X_1 M_1$. It follows that $f([m_1]_0) = ([1]_1, [0]_2, \dots, [0]_k)$.

Using the same reasoning but changing the things that need to be changed, it follows that for $i \in 1..k$, there exists an $m_i \in \mathbb Z$ such that $f([m_i]_0) = e_i$.

Now it's pretty easy to show that $f$ is onto. Let $([a_1]_1, [a_2]_2, \dots, [a_k]_k) \in \bigoplus_{i=1}^k \mathbb{Z}_{N_i}$. Define $a = a_1 m_1 + a_2 m_2 + \cdots + a_k m_k$. Because $f$ is a homomorphism,

\begin{align} f([a]_0) &= f\left( \left[\sum_{i=1}^k a_i m_i \right]_0 \right) \\ &= \sum_{i=1}^k f\left( [a_i m_i]_0 \right) \\ &= \sum_{i=1}^k a_i f\left([m_i]_0 \right) \\ &= \sum_{i=1}^k a_i e_i \\ &= ([a_1]_1, [a_2]_2, \dots, [a_k]_k) \end{align}

So $f$ is onto. Since $|\mathbb Z_{N_0}| = |\bigoplus_{i=1}^k \mathbb{Z}_{N_i}| = N_0$. It follows that $f$ must also be one-to-one.

Answer 3

If, for a prime $p$, $p^{\alpha_i}|m_i$, with $\alpha_i$ being the largest exponent with that property, then $p^{\alpha}|\operatorname{lcm}(m_1,m_2,\dots,m_k)$, where $\alpha=\max\{\alpha_i\}$. Similarly, the greatest common divisor of several numbers is the product of the largest powers of the primes that divide all the given numbers.

Associativity allows one to proceed a step at a time with an inductive argument without putting all eggs into a basket at once. Jumping at the opportunity I'll prove the most basic case of $k=2$.

Theorem 1 : Two simultaneous congruences $$\left\{\begin{array}{cccc}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 & (\mod m_2)\end{array}\right.$$ are only solvable when $n_1\equiv n_2 \ (\mod gcd(m_1,m_2))$. The solution is unique modulo $lcm(m_1,m_2)$. (When $m_1$ and $m_2$ are coprime their gcd is $1$. By convention, $a\equiv b\ (\mod 1)$ holds for any integers $a$ and $b$.)

Proof: By a generalization of Euclid's algorithm, there are integers $s$ and $t$ such that $$tm_1+sm_2=gcd(m_1,m_2).$$ Since $n_2−n_1\equiv 0 \ (\mod gcd(m_1,m_2))$, for some $t'$ and $s'$, $$t'm_1+s'm_2=n_2−n_1.$$ Then $n=t'm_1+n_1=−s'm_2+n_2$ satisfies both congruences in the theorem. This proves the existence of a solution.

To prove the uniqueness part, assume $n$ and $N$ satisfy the two congruences. Taking the differences we see that $N−n\equiv 0 \ (\mod m1)$ and $N−n\equiv 0\ (\mod m_2)$, which implies $N−n\equiv 0 \ (\mod lcm(m_1,m_2))$.

As was previously stated, a more general theorem can now be proved by induction.

Theorem 2 : The simultaneous congruences $$\left\{\begin{array}{cccc}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 & (\mod m_2) \\ & & \vdots & \\ n & \equiv & n_k & (\mod m_k)\end{array}\right.$$ are only solvable when $n_i=n_j \ (\mod gcd(m_i,m_j))$, for all $i$ and $j$, $i\neq j$. The solution is unique $\mod lcm(m_1,m_2,\dots,m_k)$.

Proof : Theorem 1 serves the initial step verification. Assume the theorem holds for $k$ congruences and consider $k+1$ of them.

$$\left\{\begin{array}{cccc}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 & (\mod m_2) \\ & & \vdots & \\ n & \equiv & n_k & (\mod m_k) \\ n & \equiv & n_{k+1} & (\mod m_{k+1})\end{array}\right.$$

Let $s$ be a solution of the first $k$ equations. Then the congruence $n\equiv s \ (\ mod lcm(m_1,m_2,\dots,m_k))$ has a solution. (Observe that every solution of the latter also satisfies the first $k$ congruences.) To be able to apply the already proven Theorem 1, we need to show that $$s\equiv n_k+1 (mod gcd(lcm(m_1,\dots,m_k),m_{k+1})).$$ Let's write $g_u=gcd(m_,m_{k+1})$, $u=1,\dots,k$. Then we know that $n_u \equiv n_{k+1}\ (\mod g_u)$ for these values of u. But $n_u=s+t_um_u$, for some $t_u$, implying $n_{k+1}=s+t_um_u\ (\mod g_u)$ so that

$$s=n_{k+1} \ (\mod g_u), u=1,2,\dots ,k.$$

If so,

\begin{align} s & \equiv n_{k+1} \ (\mod lcm(g_1,\dots,g_k))\\ & \equiv n_{k+1}\ (\mod lcm(gcd(m_1,m_{k+1}),\dots ,gcd(m_k,m_{k+1}))) \\ & \equiv n_{k+1}\ (\mod gcd(lcm(m1,…,mk),mk+1)),\end{align}

because $lcm(gcd(m_1,m_{k+1}), \dots,gcd(m_k,m_{k+1})) =gcd(lcm(m_1,\dots,m_k),m_{k+1})$. Thus the system

$$\left\{\begin{array}{cccl}n & \equiv & s & (\mod lcm(m_1,m_2,\dots,m_k)) \\ n & \equiv & n_{k+1} & (\mod m_{k+1})\end{array}\right.$$

has a solution which is unique modulo $lcm(lcm(m_1,m_2,\dots,m_k),m_{k+1})=lcm(m_1,m_2,\dots,m_k,m_{k+1})$.

It also satisfies the whole set of $k+1$ congruences.

Corollary : The simultaneous congruences $$\left\{\begin{array}{cccl}n & \equiv & n_1 & (\mod m_1) \\ n & \equiv & n_2 & (\mod m_2) \\ & & \vdots & \\ n & \equiv & n_k & (\mod m_k)\end{array}\right.$$ where all $m_i$'s are pairwise coprime has a unique solution modulo $m_1\cdot m2\cdots m_k$.

If some $m_i$'s are not mutually prime, a solution may not exist unless the corresponding congruences agree. For example, the system

$$\left\{\begin{array}{cccc}n & \equiv & 1 & (\mod 2) \\ n & \equiv & 2 & (\mod 4) \end{array}\right.$$ has no solutions, while the system

$$\left\{\begin{array}{cccc}n & \equiv & 1 & (\mod 2) \\ n & \equiv & \pm 1 & (\mod 4)\end{array}\right.$$ does.