CRT solvability for congruence systems of fraction form $\ a_i x\equiv b_i\pmod{\!m_i}$

Question

I have to see for which value of $a$ this system is solvable: $$ \begin{cases} 3x \equiv a\pmod{28}\\ ax \equiv4\pmod{21}\\ \end{cases} $$ I check the two congruences separately: $$ \gcd(3,28)=1\mid a\;\checkmark $$ $$ \gcd(a,21)\mid4 \iff \gcd(a, 21) = 1 \iff a \not\equiv 0\;(7)\;\land a \not\equiv 0\;(3) $$

$$ \begin{cases} 3x \equiv a\pmod{4}\\ ax \equiv4\pmod{3}\\ \end{cases}\\ \gcd(4,3) = 1\;\checkmark $$ $$ \begin{cases} 3x \equiv a\pmod{7}\\ ax \equiv4\pmod{7}\\ \end{cases} $$ and from here I can't go on.

So, my problem is that I can't figure out how to check if a system of congruences is solvable.

EDIT:

maybe I found the solution: $ \gcd(7,7) = 7\mid a-4 \iff a = 11+7k \land a \not\equiv 0\;(7)$

Answer 1

There is no $a$ for which the system is solvable. By the Chinese Remainder Theorem, $$ 3x \equiv a \pmod{28} \\ ax \equiv 4 \pmod{21} $$ is equivalent to solving: $$ 3x \equiv a \pmod{7} \\ 3x \equiv a \pmod{4} \\ ax \equiv 4 \pmod{7} \\ ax \equiv 4 \pmod{3} \\ $$

Note that the first equations tells us $x \equiv 5a \pmod{7}$, and the third equation tell us $5a^{2} \equiv 4 \pmod{7} \implies a^{2} \equiv 5 \pmod{7}$, but $5$ is not a quadratic residue mod $7$. The quadratic residue are $1,2,4$ mod $7$. Hence, there is no solution. Let me know if you have any questions.

Answer 2

$3x \equiv a \bmod 7$ and $ax \equiv 4 \bmod 7$ imply $3x^2 \equiv 4 \bmod 7$ or $x^2 \equiv -1 \bmod 7$. There is no such $x$.

Answer 3

Below we show how to reduce it to the well-known CRT solvability condition, and that it has a very intuitive natural interpretation in terms of modular fraction equivalence. Our system is

$$\begin{align} &\color{#90f}3x \equiv a\!\!\pmod{28}\\ &\color{#0a0}{\color{#c00}ax} \color{#0a0}{\equiv 4\!\!\pmod{\color{#c00}{21}}} \end{align}\qquad$$

Recall if $\,\color{#0a0}{\color{#c00}a\:\!x+\color{#c00}{21}\:\!y = 4}\,$ is solvable then $\,\color{#c00}{g := (a,21)}\mid \color{#0a0}4\,$ so $\,g\mid 21,4\Rightarrow \color{#c00}{g=1}.\,$ So by Theorem below the system is solvable $\!\iff\!\bmod 7\!:\ a\color{#c00}a\equiv \color{#90f}3\cdot\color{#0a0} 4\equiv -2\,\overset{\rm cube}\Rightarrow a^{\large 6}\equiv -1,\,$ contra lil Fermat.

Theorem $\ $ If $\,(a,m) = \color{#c00}{1 = (c,n)}\,$ then

$$\exists\, x\!:\ \begin{align} &\color{#90f}ax\equiv b\!\!\pmod{\!m}\\ &\:\!\color{#0a0}{\color{#c00}cx}\color{#0a0}{\equiv d\!\!\pmod{\!\color{#c00}n}}\end{align} \iff \color{#90f}a\color{#0a0}d\equiv b\color{#c00}c\!\!\pmod{(m,n)}\qquad$$

Proof $\ $ By hypotheses and Bezout: $\,a^{-1}$ exists mod $m\,$ and $\,c^{-1}$ exists mod $n,\,$ so

$$\exists\, x\!:\ \begin{align} ax&\equiv b\!\!\pmod{\!m}\\cx&\equiv d\!\!\pmod{\!n}\end{align}\iff \exists\, x\!:\!\!\!\!\!\begin{array}{} &x\equiv b/a\,\pmod{\!m}\\&x\equiv d/c\: \pmod{\!n}\end{array}\quad$$

By the well-known CRT solvability criterion the prior system is solvable iff

$$\bmod (m,n)\!:\,\ b/a\equiv x \equiv d/c\!\!\overset{\times\ ac\!}\iff bc\equiv ad$$

where we used $\,(a,(m,n)) = 1 = (c,(m,n))\, $ by $(a,m) = 1 = (c,n),\,$ therefore scaling by the units (invertibles) $\,a,c\,$ yields an equivalent congruence $\bmod (m,n)$.

Remark $ $ This solvability criterion is much more intuitive in fractional language, where it becomes the modular version of the cross-multiplication test for modular fraction equivalence, i.e.

$$\exists\, x\!:\ \begin{align} x&\equiv \frac{b}a\!\!\pmod{\!m}\\[.2em]x&\equiv \frac{d}c\!\!\pmod{\!n}\end{align}\!\iff \frac{b}a\equiv \frac{d}c\!\! \pmod{\!(m,n)}\qquad$$

This is a natural fractional extension of the said CRT solvability criterion (it is a version of CRT in the ring of fractions writable with denominator coprime to to both $m$ and $n$, a fundamental construction whose properties are developed at length when one studies commutative algebra).