What to do if the modulus is not coprime in the Chinese remainder theorem? 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.
 A: Break into coprime modulo-s
$$x\equiv1\pmod6\implies x\equiv1\pmod2, x\equiv1\pmod3\ \ \ \ (1)$$
$$x\equiv1\pmod2,x\equiv1\pmod4\implies x\equiv1\pmod4\ \ \ \ (2)$$
$$x\equiv1\pmod5\ \ \ \ (3)$$
Now apply CRT on $1,2,3$
But as all the residues are same, we don't need CRT.
We only need $x-1$ to be divisible by lcm$(2,3,4,5,6)$
A: \begin{align}
  x &\equiv 1 \pmod 2 \\
  x &\equiv 1 \pmod 3 \\
  x &\equiv 1 \pmod 4 \\
  x &\equiv 1 \pmod 5 \\
  x &\equiv 1 \pmod 6 \\
\end{align}
Note that 
$x \equiv 1 \pmod 6 \implies 
\left\{
\begin{array}{l}
    x\equiv 1 \pmod 2 \\
    x \equiv 1 \pmod 3
\end{array}
\right.$
Replace $x \equiv 1 \pmod 6$ in your original list with those two equivalences and sort the list by prime number bases:
\begin{align}
  x &\equiv 1 \pmod 2 \\
  x &\equiv 1 \pmod 2 \\ 
  x &\equiv 1 \pmod 4 \\\hline
  x &\equiv 1 \pmod 3 \\
  x &\equiv 1 \pmod 3 \\ \hline
  x &\equiv 1 \pmod 5 \\
\end{align}
Note first that $x \equiv 1 \pmod 4 \implies x \equiv 1 \pmod 2$. This means that the equivalence $x \equiv 1 \pmod 2$ is included in the equivalence $x \equiv 1 \pmod 4$ and is therefore superfluous - it can be removed.
So we can simplifiy the list to
\begin{align}
  x &\equiv 1 \pmod 4 \\
  x &\equiv 1 \pmod 3 \\
  x &\equiv 1 \pmod 5 \\
\end{align}
The solution is $x \equiv 1 \pmod{30}$.
A: $\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.
A: We need to eliminate the pairs that are not coprime to ensure we don't get a contradiction (otherwise no such solution can exist).
To check this, we must ensure that if $x \equiv a \mod{m}$ and $x \equiv b \mod{n}$, then $a \equiv b \mod{\gcd(m,n)}$.
This means that asking that $x \equiv 1 \mod{2}$ and $x \equiv 1 \mod{4}$ is fine since $1 \equiv 1 \mod{2}$, whereas if we required $x \equiv 2 \mod{4}$ instead, then this is not true meaning no such solution can exist.
If these conditions are all compatible then we can get a solution modulo the lowest common multiple of all these numbers.
To do this, note that by Chinese Remainder Theorem (CRT), if $x \equiv a \mod{mn}$, where $\gcd(m,n)=1$, then this is equivalent to requiring that $x \equiv a \mod{m}$ and $x \equiv a \mod{n}$.
Repeating this, we can assume $m$, $n$ are prime powers. If we haven't checked compatibility yet, we can do at this point as it will be quite straightforward. Assuming they are, if we have a congruence condition modulo $p^m$, we can eliminate any other congruence condition modulo $p^n$ for any $n<m$.
Now all our moduli will be coprime and we can now apply CRT again to get a solution (although we may have more equations than we started with).
In your example, splitting each congruence into prime powers we have:
\begin{eqnarray}
&x& \equiv 1 \mod{2}, \\
&x& \equiv 1 \mod{3}, \\
&x& \equiv 1 \mod{4}, \\
&x& \equiv 1 \mod{5}, \\
&x& \equiv 1 \mod{2} \mbox{ and } x \equiv 1 \mod{3}.
\end{eqnarray}
Now we may remove the last line since these conditions already appear. The only other check we need to make is the congruences for $2$ and $4$. Now these are compatible so we remove the first condition. This leaves us with the conditions
\begin{eqnarray}
&x& \equiv 1 \mod{3}, \\
&x& \equiv 1 \mod{4}, \\
&x& \equiv 1 \mod{5}. \\
\end{eqnarray}
Now all the moduli are coprime so by CRT we find the solution is $x \equiv 1 \mod{60}$.
