2
$\begingroup$

The problem is : $$19x\equiv1 \pmod {140}$$ The gcd is 1. Hence one unique solution exists. but, $$152x\equiv8 \pmod {140}$$ Dividing by 4,we get $$12x\equiv 8 \pmod {35}$$ Eventually we get from this $$x\equiv 24 \pmod {35}$$ My question is this (these) solution also an incongruent solution to the original congruence. also in the 2nd congruence $(152,140)=4$ , so 4 incongruent solutions??

$\endgroup$
3
  • $\begingroup$ How did you obtain $12x\equiv 8 \pmod {35}$ from $152x\equiv8 \pmod {140}$? $\endgroup$ – user Feb 1 '18 at 18:35
  • $\begingroup$ You can derive from $152x\equiv8 \pmod {140}\implies 12x\equiv8 \pmod {140}\implies 3x\equiv2 \pmod {35}$ $\endgroup$ – user Feb 1 '18 at 18:41
  • $\begingroup$ Please, if you are ok, you can accept the answer and set it as solved. Thanks! $\endgroup$ – user Feb 2 '18 at 21:16
1
$\begingroup$

Since $$\gcd(19,140)=1$$ we can directly calculate the inverse of $19 \pmod{140}$ by Euclidean algorithm.

As an alternative by CRT note that the equation

$$19x\equiv1 \pmod {140}$$

is equivalent to the system

$$\begin{cases} 19x\equiv1 \pmod {7} \implies 5x\equiv1 \pmod {7}\implies x\equiv3 \pmod {7}\\\\ 19x\equiv1 \pmod {5}\implies4x\equiv1 \pmod {5}\implies x\equiv-1 \pmod {5}\\\\ 19x\equiv1 \pmod {4}\implies 3x\equiv1 \pmod {4}\implies x\equiv-1 \pmod {4}\end{cases}$$

thus

$$\begin{cases}x\equiv3 \pmod {7}\\\\ x\equiv-1 \pmod {20} \implies x=-1+20k \end{cases}$$

then

$$x\equiv3 \pmod {7} \implies-1-k\equiv 3 \pmod 7\implies k\equiv 3 \pmod 7$$

therefore

$$x=59$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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