# 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 $\displaystyle x$ satisfies $\displaystyle 3x\equiv 6(\bmod 15)$ and $\displaystyle 2x\equiv 10(\bmod 12)$ if and only if $\displaystyle 3x\equiv 6(\bmod 3),3x\equiv 6(\bmod 5), 2x\equiv 10(\bmod 4), 2x\equiv 10(\bmod 3)$.

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

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

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

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

Therefore, we are left with, $\displaystyle 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 $\displaystyle x\equiv 2(\bmod 3)\text{ and }x\equiv 2(\bmod 5)$ is equivlanet to $\displaystyle x\equiv 2(\bmod 15)$ because $\displaystyle \gcd(3,5)=1$. Thus, we are left with $\displaystyle x\equiv 1(\bmod 2)\text{ and }x\equiv 2(\bmod 15)$. Note that $\displaystyle 17\equiv 1(\bmod 2),17\equiv 2(\bmod 15)$ so we have $\displaystyle x\equiv 17(\bmod 2)\text{ and }x\equiv 17(\bmod 15)$. This combines into $\displaystyle x\equiv 17(\bmod 30)$ since $\displaystyle \gcd(2,15)=1$.