Chinese remainder theorem

This article needs more work.

Please help by expanding it!

The Chinese remainder theorem (CRT) is a theorem concerning the solution of simultaneous congruences formulated by Sun Tzu. Qín Jiǔsháo in his Mathematical Treatise in Nine Sections and Fibonacci, in his famous book Liber abaci, had a section on the theorem. Today the theorem has applications in number theory and cryptography.

Theorem. (Sun Tzu) Given the $\scriptstyle n\,$ remainders $\scriptstyle r_{1},\,\ldots ,\,r_{n}\,$ for the $\scriptstyle n\,$ coprime moduli $\scriptstyle m_{1},\,\ldots ,\,m_{n},\,$ there is a unique solution $\scriptstyle 0\,\leq \,x\,<\,\prod _{i=1}^{n}m_{i}\,$ satisfying each $\scriptstyle x\,\equiv \,r_{i}{\pmod {m_{i}}}\,$ for $\scriptstyle 1\,\leq \,i\,\leq \,n\,$.

Proof. Just for the moment, let's forget about all the congruences except the first one. For $\scriptstyle x_{1}\,\equiv \,r_{1}{\pmod {m_{1}}}\,$ there is a trivial solution $\scriptstyle x_{1}\,=\,r_{1}\,$. Remembering now the second congruence, $\scriptstyle x_{2}\,\equiv \,r_{2}{\pmod {m_{2}}}\,$, form the arithmetic progression $\scriptstyle a\,=\,\{x_{1},\,m_{1}+x_{1},\,2m_{1}+x_{1},\,\ldots ,\,(m_{2}-1)m_{1}+x_{1}\}\,$. Each number in the sequence $\scriptstyle a\,$ satisfies the first congruence. The sequence was formed with the function $\scriptstyle f(j)\,=\,jm_{1}+x_{1}\,$ applied for $\scriptstyle j\,$ from 0 to $\scriptstyle m_{2}-1\,$, and since $\scriptstyle m_{1}\,$ and $\scriptstyle m_{2}\,$ are coprime, this means that $\scriptstyle f(j){\pmod {m_{2}}}\,$ over the range specified forms a complete residue class modulo $\scriptstyle m_{2}\,$, that is, the $\scriptstyle a_{j}{\pmod {m_{2}}}\,$ constitute a permutation of the numbers from 0 to $\scriptstyle m_{2}-1\,$. If $\scriptstyle m_{1}\,$ and $\scriptstyle m_{2}\,$ shared even just one prime factor, $\scriptstyle a\,$ would contain at least two instances of 0, and possibly not the number we need. But since they are coprime and we have the complete residue class, this means that in $\scriptstyle a\,$ there is precisely one number $\scriptstyle a_{j}\,$ that satisfies both the first and the second congruence: setting $\scriptstyle x_{2}\,$ to that $\scriptstyle a_{j}\,$, we then have not only $\scriptstyle x_{2}\,\equiv \,r_{1}{\pmod {m_{1}}}\,$ and $\scriptstyle x_{2}\,\equiv \,r_{2}{\pmod {m_{2}}}\,$ but also $\scriptstyle x_{2}\,\equiv \,a_{j}{\pmod {m_{1}m_{2}}}\,$. For $\scriptstyle m_{3}\,$ we can just repeat this process, using $\scriptstyle x_{2}\,$ in the place of $\scriptstyle x_{1}\,$ and $\scriptstyle m_{3}\,$ in the place of $\scriptstyle m_{2}\,$, and so on and so forth, until finding $\scriptstyle x_{n}\,$ which satisfied each congruence $\scriptstyle r_{i}{\pmod {m_{i}}}\,$ for $\scriptstyle i\,$ from 1 to $\scriptstyle n\,$ and is therefore precisely the number $\scriptstyle x\,$ specified by the theorem. □

For example, given the remainders 1, 3, 5 and the moduli 2, 7, 15, the unique solution $\scriptstyle 0\,\leq \,x\,<\,2\cdot 7\cdot 15\,$ is 185: we verify that indeed $\scriptstyle 185\,\equiv \,1{\pmod {2}}\,$, $\scriptstyle 185\,\equiv \,3{\pmod {7}}\,$ and $\scriptstyle 185\,\equiv \,5{\pmod {15}}\,$. All solutions are thus of the form $\scriptstyle 185+k\,(2\cdot 7\cdot 15),\,k\,\in \,\mathbb {Z} \,$.

The method described in the proof above is admittedly somewhat laborious. A somewhat more efficient way to solve a system of congruences requires first finding the product of the moduli $\scriptstyle M\,=\,\prod _{i=1}^{n}m_{i}\,$, then finding numbers $\scriptstyle b_{i}\,$ such that $\scriptstyle b_{i}{\frac {M}{m_{i}}}\,\equiv \,1{\pmod {m_{i}}}\,$. The solution is then

$x=\sum _{i=1}^{n}r_{i}b_{i}{\frac {M}{m_{i}}}\mod M.\,$

The $\scriptstyle \mod M\,$ operation may be performed just once, after adding up the various $\scriptstyle r_{i}b_{i}{\frac {M}{m_{i}}}\,$, or iteratively after each addend; either way, this will give the solution.

Returning to our example of $\scriptstyle x\,=\,185\,$, we find that the product of the moduli is 210, and that the $\scriptstyle b_{i}\,$ are 1, 4, 14. Then, 1 × 1 × 105 = 105, 3 × 4 × 30 = 360, 5 × 14 × 14 = 980. and that 105 + 360 + 980 = 1445, which is 185 mod 210.

The astute reader previously unfamiliar with this theorem should by now have realized that $\scriptstyle x\,$ is not the only possible solution to the system of simultaneous congruences, just the smallest possible (here we are concerned only with nonnegative integers). There are infinitely many other solutions of the form $\scriptstyle yM+x\,$, where $\scriptstyle y\,\in \,\mathbb {Z} \,$ (and of course the original $\scriptstyle x\,$ corresponds to $\scriptstyle y\,=\,0\,$). Thus, 1235, 95525 and 197585 are randomly chosen alternative solutions to the example problem above.

The importance of the moduli being coprime is that if they are not, then some of the congruences may be at best redundant and at worst contradictory. As an example of the former, we give $\scriptstyle x\,\equiv \,3{\pmod {16}}\,$ and $\scriptstyle x\,\equiv \,3{\pmod {128}}\,$ (the congruence with the smaller modulo may be dispensed with, since it will be satisfied by a number that satisfies the congruence with the larger modulo), and as an example of the latter, $\scriptstyle x\,\equiv \,3{\pmod {16}}\,$ and $\scriptstyle x\,\equiv \,4{\pmod {32}}\,$ (these two congruences can't be satisfied simultaneously).

Sequences

A053664 gives the smallest number $\scriptstyle x\,$ such that $\scriptstyle x\,\equiv \,i{\pmod {p_{i}}}\,$ for $\scriptstyle 1\,\leq \,i\,\leq \,n\,$, where $\scriptstyle p_{i}\,$ is the $\scriptstyle i\,$th prime number.

{1, 5, 23, 53, 1523, 29243, 299513, 4383593, 188677703, 5765999453, 5765999453, 2211931390883, 165468170356703, 8075975022064163, 361310530977154973, ...}

A182433 gives the smallest number such that the next $\scriptstyle n\,$ integers each have the square of one of the first $\scriptstyle n\,$ primes as a factor in order. The terms of this sequence are found by applying the Chinese remainder theorem.

{7, 547, 29347, 1308247, 652312447, 180110691547, 65335225716547, 38733853511213647, ... }