The Chinese remainder theorem may be stated as follows: if there are n numbers, a₁ to a_n, that have no factors in common (in other words, are pairwise relatively prime), then any integer greater than or equal to 0 and less than the product of all the numbers n can be uniquely represented by a series consisting of the remainders of division by the numbers n. For example, if a₁ = 3 and a₂ = 5, the Chinese remainder theorem (CRT) says that every integer from 0 to 14 will have a unique set of remainders when divided separately by (modulo) 3 and 5. Listing out all the possibilities shows that this is true:

 

0 has a remainder of 0 modulo 3 and a remainder of 0 modulo 5.
1 has a remainder of 1 modulo 3 and a remainder of 1 modulo 5.
2 has a remainder of 2 modulo 3 and a remainder of 2 modulo 5.
3 has a remainder of 0 modulo 3 and a remainder of 3 modulo 5.
4 has a remainder of 1 modulo 3 and a remainder of 4 modulo 5.
5 has a remainder of 2 modulo 3 and a remainder of 0 modulo 5.
6 has a remainder of 0 modulo 3 and a remainder of 1 modulo 5.
7 has a remainder of 1 modulo 3 and a remainder of 2 modulo 5.
8 has a remainder of 2 modulo 3 and a remainder of 3 modulo 5.
9 has a remainder of 0 modulo 3 and a remainder of 4 modulo 5.
10 has a remainder of 1 modulo 3 and a remainder of 0 modulo 5.
11 has a remainder of 2 modulo 3 and a remainder of 1 modulo 5.
12 has a remainder of 0 modulo 3 and a remainder of 2 modulo 5.
13 has a remainder of 1 modulo 3 and a remainder of 3 modulo 5.
14 has a remainder of 2 modulo 3 and a remainder of 4 modulo 5.

 

CRT enables problems such as the following to be solved: Find the two smallest counting numbers that will each have the remainders 2, 3, and 2 when divided by 3, 5, and 7, respectively. It is said that the ancient Chinese used a variant of this theorem to count their soldiers by having them line up in rectangles of 7 by 7, 11 by 11, ... After counting only the remainders, they solved the associated system of equations for the smallest positive solution.