Solving $x \equiv 9 \pmod{11}, x \equiv 6 \pmod{13}, x \equiv 6 \pmod{12}, x \equiv 9 \pmod{15}$

Question

$$x \equiv 9 \pmod{11}$$ $$x \equiv 6 \pmod{13}$$ $$x \equiv 6 \pmod{12}$$ $$x \equiv 9 \pmod{15}$$

Does this system have a solution? I want to solve this using the Chinese remainder theorem, but there's $\gcd (12,15)=3$. How can I deal with this?

Answer 1

2814 is a solution. You can find more (next is > 10000) by exhaustion.

GCD(12,15)=3 holds because 9 and 6 are equal under mod 3.

Answer 2

A good method to deal with systems of congruence equations with non coprime modulos by hand is splitting them up according to their prime factorization.

A general approach:

1. For each congruence, where the modulus is not a prime power, split the equation into several congruence equations with prime power modulus, e.g.: $$x \equiv 6 \pmod{12} \Leftrightarrow \begin{cases}x \equiv 0 \pmod{3} \\ x \equiv 2 \pmod{2^2}\end{cases} $$
2. Group the equations according to the base prime of the modulus.
3. Whenever you have more than one equation for a prime, choose only the/an equation with the highest prime power.

4. Then, compare the other equations to the choosen one. They either contradict the first one or are redundant (they are implied by the first one). Examine them one by one and either cut them off or conclude that there are no solutions.

   Example: $$x\equiv 1\pmod{2} \tag{1}$$ $$x\equiv 3\pmod{8} \tag{2}$$ $$x\equiv 3\pmod{8} \tag{3}$$ $$x\equiv 1\pmod{4} \tag{4}$$ Choose equation (2). (2) obviously implies (1). So, we can ignore (1). Same for (3). (4) however contradicts (1), so there are no solutions to this system. If we instead had $x\equiv 3\pmod{4}$ in (4), then this would be a redundancy, too, and the whole system would simplify to $x\equiv 3\pmod{8}$.

---

In your case: $$\begin{align*}x \equiv 9 \pmod{11} &\Leftrightarrow x \equiv 9 \pmod{11}\\ x \equiv 6 \pmod{13} &\Leftrightarrow x \equiv 6 \pmod{13} \\ x \equiv 6 \pmod{12} &\Leftrightarrow \begin{cases}x \equiv 0 \pmod{3} \\ x \equiv 2 \pmod{4}\end{cases} \\ x \equiv 9 \pmod{15} &\Leftrightarrow \begin{cases} x \equiv 0 \pmod{3} \\ x \equiv 4 \pmod{5}\end{cases} \end{align*}$$

Only $3$ occurs twice, and the equations are obviously identical. So you are left with five equations with pairwise coprime modulos and you can apply CRT.