May 7 Discussion

Rachel and Lin:

We discussed Sun Tzu, and the nebulous history surrounding his life. What is difficult about using the internet to look up this figure is that, understandably given the thousands of years of history that separate then and now, there is more than one person with his name.

I started with Wikipedia. The article I link to here is apparently the article for the Chinese mathematician who wrote the book containing the Chinese Remainder Theorem. The claim, according to the article is that he was alive around 200-400 C.E. Unfortunately, this wiki article is a stub, but does note that with regard to Tzu's work, he investigated astronomy and diophantine equations. Many sources, however, seem to concur that very little, if anything at all, is known about Tzu.

With regard to the Chinese Remainder Theorem, Wikipedia has a very clear definition of the theorem. It also offers an example which I found helpful. I suggest that the reader be very careful at the end, as the last few sections are confusing to me.

There appear to be many proofs on the internet of the Chinese Remainder Theorem, which appear to quote many different sources. One simpler one I found is here. I was talking to Mou and he found a very interesting proof that I hope he shares as well.

- Rob M.

Thanks Rob! The "official statement" of the Chinese Remainder Theorem I found is in the textbook of Discreet Mathematics. The theorem states as this:

Let m1,m2, … , mn be pairwise relatively
prime positive integers greater than one and a1, a2, … , an arbitrary integers. Then the system
x ≡ a1 (mod m1),
x ≡ a2 (mod m2),
x ≡ an (mod mn)
has a unique solution modulo m = m1·m2 · · ·mn. (That is, there is a solution x with
0 ≤ x <m, and all other solutions are congruent modulo m to this solution.)

Proof: To establish this theorem, we need to show that a solution exists and that it is unique
modulo m. We will show that a solution exists by describing a way to construct this solution;
showing that the solution is unique modulo m is Exercise 30.
To construct a simultaneous solution, first let
Mk = m/mk
for k = 1, 2, … , n. That is, Mk is the product of the moduli except for mk. Because mi and mk
have no common factors greater than 1 when i = k, it follows that gcd(mk,Mk) = 1. Consequently,
by Theorem 1, we know that there is an integer yk, an inverse of Mk modulo mk, such
Mkyk ≡ 1 (mod mk).
To construct a simultaneous solution, form the sum
x = a1·M1·y1 + a2·M2·y2 +· · ·+an·Mn·yn.
We will now show that x is a simultaneous solution. First, note that because Mj ≡ 0 (mod mk)
whenever j = k, all terms except the kth term in this sum are congruent to 0 modulomk. Because
Mk·yk ≡ 1 (mod mk) we see that
x ≡ ak·Mk·yk ≡ ak (mod mk),
for k = 1, 2, … , n.We have shown that x is a simultaneous solution to the n congruences.

As for the problem we saw in class, it could be simplified as finding an integer x that
x≡2(mod 3)
x≡3(mod 5)
x≡2(mod 7)
so let m=3·5·7=105
then M1=m/3=35, M2=m/5=21, M3=m/7=15. now we have to find y1, y2 and y3. They are actually the inverse of M1 mod3, M2 mod 5 and M3 mod 7. Inverse means that
y1·M1=1(mod 3)
y2·M2=1(mod 5)
y3·M3=1(mod 7)
in this case, y1=2, y2=1, y3=1.
So x≡ a1·M1·y1+a2·M2·y2+a3·M3·y3=2·35·2+3·21·1+2·15·1= 233 = 23 (mod 105)
- Mou

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License