# congruence

• February 1st 2009, 06:05 PM
Sally_Math
congruence
how do i solve this system
x=3 (mod 5), x= 5 (mod 7), x=7 (mod 11),

can i please get some help with a step by step process

(Bow)
• February 1st 2009, 08:03 PM
JaneBennet
First, look at the first two congruences.

$x\equiv3\pmod5\ \Rightarrow\ 7x\equiv21\pmod{35}\ \Rightarrow\ -14x\equiv-42\pmod{35}$
$x\equiv5\pmod7\ \Rightarrow\ 5x\equiv25\pmod{35}\ \Rightarrow\ 15x\equiv75\pmod{35}$

Adding gives $x\equiv33\pmod{35}\equiv-2\pmod{35}.$

Now compare this with the last congruence.

$x\equiv-2\pmod{35}\ \Rightarrow\ 11x\equiv-22\pmod{385}\ \Rightarrow\ 176x\equiv-352\pmod{385}$
$x\equiv7\pmod{11}\ \Rightarrow\ 35x\equiv245\pmod{385}\ \Rightarrow\ -175x\equiv-1225\pmod{385}$

And adding, $x\equiv-1577\pmod{385}\equiv348\pmod{385}.$

So the solution set is $\{348+385k:k\in\mathbb{Z}\}.$
• February 1st 2009, 10:11 PM
GaloisTheory1
also:

you may find this helpful:

here