2
$\begingroup$

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.

$\endgroup$
2
  • 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

4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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