Chinese remainder theorem dictates that there is a unique solution if the congruence have coprime modulus.
However, what if they are not coprime, and you can't simplify further?
E.g. If I have to solve the following 5 congruence equations
$x=1 \pmod 2$
$x=1 \pmod 3$
$x=1 \pmod 4$
$x=1 \pmod 5$
$x=1\pmod 6$
as gcd (2,3,4,5,6) is not coprime, how would you do it. I have heard that you can't use the lcm of the numbers, but how does it work?
Sorry for the relatively trivial question and thank you in advance.
Best Answer
$\newcommand{\lcm}{\mathrm{lcm}}$The general method is the following. Suppose you have a system of two congruences $$\tag{two} \begin{cases} x \equiv a \pmod{m}\\ x \equiv b \pmod{n}\\ \end{cases} $$ This is soluble iff $\gcd(m, n) \mid a - b$. If this is the case, first find, using Euclid's algorithm, $u, v$ such that $$ m u + n v = \gcd(m, n). $$ Multiply by $$ \lambda = \frac{a - b}{\gcd(m, n)} $$ to get $$ m (u \lambda) + n (\lambda v) = a - b, $$ and now a solution is $$ x = a - m (u \lambda) = b + n (\lambda v) = \sigma, $$ and all solutions are the numbers $$\tag{one} x \equiv \sigma \pmod{\lcm(m, n)} $$ If you have more than two equations, use this method on the first two to reduce (two) to (one), so you have an equation less. Repeat.