Elementary Congruence problem

Question

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

Answer 1

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