# Chinese remainder theorem

Suppose we have a set of $n$ congruences^{} of the form

$$\begin{array}{ccc}\hfill x\hfill & \hfill \equiv \hfill & \hfill {a}_{1}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{1})\hfill \\ \hfill x\hfill & \hfill \equiv \hfill & \hfill {a}_{2}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{2})\hfill \\ & \hfill \mathrm{\vdots}\hfill & \\ \hfill x\hfill & \hfill \equiv \hfill & \hfill {a}_{n}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{n})\hfill \end{array}$$ |

where ${p}_{1},{p}_{2},\mathrm{\dots},{p}_{n}$ are relatively prime. Let

$$P=\prod _{i=1}^{n}{p}_{i}$$ |

and, for all $i\in \mathbb{N}$ ($1\le i\le n$), let ${y}_{i}$ be an integer that satisfies

$${y}_{i}\cdot \frac{P}{{p}_{i}}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{i})$$ |

Then one solution of these congruences is

$${x}_{0}=\sum _{i=1}^{n}{a}_{i}{y}_{i}\cdot \frac{P}{{p}_{i}}$$ |

Any $x\in \mathbb{Z}$ satisfies the set of congruences if and only if it satisfies

$$x\equiv {x}_{0}\phantom{\rule{veryverythickmathspace}{0ex}}(modP)$$ |

The Chinese remainder theorem^{} originated in the book *“Sun Zi Suan Jing”*, or Sun Tzu’s Arithmetic Classic, by the Chinese mathematician Sun Zi, or Sun Tzu, who also wrote “Sun Zi Bing Fa”, or Sun Tzu’s The Art of War. The theorem is said to have been used to count the size of the ancient Chinese armies (i.e., the soldiers would split into groups of 3, then 5, then 7, etc, and the “leftover” soldiers from each grouping would be counted).

Title | Chinese remainder theorem |
---|---|

Canonical name | ChineseRemainderTheorem |

Date of creation | 2013-03-22 11:58:58 |

Last modified on | 2013-03-22 11:58:58 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 13 |

Author | CWoo (3771) |

Entry type | Theorem |

Classification | msc 11D79 |

Related topic | ChineseRemainderTheoremInTermsOfDivisorTheory |

Related topic | GodelsBetaFunction |