Chinese remainder theorem

**oldguynewstudent** · November 17th 2009, 10:13 AM

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.

**tonio** · November 17th 2009, 11:12 AM

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

**oldguynewstudent** · November 18th 2009, 02:19 AM

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

**Grandad** · November 18th 2009, 02:31 AM

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$ .

Grandad

**oldguynewstudent** · November 18th 2009, 09:54 AM

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

**mathceleb** · November 20th 2009, 12:00 PM

Originally Posted by Grandad

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)

Grandad,

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?

**Grandad** · November 20th 2009, 12:57 PM

Hello mathceleb

Originally Posted by mathceleb

Grandad,

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?

You're asking 3 questions here.

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.

Grandad

Thread: Chinese remainder theorem

LinkBack

Thread Tools

Display

Chinese remainder theorem

I was missing a step

Chinese Remainder Theorem

Aha

Similar Math Help Forum Discussions

Chinese Remainder Theorem

Chinese Remainder Theorem

Chinese remainder theorem 2

chinese remainder theorem

Chinese Remainder Theorem

Search Tags