System of Linear Congruences

Question

Find all $x$ such that

\begin{align} x&\equiv 1 \pmod {12}\\ x&\equiv 4 \pmod {21}\\ x&\equiv 18 \pmod {35} \end{align}

Im not quite sure if this system of linear congruence is solvable. Since $\gcd(12,21) =3$, $\gcd (12,35)=1$ and $\gcd(21,35) = 7$, and the CRT states that "If(m1, m2) = 1, then the system has its complete solution a single resident class (mod m1.....mr).

Answer 1

LCM of $12,21,35$ is $420$. Looking at what numbers $x$ could be congruent to $\mod 420$ from the congruence $x\equiv18\mod35$ gives 12 numbers. These are:

$$18,53,88,123,158,193,228,263,298,333,368,403.$$

Using $x\equiv1\mod12$, we see it must be odd in the above list. So get get

$$\require{cancel}\cancel{18},53,\cancel{88},123,\cancel{158},193,\cancel{228},263,\cancel{298},333,\cancel{368},403.$$

Next subtracting $1$ and checking if it is a multiple of 12 leaves just the number $193$ standing.

Final check: $21\cdot9+4=193$. So the answer is $$x\equiv193\mod{420}$$

Answer 2

When the moduli are not coprime, you can proceed like this: $x\equiv 1 \pmod{12}$ so $x=1+12y$ for some $y$.

Then $x\equiv 1+12y \equiv 4 \pmod{21}$, which has solution $y\equiv 2 \pmod{7}$, so $y=2+7z$ for some $z$ and we have $x = 1+12(2+7z)=25+84z.$

Then $x \equiv 25+84z \equiv 18 \pmod{35}$ which has solution $z=2 \pmod{5}$.

So $x = 25+84(2+5w) = 193 + 420 w$, which is to say $x\equiv 193 \pmod{420}.$

Answer 3

\begin{align} x&\equiv 1\phantom {8} \pmod {{\color{blue}{12}}}\tag {1}\\ x&\equiv 4\phantom {8} \pmod {{\color{teal}{21}}}\tag {2}\\ x&\equiv 18 \pmod {{\color{blue}{35}}}\tag{3} \end{align}

Since $\gcd(12,35)=1 $ you can first apply the Chinese Remainder Theorem to find the solution to the two simultaneous congruences $(1)$ and $(3) $, which is of the form of

$$x\equiv x_0\pmod{12\cdot 35} \equiv x_0\pmod { 420}.\tag {4}$$

To compute the smallest positive value $x_{\min} $ of $ x_0 $, using the Chinese Remainder Theorem proceed as follows:

1. since $12$ and $35$ are relatively prime, there is an $r$ and an $s$ such that $r\cdot 12 + s\cdot 35 = 1$. Indeed, $3\cdot 12 + (-1)\cdot 35 = 1$, so $r = 3$ and $s = -1$;
2. in general, if $\gcd(m,n)=1 $, then the set of all solutions of the system \begin{align} x& \equiv a \pmod {m}\\ x& \equiv b \pmod {\; n} \end{align}
   is given by the condition $x\equiv a\cdot s\cdot n + b\cdot r\cdot m \pmod {m\cdot n}$. Hence $$x \equiv 1\cdot (-1)\cdot 35 + 18\cdot 3\cdot 12 \equiv 613\equiv 613-420\equiv 193\pmod {420};\tag {5}$$

Finally solve the following two simultaneous congruences \begin{align} x\equiv &193\pmod{420} \tag {5}\\ x\equiv &4\phantom{93}\pmod{\phantom { 4}{\color {teal}{21}}};\tag {2} \end{align} Since $420\equiv 0\pmod{\color{teal}{21}}$ and $193\equiv 4\pmod{\color {teal}{21}}$, the solution of the given system is

$$x\equiv 193\pmod{420}. \tag {6}$$