Consider this system of congruence equations.

Question

\begin{cases} 4x \equiv 14 \pmod m \\ 3x \equiv 2 \pmod 5 \end{cases}

I want to prove that for $m \in 4\mathbb{Z}$ there are no solutions(1). Moreover, I want to determine all m for which I have solutions(2).

First of all, the second equation is equivalent to $ x \equiv 4$ (mod 5).

If $m$ and $5$ are coprime, the Chinese remainder theorem states that I have solution, so I pick $m$ and $5$ not coprime. In this case, $m = 5t$ for some $t \in \mathbb{Z}$. I can write: $$ 4x = 14 + (5t)c$$ $$ 4x = 4 + 5(2 + tc)$$ $$ 4x = 4$$ $$ x \equiv 1 mod 5$$ However, I also have that $ x \equiv 4 \pmod 5$, so there are no solution. In the proof I did not use the fact that $m$ is a multiple of $4$, so I think the answer for (2) is that we have solution only for $(m,a) = 1$. Is that right?

Answer 1

The solutions to the second equation are the integers of the form $4+5k$. So, for a given $m$, having a solution to both equations is equivalent to having a $k$ and a $k_1$ such that $4(5k+4)=14+mk_1$ which is true iff $20k-mk_1=-2$. This has a solution iff $gcd(20,m)|2$.

The Chinese Remainder theorem does not work here since you need the left hand side to be $x$ without a coefficient for all of the congruence relations to apply the theorem.

Answer 2

If $m$ is a multiple of $4$, then $4x \equiv 14 \bmod m$ implies $0 \equiv 4x \equiv 14 \equiv 2 \bmod 4$, a contradiction.

Answer 3

If $m=4n$, then

\begin{align} 4x \equiv 14 \pmod m &\implies 4x \equiv 14 \pmod{4n} \\ &\implies 4n \mid 14-4x \\ &\implies 2 \mid 7-2x \\ &\implies 2 \mid 7 \end{align}

which is false.

---

$3x \equiv 2 \pmod 5 \implies x \equiv 4 \pmod 5 \implies x = 4 + 5u$ for some integer, $u$.

\begin{align} 4x \equiv 14 \pmod m &\implies 4(4 + 5u) \equiv 14 \pmod m \\ &\implies 16 + 20u \equiv 14 \pmod m \\ &\implies 20u \equiv -2 \pmod m \\ &\implies m \mid 2(10u+1) \end{align}

If $u=0$, we get $x=4$ and $m \mid 2$

If $u=1$ we get $x=9$ and $m \mid 22$

$\dots$

So $x=4+5u$ and $m \mid 2(10u+1)$

Check

$3x = 12 + 15u \equiv 2 \pmod 5$

$4x - 14 = 16 + 20u - 14 = 20u + 2 = 2(10u+1)$

So $m \mid 2(10u+1) \implies m \mid 4x-14 \implies 4x \equiv 14 \pmod m$.