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


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

  • $\begingroup$ Do you mean CRT (the Chinese Remainder Theorem)? $\endgroup$ – Théophile Jan 16 at 14:50
  • $\begingroup$ @Théophile Yes indeed, I edited the title of the question. $\endgroup$ – Igor Jan 16 at 14:52
  • 1
    $\begingroup$ $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$ $\endgroup$ – reuns Jan 16 at 14:57
  • $\begingroup$ Rewrite your system as $x\equiv 1\pmod 8$ and $x\equiv 2\pmod 3$. $\endgroup$ – lulu Jan 16 at 15:11
  • $\begingroup$ 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. $\endgroup$ – 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}$$

  • $\begingroup$ This transformation happens quite naturally if we use the mod Distributive Law - see my answer. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.