Expert: Sherry Wallin - 6/29/2010

Question
QUESTION: Hello.
I've been searched and thinked a lot about this theorm (Chinese Remainder Theorem) but I can't figure out how it works and how to use it
(an example:how to demostrate for n congruences simultaneously that ig gcd(m1,m2)=1 then there is a solution x of the congruences x congruent to a1 (mod m1),x congruent a2 (mod m2) and so on...)

Thanks in advance

ANSWER: Manuel, help me out here please. What do you mean by 'ig'? Also provide me with a specific problem and I will work it and explain step by step what I am doing.

Math Prof



**  As promised I have written a document to help explain the Chinese Remainder Theorem. Please let me know if this helps you and how much, thank you

Math Prof**

---------- FOLLOW-UP ----------

QUESTION: I read your work and is very clear.
But from "Basically your moduli..." (part of the paragraph starting with "x= 172+315w" about in middle of the image).
And moreover is right witch is a congruence is true then we can handle it just as a normal equation? (example: 1 congrous 1 mod 1 is true so we can handle it as "1=1" with the "extra property" which we can "read" it as 1+ my = 1)
Thanks

ANSWER: I'm not sure what your question is here. 1 cong 1 mod 1 isn't very useful since any integer is divisible by 1.

So you can only use CRT if the moduli are relatively (pairwise) prime. It doesn't work otherwise. It works because if all are pairwise relatively prime when you pair them up their product is still relatively prime to the 3rd one. As in our example the three moduli are 5,7,9. These are relatively prime and 9 is still relatively prime to 5*7 = 35 and 7 is still relatively prime to 5*9 = 45 and 5 is still relatively prime to 7*9 = 63.

You can take each congruence on it's own and solve it but you must substitute it's value into the next one or else you won't find a solution to the congruence system. Remember in algebra when you were solving a system of linear equations? It is necessary that you use substitution somewhere so that you are finding the solution for the system and not just an equation.

If I haven't understood your question or answered it please try to restate it so I can respond effectively to you.

Math Prof

---------- FOLLOW-UP ----------

QUESTION: They were intended to be two distinct question:
1)"I'm not sure what your question is here. 1 cong 1 mod 1 isn't very useful since any integer is divisible by 1.":simply = is THE SAME of "operator congruence" in Zm,when we are sure the congruence is true (and consequently we can handle,for example 9 congruos 3 mod 3,as a simple equation like 3*k=3)? ("Stupid" example but I saw you are in example apply the property of equations to congruences)
2) So substitute the result of first congruence in the second and next in the third is THE SAME to apply CRT?

3)However is clear to me WHEN WE CAN use CRT,but NOT KNOW to use it (I suppose you applied it from "Basically..." right?)

Thanks again

Answer
If you have 9 cong 3 mod 3 this translates as 3|9 (here I am using | for the concept of divides) which in turn translates as 9 = 3k but only because 3 divides 9. Suppose instead you had 10 cong 1 mod 3 then this translates as 10 divided by 3 = 3 remainder 1 or that 10 = 3k + 1 and this means that x cong 1 mod 3 can be rewritten as x = 3k +1 for k an integer. And yes you can consider congruences in Zm as equals if that makes it seem more plausible to you. Just keep in mind if the modulus does not divide x then the congruence will not be 0, the congruence  will be the remainder upon division.

In the attached image I showed you the same problem worked two ways. The first was meant to show you that the CRT in the 2nd generates the same solution. But the first was also used to explain why the CRT works.

Math Prof