Chinese remainder theorem
Thanks for the wonderful help I've been getting!
Here is a problem with the Chinese Remainder Theorem:
x 1(mod 2)
x 2(mod 3)
x 3(mod 5)
x 4(mod 11)
x (1)(165) + (2)(110) + (3)(66) + (4)(30)
165 (mod 2) = 1
110 (mod 3) = 2
66 (mod 5) = 1
30 (mod 11) = 7 ??
I don't understand how the rest of the steps work if now we have to go back and use:
30 8 (mod 11) then 8 1 (mod 11)?
I thought I had finally comprehended Euclidean Algorithm with inverses, but now I'm not so sure.
Chinese Remainder Theorem
Hold on here, I think you've oversimplified things! Perhaps you realised that things weren't right because , and you needed to get the right answer! Hence the question mark in your solution.
Originally Posted by oldguynewstudent
I'm afraid the method is a little bit more complicated than your answer.
Let me try and spell it out for you.
First, let me repeat the correct start you made: we need to find numbers , and then find by saying: where:
are the modular equivalents of (mods ) in the four original equations;and the numbers
are quotients when the product of the four moduli, , is divided in turn by .So far, so good.
So how do we find the ? The answer is by solving a set of equations of the form , by using the Euclidean Algorithm. In each case:
is the modulus of the equation: So we get:
is the corresponding quotient
For : solve the equation . This gives
For : solve . This gives (which is equivalent to as you had)
For , let me do the working in full, using the Euclidean Algorithm. We need to solve: So we say:Then we 'go back' (perhaps this is what you meant):Finally, we use these four values of to calculate :If you don't like this answer, and would like something a bit more positive, you can add on as many 's ( ) as you like. The smallest positive value of , then, is ; and to get the solution which (by chance!) you found, add to get .