1. ## Chinese remainder theorem

Thanks for the wonderful help I've been getting!

Here is a problem with the Chinese Remainder Theorem:

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

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

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

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

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

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

I don't understand how the rest of the steps work if now we have to go back and use:
30 $\displaystyle \equiv$ 8 (mod 11) then 8$\displaystyle y_4$ $\displaystyle \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 $\displaystyle \equiv$ 1(mod 2)
x $\displaystyle \equiv$ 2(mod 3)
x $\displaystyle \equiv$ 3(mod 5)
x $\displaystyle \equiv$ 4(mod 11)

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

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

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

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

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

I don't understand how the rest of the steps work if now we have to go back and use:
30 $\displaystyle \equiv$ 8 (mod 11) then 8$\displaystyle y_4$ $\displaystyle \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 $\displaystyle y_1=1\,,\,y_2=2\,,\,y_3=1\,,\,y_4=7$ $\displaystyle \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 $\displaystyle y_1=1\,,\,y_2=2\,,\,y_3=1\,,\,y_4=7$ $\displaystyle \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$\displaystyle y_1$ $\displaystyle \equiv$ 1(mod 2) $\displaystyle \Rightarrow$ $\displaystyle y_1$ = 1

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

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

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

Substituting in the above equation gives x = 1643 $\displaystyle \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 $\displaystyle \equiv$ 1(mod 2)
x $\displaystyle \equiv$ 2(mod 3)
x $\displaystyle \equiv$ 3(mod 5)
x $\displaystyle \equiv$ 4(mod 11)

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

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

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

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

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

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

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

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

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

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

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

For $\displaystyle y_4$, let me do the working in full, using the Euclidean Algorithm. We need to solve:
$\displaystyle 11n_4+30y_4 = 1$
So we say:
$\displaystyle 30 = 2\times11+8$
$\displaystyle 11=1\times8+3$
$\displaystyle 8=2\times3+2$
$\displaystyle 3=2+1$
Then we 'go back' (perhaps this is what you meant):
$\displaystyle 1=3-2$
$\displaystyle =3-(8-2\times3)$
$\displaystyle =3\times3-8$
$\displaystyle =3\times(11-8)-8$
$\displaystyle =3\times11-4\times8$
$\displaystyle =3\times11-4(30-2\times11)$
$\displaystyle =11\times11-4\times30$
$\displaystyle \Rightarrow n_4=11, y_4 = -4$
Finally, we use these four values of $\displaystyle y_i$ to calculate $\displaystyle x$:
$\displaystyle 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 $\displaystyle 330$'s ($\displaystyle =2\times3\times5\times11$) as you like. The smallest positive value of $\displaystyle x$, then, is $\displaystyle -337+2\times330 =323$; and to get the solution which (by chance!) you found, add $\displaystyle 6\times 330 = 1980$ to get $\displaystyle 1643$.

5. ## Aha

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

For $\displaystyle y_2$: solve $\displaystyle 3n_2+110y_2=1$. This gives $\displaystyle n_2=37, y_2 = -1$ (which is equivalent to $\displaystyle 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 $\displaystyle y_2 = 2$? We don't. $\displaystyle -1$ works just as well. See below.

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

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

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

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

I hope that helps to clarify things.