|
So this is my question: 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: 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? |
||||
|
|
|
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. |
|||
|
|
|
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}$ |
|||
|
|
