# Chinese remainder theorem

The Chinese remainder theorem may be stated as follows: if there are *n* numbers, *a*_{1} 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*_{1} = 3 and *a*_{2} = 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.