System of Linear Equations for Congruency

Question

So this is my question:
Find all x such that $4x=3 \pmod{21}$, $3x=2 \pmod{20},$ and $7x=3 \pmod{19}$

So I know I have to use chinese remainder theorem and I know how to do it if $x$ didn't have a coefficient in front of it. In other words, if it was like:
$x=3 \pmod{21}$, $x=2 \pmod{20},$ and $x=3 \pmod{19}$

Then I would be able to do it. All you would have to do is pick a pair, list out the congruency and find the commonality. But how do I do it with the coefficients?

Answer 1

You can use the fact that the coefficient of $x$ is coprime to the modulus in each case, hence a unit. In the first case, $4\cdot 16=1\pmod{21}$, so $$ 4x=3\pmod{21}\iff x=3\cdot 16=6\pmod{21}. $$

Also, $3\cdot 7=1\pmod{20}$, so $$ 3x=2\pmod{20}\iff x=14\pmod{20}. $$

I'll leave the last one for you. Try using the Euclidean Algorithm on $7$ and $19$ to find an inverse if you get stuck. So you can get an equivalence system of congruences, and solve with CRT, as you mention you are familiar with.

Answer 2

Using the Convergent proeprty of continued fraction, $$\frac{21}4=5+\frac14$$

The last but one convergent is $5$ $\implies 21-4\cdot5=1\implies 4\cdot5\equiv-1\pmod{21}\implies 4^{-1}\equiv-5\equiv16$

So, $4x\equiv 3\pmod{21}$ becomes $x\equiv16\pmod{21}--->(1)$

$$\frac{20}3=6+\frac23=6+\frac1{\frac32}=6+\frac1{1+\frac12}$$ The last but one convergent is $6+\frac11=7$ $\implies 20\cdot1-3\cdot7=-1\implies 3\cdot7\equiv1\pmod{20}\implies 3^{-1}\equiv7$

$3x\equiv2\pmod{20}$ becomes $x\equiv2\cdot7\pmod{20}\equiv14--->(2)$

$$\frac{19}7=2+\frac57=2+\frac1{\frac75}=2+\frac1{1+\frac25}=2+\frac1{1+\frac1{\frac52}}=2+\frac1{1+\frac1{2+\frac12}}$$

The last but one convergent is $2+\frac1{1+\frac1{2}}=\frac83$ $\implies 19\cdot3-7\cdot8=1\implies 7\cdot8\equiv-1\pmod{19}\implies 7\equiv-8\equiv11$

$7x\equiv3\pmod{19}$ becomes $x\equiv3\cdot11\pmod{19}\equiv14--->(3)$

Applying Chinese Remainder Theorem on $(1),(2),(3)$, $$x\equiv 16\cdot19\cdot20\cdot b_1+14\cdot19\cdot21\cdot b_2+14\cdot20\cdot21\cdot b_3\pmod{ 19\cdot20\cdot21} $$ where

$19\cdot20\cdot b_1\equiv1\pmod {21}\implies (-2)(-1)b_1\equiv1\pmod {21}\implies b_1\equiv11\pmod{21}$ as $\frac{21}2=10+\frac12\implies 21\cdot1-2\cdot10=1\implies 2^{-1}\equiv-10\pmod{21}\equiv11$

$19\cdot21\cdot b_2\equiv1\pmod {20}\implies (-1)(1)\cdot b_2\equiv1\pmod {20}\implies -b\equiv1$ or $b\equiv-1\equiv19\pmod{20}$

$20\cdot21\cdot b_3\equiv1\pmod {19}\implies (1)(2)b_3\equiv1\pmod {19}\implies b_3\equiv10\pmod{19} $ as $\frac{19}2=9+\frac12\implies 19\cdot1-10\cdot2=-1\implies 2^{-1}\equiv10\pmod{19}$