CRT Intermediate

Problem - 4199

Solve the congruent system: $4x\equiv 2\pmod{6}$ and $3x\equiv 5\pmod{8}$.


Let's start by simplifying the first equation to $2x\equiv 1\pmod{3}$. While $3$ and $8$ are now co-prime, we need to adjust the coefficient to $1$ in order to apply the CRT. Note $2^{-1}\equiv 2\pmod{3}$ and $3^{-1} \equiv 3\pmod{8}$, we have

$$\left\{  \begin{array}{lr} x \equiv 2 &\pmod{3} \\ x \equiv -1 &\pmod{8} \end{array} \right.$$

Applying CRT gives $$x\equiv 2\times 8\times 2 +(-1)\times 3\times 3\equiv 23\pmod{24}$$

Additionally, we can rewrite the first relation as $x\equiv 2\equiv -1\pmod{3}$. Then, the solution must be one less the least common multiple of $3$ and $8$ which leads to the same result.

report an error