Find all $x\in \mathbb{Z}$ with $x \equiv 2 \mod 4$ , $x \equiv 8\mod9$ and $x \equiv 1\mod5$

Question

Find all $x\in \mathbb{Z}$ with $x \equiv 2 \mod 4$ , $x \equiv 8\mod9$ and $x \equiv 1\mod5$

My attempt:

$\gcd\left(9,5,4\right) = 1 = 9r+5s+4\times0$

$9 = 1\times5+4$

$5 = 1\times4+1$

so $1 = 5-(9-5) = 2\times5 - 1\times9$

thus $r=-1$ and $s = 2$

so $x = 2\times5\times8 -1\times9\times1=80 - 9=71\mod 180$

But the problem is that $71\equiv8\mod9$ and $71\equiv1\mod5$, but $71 \ne 2 \mod 4$. What is wrong?

Answer 1

I am using the method for solving this system of equations as outlined here.

---

Here, we have $a_1 = 2, a_2 = 8, a_3 = 1$. Additionally, $n_1 = 4, n_2 = 9, n_3 = 5$. Now, $N = n_1 \cdot n_2 \cdot n_3 = 180$.

Hence, $y_1 = 45, y_2 = 20, y_3 = 36$. Now, we are supposed to find the values of $z_i$ for $i = 1, 2, 3$. I'll outline the method for finding $z_1$, and the others follow similarly.

Now, $z_1 \equiv 45^{-1} \mod 4$. Now, what is the value of $45^{-1}$? It is that value of $x \in \mathrm{Z_4}$ such that $$45x \equiv 1 \mod 4$$ We can easily see that $x = 1$. So, we get: $z_1 \equiv 1 \mod 4$, which gives $z_1 = 1$.

---

Can you take it from here?

Answer 2

CRT does not work with the Bezout coefficients of the entire system : it works with two at a time, but not all three. That's why the $x$ you get solves the first two congruences, but not the third one : because you actually did the procedure correct for the latter two moduli, but the third one was incorporated with the coefficient $0$, which is incorrect.

What you should have done is this : solve the last two together by noting that $1 = 9r+5s$ with $s = 2$ and $r = -1$, so then you get $8 \times 5 \times 2 + 9 \times -1 \times 1= 71$, but only modulo $\mathbf{45}$, not the whole $180$. This reduces to $26$ modulo $45$.

Now, you solve $26 \pmod{45}$ and $2 \pmod{4}$ together, by noting that $4r + 45s = 1$ where $s =1$ and $r = -11$, so we get $4 \times -11 \times 26 + 45 \times 1 \times 2 = -1054$ mod $180$, which then gives $26 \mod 180$ (which one could have observed from the equations themselves, but I did the solving just to make sure).

Now, it turns out that you can do all the coefficients at once : but for this, you still need three separate Bezout coefficient solutions but wwith different moduli. See here for details.

Answer 3

The smallest positive integer to satisfy all your conditions is $26$ thus the set of your solutions are integers of form $$180k+26$$ for $$k=0, \pm1, \pm 2,....$$

Answer 4

Here's an elementary way to do it: Since $x\equiv 2\mod 4$ then $x$ is even. Since $x\equiv 1\mod 5$ then the decimal expansion of $x$ has $1$ or $6$ in the units. But $x$ is even, so it must be $6$.

So $x=10k+6$ for some $k$. But also, $x\equiv 8\mod 9$, so the sum of the algarisms of $x$ is of the form $9p+8$. But since $x=10k+6$, the sum of the algarisms of $x$ is $k+6$, i.e. $$9p+8=k+6$$ so $k=9p+2$. Substituting, we have $x=10(9p+2)+6=90p+26$ for some $p$.

But now we use again that $x\equiv 2\mod 4$, which means that the remainder of the division of $x=90p+26$ by $4$ is $2$. From this, $90p$ should be divisible by $4$, so $p$ is even, say $p=2q$.

Therefore, $x=180q+26$, for some $q=0,1,2,\ldots$. Conversely, you can check that any number of this form satisfies all desired congruences.

Answer 5

From $x\equiv2\mod4$, let $x=4a+2$ that $a$ is an integer. Then sub it into the second equation,$$4a+2\equiv8\mod9\\4a\equiv6\mod9\\2a\equiv3\mod9\\2a\equiv12\mod9\\a\equiv6\mod9$$ After that, we do the same thing: let $a=9b+6$ that $b$ is an integer, $x=4\left(9b+6\right)+2=36b+26$. Then sub it into the third equation, $$36b+26\equiv1\mod5\\36b\equiv0\mod5\\b\equiv0\mod5$$ Then, let $b=5k$ that $k$ is an integer. $x=36\left(5k\right)+26=180k+26$, and that is the answer.

Conclusion: The answer is $180k+26$ for $k\in\mathbb{Z}$.

Answer 6

Hint $\ \overbrace{x = \color{#0a0}{-1\!+\!9}(a\!+\!5(b\!+\!4c))}^{\text{by iterated division}}\,$ so $\overbrace{\color{#90f}{\bmod 5}\Rightarrow a\equiv 3}^{\large\color{#90f}{x\ \equiv\ 1}};\ $ $\overbrace{\color{#c00}{\bmod 4}\Rightarrow b\equiv 0}^{\large\color{#c00}{x\ \equiv\ 2}},\,$ so $\ \bbox[5px,border:1px solid #c00]{x= 26\!+\!180c}$

Remark $ $ What went wrong in your method is you didn't correctly apply the CRT formula (or you incorrectly tried to generalize the formula for two congruences). Applying the linked formula yields

$\!\begin{align} x\,&\equiv\, \color{#c00}{2\pmod{4}}\ \ \ \ {\rm and}\, \ \ \ x\equiv \color{#0a0}{-1\pmod{9}}\ \ \ \ \ {\rm and}\,\ \ \ \ \ x\equiv \color{#90f}{1\pmod{5}}\\[.5em] \iff x\ &\equiv\, \color{#c00}2(9\cdot 5)\overbrace{((9\cdot 5)^{-1}\!\color{#c00}{\bmod 4)}}^{\large\! 1/45\ \equiv\ \color{#c00}{1/1}\ } \color{#0a0}{-1} (4\cdot 5)\overbrace{((4\cdot 5)^{-1}\!\color{#0a0}{\bmod 9)}}^{\large 1/20\ \equiv\ 10/2\ \equiv\ \color{#0a0}{5/1}} + \color{#90f}1(4\cdot 9)\overbrace{((4\cdot 9)^{-1}\!\color{#90f}{\bmod 5)}}^{\large\! 1/36\ \equiv\ \color{#90f}{1/1}}\\[.5em] &\equiv\, \color{#c00}2(9\cdot 5)\,(\color{#c00}{1/1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \color{#0a0}{-1} (4\cdot 5)\,(\color{#0a0}{5/1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \:\! + \color{#90f}1(4\cdot 9)\,(\color{#90f}{1/1})\\[.5em] &\equiv\ \color{#c00}{90}\ \ - \ \ \color{#0a0}{100}\ \ +\ \ \color{#90f}{36}\ \bbox[5px,border:1px solid #c00]{\equiv\, 26\pmod{\!180}} \end{align}$

See this answer for an intuitive explanation of the genesis of the above CRT formula (which will help you to correctly remember it and efficiently apply it).