Solving system of congruences where $m$'s are not coprime

Question

I'm really struggling with how to find the solution to a system of congruences where the m_i's are not relatively prime. For example:

$x ≡ 3 (mod4)$

$x ≡ 1 (mod6)$.

I know this has a unique solution mod 12 but I'm stuck here. I read through some similar questions but I'm still confused. Since I can't use the Chinese Remainder Theorem, how do I find the solution?

Answer 1

Write $$4k+3 =x=6l+1$$ so we have $$2k+1=3l \Longrightarrow 2\mid 3l-1 \Longrightarrow 2\mid l-1 \Longrightarrow l-1=2n$$ Thus $l=2n+1$ and $k=3n+1$ and finally $x= 12n+7$. Or if you want $x\equiv 7 \pmod {12}$.

Answer 2

You use the CRT for each modulus, then combine the results. For your system, $x \cong 3 \pmod{4}$ just gives you that congruence (because $4$ is a power of a prime) and then $x \cong 1 \pmod{6}$ gives \begin{align*} x &\cong 1 \pmod{2} \\ x &\cong 1 \pmod{3} \text{.} \end{align*}

The first of these is redundant with the previous equation ("$x$ is odd" is compatible with but tells you less than $x \cong 3 \pmod{4}$.) So your three equations reduce to \begin{align*} x &\cong 3 \pmod{4} \\ x &\cong 1 \pmod{3} \text{.} \end{align*}

Then reassemble using the CRT: $x \cong 7 \pmod{12}$.

Answer 3

For small values, like your problem, you can use the method of adding the modulus:

$\pmod{6}: x\equiv 1\equiv 7 $.

Then noting that also $7\equiv 3 \pmod{4}$, you have your solution:

$x\equiv 7 \pmod{12}$

(Sometimes you may have to add the modulus more than once.)