 |
|
| A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
|
|
Chinese remainder theorem
If there are n numbers, a1 to an, 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 a1 = 3 and a2 = 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.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.
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.
Related category
• NUMBER THEORY
Also on this site:
Encyclopedia of Alternative Energy & Sustainable Living
Encyclopedia of History
Transport Concepts & Designs (partner site)