Chinese remainder theorem

The Chinese remainder theorem is a mathematical result about modular arithmetic. It describes the solutions to a system of linear congruences with distinct moduli. As well as being a fundamental tool in number theory, the Chinese remainder theorem forms the theoretical basis of algorithms for storing integers and in cryptography. The Chinese remainder theorem can be generalized to a statement about commutative rings; for more about this, see the "Advanced" subpage.

Theorem statement

The Chinese remainder theorem:

Let $n_{1},\ldots ,n_{t}$ be pairwise relatively prime positive integers, and set $n=n_{1}n_{2}\cdots n_{t}$. Let $a_{1},\ldots ,a_{k}$ be integers. The system of congruences

${\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\\vdots &\equiv \vdots \\x&\equiv a_{t}{\pmod {n_{t}}}\\\end{aligned}}$

has solutions, and any two solutions differ by a multiple of $n$.