[Math] Chinese Remainder Theorem and linear congruences

elementary-number-theorymodular arithmetic

I have found the following congruences:

  1. $x \equiv 2\mod 5$
  2. $x \equiv 12\mod27$
  3. $x \equiv 2\mod4$

How can I solve for x using the Chinese Remainder Theorem? Please include justifications for the steps you take.

How can I find $x$?

Best Answer

Hint $\ $ Note that by the constant-case optimization of CRT we have

$$\rm\begin{eqnarray} x\equiv 2\pmod 4\\\rm x\equiv 2\pmod 5\end{eqnarray}\ \iff\ x\equiv 2\pmod{4\cdot 5}$$

Now applying Easy CRT to the RHS congruence and the remaining congruence we obtain

$$\rm\begin{eqnarray} x\equiv \color{#C00}2\pmod{\color{blue}{20}}\\\rm x\equiv \color{#0A0}{12}\pmod{27}\end{eqnarray}\ \iff\ x\equiv \color{#0A0}{12}+27\,\left[\dfrac{\color{#C00}2\!-\!\color{#0A0}{12} }{27}\ mod\ \color{blue}{20}\right]\equiv 282\pmod{\color{blue}{20}\cdot 27}$$

where the above fraction is computed as $\rm\, mod\ 20\!:\ \dfrac{10}{27}\equiv \dfrac{10}{7}\equiv\dfrac{30}{21}\equiv \dfrac{10}1,\ $ and $\rm\:-10\equiv 10$