# 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.

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 moduluses 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 moduluses are coprime so by CRT we find the solution is $x \equiv 1 \mod{60}$.

$\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.

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)$

\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}$.