Solving a simultaneous system of linear congruences

26 Views Asked by At

I wish to solve the following system of congruences using the Chinese remainder theorem: $$13X \equiv 3 (\text{mod} 15), \\ 2X \equiv 6 (\text{mod} 10).$$ I have reduced this system to $$X \equiv 6 (\text{mod} 15), \\ X \equiv 3(\text{mod} 5),$$ by multiplying the first by the multiplicative inverse of $13$ and dividing the second through by $2$. However, the moduli are still not relatively prime, so I am unsure how to solve this system.