Find how many solutions the following equation has:
$x^3\equiv 5 \pmod {143}$
Using Euler's criterion I found that the equation $x^3\equiv 5 \pmod {11}$ has one solution, and $x^3\equiv 5 \pmod {13}$ has 3 solutions.
How can I conclude from that how many solutions the original equation has? I thought maybe to use the CRT.
Best Answer
If you have $m$ solutions to $f(x)\equiv0\bmod p$ and $n$ to $f(x)\equiv0\bmod q$, every pair of solutions to the sub-congruences combines by the CRT into a distinct solution modulo $pq$, so there are $mn$ solutions to the mod-$pq$ congruence.
Thus, in your case, there are $3×1=3$ solutions.