How to apply CRT to a congruence system with moduli not coprime?

Question

$x=1 \pmod 8$

$x=5 \pmod{12}$

8 and 12 are not coprime, I could break it to:

$x=1 \pmod 2$

$x=1 \pmod 4$

and

$x=5 \pmod 3$

$x=5 \pmod 4$

But what are the next steps to solve it? By the way, $x$ should be $17$ not sure how to get that number ...

Thanks in advance.

Answer 1

Here is a way: $$\begin{cases} x\equiv 1\pmod 8\\x\equiv 5\pmod{12} \end{cases}\iff \begin{cases} x -1\equiv 0\pmod 8\\x -1\equiv 4\pmod{12}\end{cases}\iff \begin{cases} \frac{x -1}4\equiv 0\pmod 2\\\frac{x -1}4\equiv 1\pmod{3} \end{cases}$$

Now set $y=\frac{x-1}4$. As $3-2=1$, the solutions of the last system of congruences is $$ y\equiv 0\cdot 3- 1\cdot 2 =-2\pmod{6},$$ so that, multiplying by $4$, $$x-1\equiv -8 \iff x\equiv -7\iff x\equiv 17\pmod{24}$$

Answer 2

No point in figuring it out to any lesser power of $2$ than $2^3$.

Leave it at $x\equiv 1 \pmod 8$ but $x \equiv 5 \pmod {12}$ can be reduced to $x\equiv 5 \equiv 2 \pmod 3$.

So CRT says there is a unique solution $\pmod {28}$; $x \equiv 17 \pmod{24}$.

$x = A \pmod {n_1}$ $(A = 1; n_1 = 8)$

$x = B \pmod {n_2}$ $(B = 2; n_2 = 3)$

$m_1n_1 + m_2n_2 = 1$ (in this case $8m_1 + 3m_2 = 1$ so $m_1 =2; B=-5$ or $A=-1; B=3$ or .....)

Then $x = Am_2n_2 + Bn_1n_1\pmod {n_1n_2}$.

$x = 1*(-5)*3 + 2*2*8= -15+32 = 17$.

There's utterly no point in reducing to $x \equiv 5 \pmod 4$ and $x \equiv 5\pmod 3$ as that will just get you back to $x\equiv 2,5,8,11 \pmod {12}$ and $x \equiv 1,5 \pmod 8$ which is worse than what you started with.

Answer 3

Alternatively: $$\begin{cases}x\equiv 1\pmod{8}\\ x\equiv 5\pmod{12}\end{cases} \Rightarrow \begin{cases} x=8n+1\\x=12m+5\end{cases} \Rightarrow 8n+1=12m+5 \Rightarrow \\ 2n-3m=1 \Rightarrow \begin{cases}n=2+3k\\m=1+2k\end{cases} \Rightarrow \begin{cases} x=8(2+3k)\\ x=12(1+2k)+5\end{cases} \Rightarrow \\ x=24k+17 \Rightarrow x\equiv 17\pmod{24}.$$

Answer 4

The moduli gcd is $\,d = (8,12) = 4\,$ and $\,4\mid 5-1\,$ so by CRT a solution uniquely exists mod ${\rm lcm}(8,12) $ $ = 8(12)/4 = 24,\,$ computable by $\, ab\bmod ac = a(b\bmod c) = $ $\!\bmod\!$ Distributive Law.

$8\mid x\!-\!1\Rightarrow x\!-\!1\bmod 24 = 8\left[\dfrac{\color{#c00}x\!-\!1}8\!\bmod 3\right] = 8\left[\dfrac{\color{#c00}5\!-\!1}{2 }\!\bmod 3\right]= 16\, $ by $ \begin{align}x&\equiv 5 \!\!\!\pmod{\!12}\\ \Rightarrow\,\color{#c00}x&\equiv \color{#c00}5\!\!\!\pmod{\!3}\end{align}$

---

Remark $ $ This works generally for $\,x\equiv a\pmod{\!m},\ x\equiv b\pmod{\!n}\,$ when $\,(m,n)=\color{#0a0}{d\mid b\!-\!a}$

$m\mid x\!-\!a\,\Rightarrow\,x\!-\!a\bmod mn/d = m\left[\dfrac{x-a}m\bmod n/d\right] = m\left[\dfrac{b-a}m\bmod n/d\right] $

Note $\,d\mid b\!-\!a\,\Rightarrow\, \dfrac{b-a}m = \dfrac{\color{#0a0}{(b-a)/d}}{m/d}$ and $\,m/d\,$ is invertible $\!\bmod n/d\,$ by $\,(m/d,n/d)= 1,\,$ thus the fraction exists $\bmod n/d$.

Answer 5

By CRT $\,x\equiv 5\pmod{\!12}\!\iff\! x\equiv 5\pmod{\!3}\,$ and $\,\color{#c00}{x\equiv 5\pmod{4}}$

But $\,x\equiv 1\pmod{\!8}\,\Rightarrow\,x\equiv 1\equiv 5\pmod{\!4},\,$ hence $\,\color{#c00}{x\equiv 5\pmod{4}}\,$ is redundant, thus

$$\begin{align} x&\equiv 1\!\!\pmod{8}\\ x&\equiv 5\!\!\pmod{12}\end{align}\iff \begin{array}{} x\equiv 1\ \pmod{8}\\ x\equiv 5\ \pmod{3}\end{array}\qquad$$

so we have reduced it to a an equivalent system where the moduli are coprime. See my other answer for a convenient operational CRT method to solve (both!) of those congruence systems.