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).


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:


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


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}$$


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}.$


\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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.