Find all solutions, if any, to the system of congruences x ≡ 5(mod 6), x ≡ 3(mod 10), and x ≡ 8 (mod 15)

chinese remainder theoremdiscrete mathematics

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.

Best Answer

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.