Find all solutions to the system $x \equiv 1 \pmod 4, x \equiv 0 \pmod 3$, and $x \equiv 5 \pmod 7$

Question

Find all solutions to the congruences $x \equiv 1 \pmod 4, x \equiv 0 \pmod 3$, and $x \equiv 5 \pmod 7$.

I got $M =m_1 * m_2 * m_3 = 4*3*7 = 84$

$M_1 = 21, M_2 = 28, M_3 = 12$

So I get $x = 21*u + 28*v + 12*w$

Now I don't know how to get $u, v$, and $w$. I know that I am supposed to use Chinese Remainder Theorem and Euler's algorithm but I don't know how to use them here. Can someone please help me. Or suggest me something easier.

Answer 1

By CRT $\, x\, \equiv\, 1\cdot 21\,(\color{#c00}{21^{-1}}\!\bmod 4) + 0\cdot 28\,(28^{-1}\!\bmod 3) + 5\cdot12\,\color{#0a0}{(12^{-1}}\!\bmod 7)\ \ \pmod{84}$

$\quad \bmod 4\!:\,\ \color{#c00}{21^{-1}}\equiv 1^{-1}\equiv \color{#c00}1$

$\quad \bmod 7\!:\,\ \color{#0a0}{12^{-1}}\equiv (-2)^{-1}\equiv 1/(-2)\equiv 8/(-2)\equiv -4\equiv\color{#0a0}{ 3}$

Therefore $\ x\,\equiv\, 1\cdot 21\cdot\color{#c00} 1\, +\, 0\, +\, 5\cdot 12\cdot\color{#0a0} 3\equiv 201\equiv 33\pmod{84}.\ \ $ Aternative below.

---

$\!\bmod 3\!:\,\ x\equiv 0\iff x = 3j$

$\!\bmod 7\!:\,\ x = 3j \equiv 5 \equiv 12\iff j \equiv 4\iff x = 3(4+7k) = 12+21k$

$\!\bmod 4\!:\,\ 1\equiv x = 12+21k\equiv k\iff x = 12+21(1+4n) = 33+84n$

Answer 2

We have $x\equiv 0 \pmod 3.$

Since $\gcd(3,4)=1,$ the set $\{0+3n:1\leq n\leq 4\}$ is a complete residue system modulo $4.$ So just one member $(0+3\cdot 3=9)$ is congruent to $1$ mod $4.$ So $x\equiv 9 \pmod {3\cdot 4}.$

Since $\gcd(3\cdot 4,7)=1$ the set $\{9+12m: 1\leq m\leq 7\}$ is a complete residue system modulo $7.$ So just one member $(9+12\cdot 2=33)$ is congruent to $5$ mod $7.$ So $x\equiv 33 \pmod {3\cdot 4\cdot 7}.$