## Chinese remainder theoremIf 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.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. ## Related category• NUMBER THEORY | |||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |