# Thread: simultaneous congruence that isn't working

1. ## simultaneous congruence that isn't working

find a general solution to the simultaneous congruence equations:

3x congruent to 6 mod 15
2x congruent to 10 mod 12

solving the first, 3x = 15t + 6

i.e. x = 5t + 2

plugging this into the second, 2(5t + 2) congruent to 10 mod 12

i.e. 10t congruent to 6 mod 12

so 10t = 12z + 6

i.e. 5t = 6z + 3

so x = 5t + 2 = 6z + 5

this works for the second, but not the first. What am I doing wrong?

2. Originally Posted by minivan15
find a general solution to the simultaneous congruence equations:

3x congruent to 6 mod 15
2x congruent to 10 mod 12
An integer $x$ satisfies $3x\equiv 6(\bmod 15)$ and $2x\equiv 10(\bmod 12)$ if and only if $3x\equiv 6(\bmod 3),3x\equiv 6(\bmod 5), 2x\equiv 10(\bmod 4), 2x\equiv 10(\bmod 3)$.

Look at $3x\equiv 6(\bmod 3)$ first. This is a completely unnecessary congruence because regardless of what $x$ is this congruence always holds, therefore we can throw it away.

Look at $3x\equiv 6(\bmod 5)$, since $\gcd(3,5)=1$ you can divide both sides by $3$ to get an equivalent congruence $x\equiv 2(\bmod 5)$.

Look at $2x\equiv 10(\bmod 4)$, since $\gcd(2,4)=2$ and $\tfrac{4}{2}=2$ we replace it by and equivalent congruence $x\equiv 5(\bmod 2)$ after dividing by 2. This can be further simplifed to the congruence $x\equiv 1(\bmod 2)$.

Look at $2x\equiv 10(\bmod 3)$, since $\gcd(2,3)=1$ we get $x\equiv 2(\bmod 3)$.

Therefore, we are left with, $x\equiv 1(\bmod 2),x\equiv 2(\bmod 3),x\equiv 2(\bmod 5)$. These congruences now get solved with the Chinese remainder theorem, however I liked to do it without the Chinese remainder theorem, so I show you how I do these sort of problems. Notice that $x\equiv 2(\bmod 3)\text{ and }x\equiv 2(\bmod 5)$ is equivlanet to $x\equiv 2(\bmod 15)$ because $\gcd(3,5)=1$. Thus, we are left with $x\equiv 1(\bmod 2)\text{ and }x\equiv 2(\bmod 15)$. Note that $17\equiv 1(\bmod 2),17\equiv 2(\bmod 15)$ so we have $x\equiv 17(\bmod 2)\text{ and }x\equiv 17(\bmod 15)$. This combines into $x\equiv 17(\bmod 30)$ since $\gcd(2,15)=1$.