# Math Help - Simultaneous Linear Congruences.

1. ## Simultaneous Linear Congruences.

I am confused about how I am to solve simultaneous linear congruences, in the book I am reading I am only given 1 example and no general principle.

Solve

$x\equiv1\mbox{mod}(4)\ \ \ x\equiv2\mbox{mod}(3)\ \ \ \ x\equiv3\mbox{mod}(5)$

From the example i think i have to:
$n_1=4\ \ \ n_2=3\ \ \ \ n_3=5\ \ \ n=60$ and $c_1=15\ \ c_2=20\ \ \ c_3=12$

and so i have:

$15x\equiv1\mbox{mod}(4)\rightarrow{3x\equiv1\mbox{ mod}(4)$
$20x\equiv1\mbox{mod}(3)\rightarrow{2x\equiv1\mbox{ mod}(3)$
$12x\equiv1\mbox{mod}(5)\rightarrow{2x\equiv1\mbox{ mod}(5)$

but after this I am lost (im not sure any of that is correct either,

Thanks very much for any help

2. Are you sure you have written this correctly? The same x cannot be equivalent to both 1 and 3 modulo 4. That would be like solving a set of simultaneous equations that included both "x= 1" and "x= 3"!

I will, however, show what I would do if it were, say, $x\equiv 7 (mod 9)$, $x\equiv 3 (mod 5)$ and $x\equiv 1 (mod 4)$ where I have changed the "mod" for one equation.

Saying that $x\equiv 7 (mod 9)$ means that x= 7+ 9i for any integer i.

Now put that into the next equation: $x\equiv 3 (mod 5)$ becomes $7+ 9i\equiv 2+ 4i\equiv 3$ (I have reduced 7 and 9 modulo 5) which is the same as $4i\equiv 1 (mod 5)$. Since $4(4)= 16\equiv 1 (mod 5)$, That says that $i\equiv 4 (mod 5)$ so i= 4+ 5j for any integer j. Putting that back into the formula for x, $x= 7+ 9(4+ 5j)= 43+ 45j$.

Now the third equation, $x\equiv 1 (mod 4)$ becomes $43+ 45j\equiv 3+ j\equiv 1 (mod 4)$ which is the same as $j\equiv 2 (mod 4)$. And that, in turn gives $j= 2+ 4m$ for any integer m. Putting that into the formula for x, we get $x= 43+ 45(2+ 4m)= 133+ 180m$ as our answer.

To check, note that 133/9= 14+ 7/9 so x= 133 does satisfy $x\equiv 7 (mod 9)$. 133/5= 26+ 3/5 so x= 133 does satisfy $x\equiv 3 (mod 5)$ and, finally, 133/4= 33+ 1/4 so x= 133 does satisfy $x\equiv 1 (mod 4)$.

The fact that adding any multiple of 180 to 133 will still give a solution is clear because 180= 9(5)(4) is congruent to 0 mod 9, 5, and 4.

3. You are right i completely messed that question up in asking it I am very sorry it should have been:

$x\equiv1\mbox{mod}(4)\ \ \ x\equiv2\mbox{mod}(3)\ \ \ \ x\equiv3\mbox{mod}(5)$

following on from what i have from my textbook i would have that

$x_0=1.15.3+2.20.2+3.12.2=197mod(60)\equiv17mod(60) )$ but the answer at the back is 57mod(60)

thanks very much for any help