---
tag: 0FNN9B4W64
kind: statement
role: theorem
name: Chinese remainder theorem
msc: [11A07]
uses: [0TPW25CBN6, 0GFKP8F8AG]
sources:
  - url: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
    locator: Statement
same_as:
  wikidata: Q193878
  wikipedia: Chinese remainder theorem
---

## Statement

Let $n_1, \dots, n_k$ be positive integers that are pairwise [[coprime|0GFKP8F8AG]], and let $N = n_1 n_2 \cdots n_k$.
Let $a_1, \dots, a_k$ be integers.
Then there is an integer $x$ such that $x \equiv a_i \pmod{n_i}$ for each $i$.
Two such integers are congruent modulo $N$.

## Remarks

In the language of rings, the map $\mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}$, $\overline{x} \mapsto (\overline{x}, \dots, \overline{x})$, is a ring isomorphism.
For two moduli $m$ and $n$, write $m u + n v = 1$ with [[Bézout's identity|0DQVHMYAGA]]. Then $x = a_2 m u + a_1 n v$ solves $x \equiv a_1 \pmod m$ and $x \equiv a_2 \pmod n$.
The [[Chinese remainder theorem for non-coprime moduli|04SJTX9P4N]] removes the hypothesis of coprimality.

## History

The Chinese book Sunzi Suanjing, from the 5th century, contains the oldest known example of the problem. Qin Jiushao gave a complete method in 1247.

## Explanations

### L1 human

Find a number that leaves the remainder $2$ when you divide by $3$, the remainder $3$ by $5$, and the remainder $2$ by $7$.
The theorem says that such a number exists, and that it is unique up to multiples of $3 \cdot 5 \cdot 7 = 105$.
The smallest positive answer is $23$.