Chinese Remainder Theorem

Chinese Remainder Theorem

Let $n_1,n_2,\dots ,n_r$ be positive integers such that $gcd(n_i,n_j)=1$ for $i\ne j$. Then the linear congruence’s:

$$\begin{array}{rl}x& \equiv a_1(\mathrm{mod}{n}_1)\\ x& \equiv a_2(\mathrm{mod}{n}_2)\\ & ⋮\\ x& \equiv a_r(\mathrm{mod}{n}_r)\end{array}$$

has a simultaneous solution, which is unique modulo the integer $n_1{n}_2\cdots n_r$.

Proof

• Existence of a solution:

Let $n=n_1\cdots n_r$ For each $k\in [r]$, let $N_k=\frac{n}{n_k}$. Since $gcd(n_i,n_j)=1$, then $gcd(N_k,n_k)=1$. Using this, we know that there exists a solution to $N_{k}x\equiv 1(\mathrm{mod}{n}_k)$ We will denote the unique solution of this equation as $x_k$. Our goal is to prove that the integer: $\bar{x}=a_1{N}_1{x}_1+\dots +a_r{N}_r{x}_r$ is a simultaneous solution of the given system.

1. $N_i\equiv 0(\mathrm{mod}{n}_k)$ when $i\ne k$, because $n_k\mid N_i$. We get the following congruence: $\bar{x}\equiv a_k{N}_k{x}_k(\mathrm{mod}{n}_k)$
2. Since $N_k{x}_k\equiv 1(\mathrm{mod}{n}_k)$, we now get $\bar{x}\equiv a_k(\mathrm{mod}{n}_k)$ Giving us the existence of a solution to the system of congruences.

• Uniqueness of the Solution

Suppose $x^{\prime }$ is another integer that satisfies these congruences. Then, $\bar{x}\equiv a_k\equiv x^{\prime }(\mathrm{mod}{n}_k)k\in [r]$ Then $n_k\mid \bar{x}-x^{\prime }$ for every $k$. Since $gcd(n_i,n_j)=1$, then we can easily obtain $n_1{n}_2\dots n_r\mid \bar{x}-x^{\prime }⟺\bar{x}\equiv x^{\prime }(\mathrm{mod}{n}_1{n}_2\cdots n_r)$. Hence proving that our solution is unique modulo the integer $n_1{n}_2\cdots n_r$

Example (Ancient Chinese Problem)

A band of 17 pirates stole a sack of gold coins. When they tried to divide the fortune into equal portions, 3 coins remained. In the ensuing brawl over who should get the extra coins, one pirate was killed. The wealth was redistributed, but this time an equal division left 10 coins. Again an argument developed in which another pirate was killed. But now the fortune was evenly distributed among the survivors. What was the least number of coins that could of been stolen

Let $x$ be the number of gold coins.

$$\begin{array}{rl}x& \equiv 3(\mathrm{mod}17)\\ x& \equiv 10(\mathrm{mod}16)\\ x& \equiv 0(\mathrm{mod}15)\end{array}$$ $$\begin{array}{rl}(16\cdot 17)x_1& \equiv 1(\mathrm{mod}15)\\ (1\cdot 2)x_1& \equiv 1(\mathrm{mod}15)\\ x_1& \equiv 8(\mathrm{mod}15)\end{array}$$ $$\begin{array}{rl}(15\cdot 17)x_2& \equiv 1(\mathrm{mod}16)\\ (-1\cdot 1)x_2& \equiv 1(\mathrm{mod}16)\\ x_2& \equiv 15(\mathrm{mod}16)\end{array}$$ $$\begin{array}{rl}(15\cdot 16)x_3& \equiv 1(\mathrm{mod}17)\\ (-2\cdot -1)x_3& \equiv 1(\mathrm{mod}17)\\ x_3& \equiv 9(\mathrm{mod}17)\end{array}$$ $$\begin{array}{rl}\bar{X}& =a_1{N}_1{x}_1+a_2{N}_2{x}_2+a_3{N}_3{x}_3\\ & =(0)(16\cdot 17)(8)+(10)(15\cdot 17)(15)+(3)(15\cdot 16)(9)\\ & =44730\end{array}$$ $$\begin{array}{rl}44370& \equiv x(\mathrm{mod}15\cdot 16\cdot 17)\\ x& \equiv 3930(\mathrm{mod}4080)\end{array}$$

OR! if you kept $x^2=-1$, you will instantly get the calculation in less steps!

$$\begin{array}{rl}\bar{X}& =a_1{N}_1{x}_1+a_2{N}_2{x}_2+a_3{N}_3{x}_3\\ & =(0)(16\cdot 17)(8)+(10)(15\cdot 17)(-1)+(3)(15\cdot 16)(9)\\ & =3930\end{array}$$