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

Hello oldguynewstudent Quote:

Originally Posted by

**oldguynewstudent** 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.

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.

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:

is the corresponding quotient So we get:

For : solve the equation . This gives

For : solve . This gives (which is equivalent to as you had)

For :

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 .

Grandad