Having problem to find all solutions using the Chinese Remainder Theorem

Question

Find all solutions using the Chinese Remainder Theorem.

x = 2 (mod 4)
x = 3 (mod 5)
x = 9 (mod 13)

My step is here:

a = 2 (mod 4) , a = 0 (mod 5) , a = 0 (mod 13)
b = 0 (mod 4) , b = 3 (mod 5) , b = 0 (mod 13)
c = 0 (mod 4) , c = 0 (mod 5) , c = 9 (mod 13)

The general solution for x is given by x = a + b + c + k*lcm(4,5,13) = a+b+c+260k

since a = 0 (mod 5) and a = 0 (mod 13), so a = 65m for some integer m then 65m = 2 (mod 4)

What should i do next? I think the step i write 65m - 2 = 4 is wrong

Answer 1

We have ,

$$x\equiv2 \mod 4 \implies \color{#d05}{x=4a+2}\\ $$
$$\begin{align}x&\equiv3 \mod 5 \\4a+2&\equiv3\mod5\\ 4a&\equiv 1\mod5 \\ a &\equiv 4 \mod 5\implies\color{#2cd}{a = 5b+4}\end{align} $$
$$\begin{align}x&\equiv9 \mod 13 \\ 4(5b+4)+2&\equiv 9\mod13 \\ 20b+18&\equiv9\mod13 \\ 20b&\equiv 4\mod 13 \implies \color{#2c0}{b = 13c+8}\end{align} $$

So , $x = 4a+2 = 20b+18=260c + 178$

Answer 2

Following @lulu's suggestion, but using Bezout coefficients, we first get for $\begin{cases} x\cong2\pmod4\\x\cong3\pmod5\end{cases}$, that $-1\cdot4+1\cdot 5=1$.

Now, by a well known result, detailed in the section "Using the existence construction" of "Computation" in this article , we get $x=(-4)\cdot 3+(5)\cdot 2=-2+20k$.

Then, repeat for $20$ and $13$. That is, take $\begin {cases} x\cong-2\pmod{20}\\x\cong 9\pmod{13}\end{cases}$.

So $2\cdot20+-3\cdot 13=1$.

And we get $x=40\cdot9+(-39)\cdot (-2)=438+260k$, or $x=178+260k$, as our solution.

Answer 3

By CCRT $\,x\equiv -2\pmod{\!4,5}\!\iff\! x\equiv \color{#0a0}{-2\pmod{\!20}}$
$\,\bmod \color{#c00}{13^{\phantom{|^|}}}\!\!\!\!:\,\ 9\equiv x\equiv \color{#0a0}{-2\!+\!20}\color{#c00}k\equiv -2\!-\!6k\!\iff\! 6k\equiv -11\equiv-24\!\iff\! \color{#c00}{k\equiv -4}$
So we conclude $\ x = -2^{\phantom{|^i}}\!\!\!\!+\!20(\color{#c00}{-4\! +\! 13}n) = -82+260n,\, $ using only trivial mental arithmetic.

---

Remark $\ $ We solved $\bmod 13\!:\ 6x\equiv 6(-4)\ $ using $$\bmod n\!:\ ax\equiv ab\iff x\equiv b,\ \ {\rm when}\ \ \gcd(a,n)=1\!$$

since by Bezout, $\,a\,$ is invertible so cancellable from LHS, i.e. scale LHS by $\,a^{-1}\,$ to cancel $\,a,\,$ using the Congruence Product Rule.

Such linear congruences are often much easier to solve using modular fractions, e.g. see my comment below, and see here, and here and here for circa $20$ motley worked examples via a handful of methods.