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.
I found out in class last night that I should have had the following:
165 1(mod 2) = 1
110 1(mod 3) = 2
66 1(mod 5) = 1
30 1(mod 11) = 7
Substituting in the above equation gives x = 1643 323(mod 330)
So x = 323 + 330k where k is an element Z
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 .
Why do we need to make ? We don't. works just as well. See below.
Does it need to be positive? No. You'll see that I used negative values ( and ) in my final evaluation of . These were the ones I got by using the Euclidean Algorithm to solve the equations. This gave me the value , which is a perfectly good solution. Try it - you'll find it satisfies all four of the original modular equations.
As I then explained, you can add on any multiple of to obtain further, equally valid, values of . In general, then, any value given by will work.
How did I get from to ? It may sound trivial, but I added . Why?
was a solution to the equation:which again I found using the Euclidean Algorithm. But, since this is simply a solution to the modular equationany value of that is equivalent to will do equally well. So that's and so on. Each different value of will have a different value of (for example, will require ), but any one of these could be used in the final calculation of .
Can you see why? It's because in the formula for is multiplied by . So two values of that differ by will result in a value of that differs by , and as we've seen, that will work just as well.
I hope that helps to clarify things.