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.
Related category NUMBER THEORY
Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact