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

Grandad