Chinese Remainder Theorem Essay, Research Paper

CHINESE REMAINDER THEOREM WHAT IS IT ? Mathematics plays an important role in our world, as we know it. It is used everyday to solve all kinds of complex problems enabling us to create a better place for everyone to live in. One particular aspect of Mathematics known as the Chinese Remainder Theorem has a very interesting background. The Chinese Remainder Theorem was believed to have been created around 3rd Century AD by Sun Tzu Suan Ching and is the earliest recorded congruence problems in Chinese Mathematical works. A congruence problem can best be described by the following example: “You have a number of items but don’t know exactly how many. If you count them by threes you have two left over. If you count them by fives, you have three left over. If you count them by sevens you have 2 left over. How many are there ?” Sun Zi discovered that if he used the numbers 70,21,15, which are multiples of 5*7, 3*7, and 3*5 respectively, that the sum (2*70) + (3*21) + (2*15) equals 233. Thus 233 was one answer. He then cast out a multiple of 3*5*7 as many times as possible. By doing so, the least answer result was 23. In modern notation Sun Zi concluded the following: 70 = 1 (mod 3) = 0 (mod 5) = 0 (mod 7) 21 = 1 (mod 5) = 0 (mod 3) = 0 (mod 7) 15 = 1 (mod 7) = 0 (mod 3) = 0 (mod 5) Hence, (2*70) + (3*21) + (2*15) = 233 satisfies the desired congruencies. Also note that any multiples of 105 are divisible by 3, 5, 7. Therefore 2 * 105 is subtracted from 233 to get 23 which is the smallest positive number.

Present day, the Chinese Remainder Theorem is used in many things that require this type of problem solving capabilities. One such example is in the textbook Applied Cryptography by Bruce Schneier. In his text, the Chinese Remainder Theorem is used to solve system equations given you know the prime factorization of “n”. “In general if the prime factorization of n is P1*P2*P3 *Pt, then the system of equations is represented by (x mod pi) = ai, where I = 1,2, t which has a unique solution, x, where x An example of this would be to use 3 and 5 as primes, and 14 as the number. Fourteen mod 3 = 2, and 14 mod 5 = 4. There is only one number less that 3 * 5, which has those residues: 14. The two resides uniquely determine the number. So for an arbitrary a “To find this x, first use Euclid’s algorithm to find u, such that u * q = 1 ( mod p). Then compute x = ((( a-b) * u) mod p) * q + b.”2 In conclusion we can note that Mathematics is a complex system in itself. We also realize that there are many aspects of Mathematics used every day by all types of occupations. Having this capability gives us the ability to greatly enhance our lives and also shows us how important Mathematics is today, and how useful it was thousands of years ago as well.