1. ## Chinese remainder theorem

Thanks for the wonderful help I've been getting!

Here is a problem with the Chinese Remainder Theorem:

x $\equiv$ 1(mod 2)
x $\equiv$ 2(mod 3)
x $\equiv$ 3(mod 5)
x $\equiv$ 4(mod 11)

x $\equiv$ (1)(165) $y_1$ + (2)(110) $y_2$ + (3)(66) $y_3$ + (4)(30) $y_4$

165 $\equiv$ $y_1$ (mod 2) $\Rightarrow$ $y_1$ = 1

110 $\equiv$ $y_2$ (mod 3) $\Rightarrow$ $y_3$ = 2

66 $\equiv$ $y_3$ (mod 5) $\Rightarrow$ $y_3$ = 1

30 $\equiv$ $y_4$ (mod 11) $\Rightarrow$ $y_4$ = 7 ??

I don't understand how the rest of the steps work if now we have to go back and use:
30 $\equiv$ 8 (mod 11) then 8 $y_4$ $\equiv$ 1 (mod 11)?

I thought I had finally comprehended Euclidean Algorithm with inverses, but now I'm not so sure.

2. Originally Posted by oldguynewstudent
Thanks for the wonderful help I've been getting!

Here is a problem with the Chinese Remainder Theorem:

x $\equiv$ 1(mod 2)
x $\equiv$ 2(mod 3)
x $\equiv$ 3(mod 5)
x $\equiv$ 4(mod 11)

x $\equiv$ (1)(165) $y_1$ + (2)(110) $y_2$ + (3)(66) $y_3$ + (4)(30) $y_4$

165 $\equiv$ $y_1$ (mod 2) $\Rightarrow$ $y_1$ = 1

110 $\equiv$ $y_2$ (mod 3) $\Rightarrow$ $y_3$ = 2

66 $\equiv$ $y_3$ (mod 5) $\Rightarrow$ $y_3$ = 1

30 $\equiv$ $y_4$ (mod 11) $\Rightarrow$ $y_4$ = 7 ??

I don't understand how the rest of the steps work if now we have to go back and use:
30 $\equiv$ 8 (mod 11) then 8 $y_4$ $\equiv$ 1 (mod 11)?

I thought I had finally comprehended Euclidean Algorithm with inverses, but now I'm not so sure.
I'm not sure what's your problem: you got $y_1=1\,,\,y_2=2\,,\,y_3=1\,,\,y_4=7$ $\Longrightarrow\,x=165\cdot 1+220\cdot 2+198\cdot 1+120\cdot 7=1,643$.

What do you mean "go back", anyway? Go back where and what for?

Tonio

3. ## I was missing a step

Originally Posted by tonio
I'm not sure what's your problem: you got $y_1=1\,,\,y_2=2\,,\,y_3=1\,,\,y_4=7$ $\Longrightarrow\,x=165\cdot 1+220\cdot 2+198\cdot 1+120\cdot 7=1,643$.

What do you mean "go back", anyway? Go back where and what for?

Tonio
I was missing a step or I had the next to last step incorrect.

I found out in class last night that I should have had the following:

165 $y_1$ $\equiv$ 1(mod 2) $\Rightarrow$ $y_1$ = 1

110 $y_2$ $\equiv$ 1(mod 3) $\Rightarrow$ $y_2$ = 2

66 $y_3$ $\equiv$ 1(mod 5) $\Rightarrow$ $y_3$ = 1

30 $y_4$ $\equiv$ 1(mod 11) $\Rightarrow$ $y_4$ = 7

Substituting in the above equation gives x = 1643 $\equiv$ 323(mod 330)

So x = 323 + 330k where k is an element Z

4. ## Chinese Remainder Theorem

Hello oldguynewstudent
Originally Posted by oldguynewstudent
Thanks for the wonderful help I've been getting!

Here is a problem with the Chinese Remainder Theorem:

x $\equiv$ 1(mod 2)
x $\equiv$ 2(mod 3)
x $\equiv$ 3(mod 5)
x $\equiv$ 4(mod 11)

x $\equiv$ (1)(165) $y_1$ + (2)(110) $y_2$ + (3)(66) $y_3$ + (4)(30) $y_4$

165 $\equiv$ $y_1$ (mod 2) $\Rightarrow$ $y_1$ = 1

110 $\equiv$ $y_2$ (mod 3) $\Rightarrow$ $y_3$ = 2

66 $\equiv$ $y_3$ (mod 5) $\Rightarrow$ $y_3$ = 1

30 $\equiv$ $y_4$ (mod 11) $\Rightarrow$ $y_4$ = 7 ??

I don't understand how the rest of the steps work if now we have to go back and use:
30 $\equiv$ 8 (mod 11) then 8 $y_4$ $\equiv$ 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 $30\equiv 8 \mod 11$, and you needed $30\equiv 7 \mod 11$ 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 $4$ numbers $y_1 ... y_4$, and then find $x$ by saying:
$x = 1.165y_1+2.110y_2+3.66y_3+4.30y_4$
where:
$1, 2, 3, 4$ are the modular equivalents of $x$ (mods $2, 3, 5, 11$) in the four original equations;
and the numbers
$165, 110, 66, 30$ are quotients when the product of the four moduli, $2\times3\times5\times11$, is divided in turn by $2, 3, 5, 11$.
So far, so good.

So how do we find the $y_i$? The answer is by solving a set of equations of the form $a_in_i + b_iy_i = 1$, by using the Euclidean Algorithm. In each case:
$a_i$ is the modulus of the equation: $2, 3, 5, 11$

$b_i$ is the corresponding quotient $165, 110, 66, 30$
So we get:

For $y_1$: solve the equation $2n_1 + 165y_1=1$. This gives $n_1=-82, y_1=1$

For $y_2$: solve $3n_2+110y_2=1$. This gives $n_2=37, y_2 = -1$ (which is equivalent to $y_2 = 2$ as you had)

For $y_3$: $5n_3+66y_3 = 1\Rightarrow n_3 =-13, y_3=1$

For $y_4$, let me do the working in full, using the Euclidean Algorithm. We need to solve:
$11n_4+30y_4 = 1$
So we say:
$30 = 2\times11+8$
$11=1\times8+3$
$8=2\times3+2$
$3=2+1$
Then we 'go back' (perhaps this is what you meant):
$1=3-2$
$=3-(8-2\times3)$
$=3\times3-8$
$=3\times(11-8)-8$
$=3\times11-4\times8$
$=3\times11-4(30-2\times11)$
$=11\times11-4\times30$
$\Rightarrow n_4=11, y_4 = -4$
Finally, we use these four values of $y_i$ to calculate $x$:
$x=1\times165-2\times110+3\times66-120\times4=-337$
If you don't like this answer, and would like something a bit more positive, you can add on as many $330$'s ( $=2\times3\times5\times11$) as you like. The smallest positive value of $x$, then, is $-337+2\times330 =323$; and to get the solution which (by chance!) you found, add $6\times 330 = 1980$ to get $1643$.

5. ## Aha

As Ricky said to Lucy, "That 'splains it!"

For $y_2$: solve $3n_2+110y_2=1$. This gives $n_2=37, y_2 = -1$ (which is equivalent to $y_2 = 2$ as you had)

Why if we get a negative answer for y2, do we need to make it 2?

Is there something in the theorem that states it needs to be positive?

How did you get from -1 to 2?

7. Hello mathceleb
Originally Posted by mathceleb

Why if we get a negative answer for y2, do we need to make it 2?

Is there something in the theorem that states it needs to be positive?

How did you get from -1 to 2?

Why do we need to make $y_2 = 2$? We don't. $-1$ works just as well. See below.

Does it need to be positive? No. You'll see that I used $2$ negative values ( $y_2=-1$ and $y_4 = -4$) in my final evaluation of $x$. These were the ones I got by using the Euclidean Algorithm to solve the equations. This gave me the value $x = -337$, 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 $330$ to obtain further, equally valid, values of $x$. In general, then, any value given by $x = -337 + 330n$ will work.

How did I get from $-1$ to $2$? It may sound trivial, but I added $3$. Why?

$y_2=-1, n_2 = 37$ was a solution to the equation:
$3n_2+110y_2=1$
which again I found using the Euclidean Algorithm. But, since this is simply a solution to the modular equation
$110y_2\equiv 1\mod 3$
any value of $y_2$ that is equivalent to $-1 \mod 3$ will do equally well. So that's $2, 5, 8, ..., -4, -7, ...$ and so on. Each different value of $y_2$ will have a different value of $n_2$ (for example, $y_2=2$ will require $n_2 = -73$), but any one of these could be used in the final calculation of $x$.

Can you see why? It's because in the formula for $x, y_2$ is multiplied by $220$. So two values of $y_2$ that differ by $3$ will result in a value of $x$ that differs by $660$, and as we've seen, that will work just as well.

I hope that helps to clarify things.