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

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.

• Just apply extended euclidean algorithm to two of the congruences, then to the result apply the third. Commented Oct 31, 2018 at 2:18
• Do you know, Pratyush, what $u,v,w$ stand for? how they are defined? No good "knowing" a formula, if you don't know what the letters mean. Also, when you write "Euler", chances are you mean "Euclid". Commented Oct 31, 2018 at 2:30
• @GerryMyerson I do know what they mean. Commented Oct 31, 2018 at 2:31
• @RushabhMehta so would I first solve x = 21u + 28v and then solve for w later? Commented Oct 31, 2018 at 2:32
• Good. So, tell us, Pratyush: what do they mean? Commented Oct 31, 2018 at 2:34

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

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