Chinese Remainder Theorem

$⟨$ Theorem A-13.1 $⟩$ Chinese Remainder Theorem

Suppose we have positive coprime integers $n_{0}, n_{1}, n_{2}, \dots, n_{k}$ . Let $N = n_{1} n_{2} \dots n_{k}$ . We sample $k + 1$ random integers $a_{0}, a_{1}, a_{2}, \dots, a_{k}$ from each modulo domain $n_{0}, n_{1}, n_{2}, \dots, n_{k}$ (i.e., $a_{0} \in ℤ_{n_{0}}$ , $a_{1} \in ℤ_{n_{1}}$ , $\dots$ , $a_{k} \in ℤ_{n_{k}}$ ). Then, there exists one and only one solution $x mod N$ such that $x$ is congruent with $a_{0}, a_{1}, a_{2}, \dots, a_{k}$ in each modulo $n_{0}, n_{1}, n_{2}, \dots, n_{k}$ . That is:

$x \equiv a_{0} mod n_{0}$

$x \equiv a_{1} mod n_{1}$

$x \equiv a_{2} mod n_{2}$

$⋮$

$x \equiv a_{k} mod n_{k}$

To compute $x$ , we first compute each $y_{i}$ and $z_{i}$ (for $0 \leq i \leq k$ ) as follows:

$y_{i} = \frac{N}{n_{i}}, z_{i} = y_{i}^{- 1} mod n_{i}$

Note that each $y_{i}$ ’s inverse (i.e., $y_{i}^{- 1}$ ) can be computed by using the Extended Euclidean algorithm (watch the YouTube tutorial). Then, the unique solution $x$ can be computed as follows:

$x = \sum_{i = 0}^{k} a_{i} y_{i} z_{i}$ # Alternatively, we can compute $x = \sum_{i = 0}^{k} | a_{i} z_{i} |_{n_{i}} y_{i}$ (where $| a_{i} z_{i} |_{n_{i}} = a_{i} z_{i} mod n_{i}$ )

Since such $x$ is unique in $mod N$ , there are isomorphic mappings between $x mod N$ and $(a_{0}, a_{1}, a_{2}, \dots, a_{k})$ .

Also, $y_{i} z_{i} \equiv {(y_{i} z_{i})}^{2} mod N$ for all $0 \leq i \leq k$

Proof.

1.

Given

x = \sum_{i = 0}^{k} a_{i} y_{i} z_{i}

, let’s compute

x mod n_{i}

for each

i

where

0 \leq i \leq k

$x mod n_{i} = \sum_{i = 0}^{k} a_{i} y_{i} z_{i} mod n_{i}$

$= a_{0} y_{0} z_{0} + a_{1} y_{1} z_{1} + a_{2} y_{2} z_{2} + \dots + a_{k} y_{k} z_{k} mod n_{i}$

$= a_{i} y_{i} z_{i} mod n_{i}$ # because $y_{j} \equiv 0 mod n_{i}$ for all $j \neq i$ , as they are a multiple of $n_{i}$

$= a_{i}$ # because $y_{i} z_{i} = y_{i} y_{i}^{- 1} = 1$

Thus, the value of $x$ in each modulo $n_{0}, n_{1}, n_{2}, \dots, n_{k}$ is congruent with $a_{0}, a_{1}, a_{2}, \dots, a_{k}$ .

Alternatively, note that the following is also true:

$x mod n_{i} = \sum_{i = 0}^{k} | a_{i} z_{i} |_{n_{i}} y_{i} (mod n_{i})$

$= | a_{0} z_{0} |_{n_{0}} y_{0} + | a_{1} z_{1} |_{n_{1}} y_{1} + | a_{2} z_{2} |_{n_{2}} y_{2} + \dots + | a_{k} y_{k} |_{n_{k}} y_{k} mod n_{i}$

$= | a_{i} z_{i} |_{n_{i}} y_{i} mod n_{i}$

$= a_{i}$

2.

Now, we prove that

x

is a unique solution in modulo

N

. Suppose there were two solutions:

x

and

x^{'}

such that:

$x \equiv x^{'} \equiv a_{0} mod n_{0}$

$x \equiv x^{'} \equiv a_{1} mod n_{1}$

$x \equiv x^{'} \equiv a_{2} mod n_{2}$

$⋮$

$x \equiv x^{'} \equiv a_{k} mod n_{k}$

Then, by definition of modulo congruence, $n_{0} | (x - x^{'}), n_{1} | (x - x^{'}), n_{2} | (x - x^{'}), \dots, n_{k} | (x - x^{'})$ .

Also, since $n_{0}, n_{1}, n_{2}, \dots, n_{k}$ are coprime, it must be the case that $n_{0} n_{1} n_{2} n_{3} \dots n_{k} | (x - x^{'})$ , or $N | (x - x^{'})$ . This means that $x \equiv x^{'} mod N$ . Therefore, $x$ is a unique solution in modulo $N$ .

3.

Now, we will prove that

y_{i} z_{i} \equiv {(y_{i} z_{i})}^{2} mod N

for all

0 \leq i \leq k

In the case of modulo $n_{i}$ , $y_{i} z_{i} \equiv 1 mod n_{i}$ , since $z_{i}$ is an inverse of $y_{i}$ modulo $n_{j}$ . In the case of all other modulo $n_{j}$ where $i \neq j$ , $y_{i} z_{i} \equiv 0 mod n_{j}$ , because $y_{i} = \frac{N}{n_{i}}$ and thus $n_{j}$ divides $y_{i}$ .

By squaring both sides of $(y_{i} z_{i}) \equiv 1 mod n_{i}$ , we get ${(y_{i} z_{i})}^{2} \equiv 1 mod n_{i}$ . Similarly, by squaring both sides of $(y_{i} z_{i}) \equiv 1 mod n_{j}$ , we get ${(y_{i} z_{i})}^{2} \equiv 0 mod n_{j}$ .

Therefore, $y_{i} z_{i} - {(y_{i} z_{i})}^{2} \equiv 0 mod n_{i}$ , and $y_{i} z_{i} - {(y_{i} z_{i})}^{2} \equiv 0 mod n_{j}$ . In other words, $y_{i} z_{i} - {(y_{i} z_{i})}^{2} \equiv 0 mod n_{j}$ for all $0 \leq j \leq k$ .

Then, we do the similar reasoning as step 2: since every co-prime $n_{j}$ divides $y_{i} z_{i} - {(y_{i} z_{i})}^{2}$ , $n_{0} n_{1} \dots n_{k} = N$ divides $y_{i} z_{i} - {(y_{i} z_{i})}^{2}$ . Thus, $y_{i} z_{i} - {(y_{i} z_{i})}^{2} \equiv 0 mod N$ , which is $y_{i} z_{i} \equiv {(y_{i} z_{i})}^{2} mod N$ . This is true for all $0 \leq i \leq k$ .

□

A-13 Chinese Remainder Theorem