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

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

• Do you mean CRT (the Chinese Remainder Theorem)? – Théophile Jan 16 at 14:50
• @Théophile Yes indeed, I edited the title of the question. – Igor Jan 16 at 14:52
• $12 = nm, n=3,m=4,gcd(n,m)=1$ so $x \equiv 5 \bmod nm$ iff $x \equiv 5 \bmod n,x \equiv 5 \bmod m$. In the opposite direction when you have $x \equiv a \bmod n,x \equiv b \bmod m$ the goal is to find $c = un+vm$ such that it becomes $x \equiv c \bmod nm$ – reuns Jan 16 at 14:57
• Rewrite your system as $x\equiv 1\pmod 8$ and $x\equiv 2\pmod 3$. – lulu Jan 16 at 15:11
• Um.... you haven't actually stated what the question is you are trying to answer? I assume it is what is the smallest such value of $x$ or what is $x \pmod {24}$. But you haven't said it. – fleablood Jan 16 at 16:24

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.

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

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

• This transformation happens quite naturally if we use the mod Distributive Law - see my answer. – Bill Dubuque Jan 16 at 23:17

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

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.