Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.