Using the Chinese Remainder Theorem:

$m=6\times 10\times 15=900$, $M_1=\frac{900}{6} =150$ , $M_2=\frac{900}{10} =90$ , $M_3=\frac{900}{15} =60$

i am trying to find inverse but $150x_1 \equiv 1\pmod 6$ and others have no inverse.

  • 2
    $\begingroup$ The problem is that $6,10,15$ are not pairwise relative primes, which is required in order to use CRT. $\endgroup$
    – M.P
    Commented Oct 2, 2019 at 17:57
  • 1
    $\begingroup$ The Chinese remainder theorem applies when the moduli are relatively prime, and these are not, so you need to do a little more analysis. $\endgroup$
    – saulspatz
    Commented Oct 2, 2019 at 18:00

1 Answer 1


Since these moduli aren't pairwise relatively prime, we need to double-check to be certain there is a solution.

$x\equiv5\pmod 6$ leads to $x\equiv 1\pmod2$ and $x\equiv 2\pmod3$.
$x\equiv3\pmod {10}$ leads to $x\equiv 1\pmod2$ and $x\equiv 3\pmod5$.
$x\equiv8\pmod {15}$ leads to $x\equiv 2\pmod3$ and $x\equiv 3\pmod5$.

Since these are all compatible, there is a solution, which is also the solution to $x\equiv 1\pmod2$ and $x\equiv 2\pmod3$ and $x\equiv 3\pmod5$. You should have better luck solving that system since the moduli are pairwise relatively prime.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .