System of congruences when $gcd(m,n) \not= 1$

Question

I have to solve this system but I don't know what I did wrong, since the result should be: $ x \equiv19\;(mod\;56)$. $$ \begin{cases} x \equiv 3\;(mod\;8) \\ x \equiv 19\;(mod\;28) \\ \end{cases}\\ $$ $$ 3 + 8k = 19 + 28h\\ 8k-28h = 16\\ 2k−7h=4\\ $$ $$ k_0 = -5;\;h_0 = -2\\ k = -5+7t;\;h = -2+2t\\ $$ $$ x = 3+2(-5+7t)\\ x \equiv 7\;(mod\;14)\\ $$

Edit: Do I have to use this theorem?$$ \begin{cases} x \equiv a\;(mod\;p) \\ x \equiv b\;(mod\;p^k) \\ \end{cases}\; ⇒x \equiv b\;(mod\;p^k) $$ $$ \begin{cases} x \equiv 3\;(mod\;2^3) \\ x \equiv 19\;(mod\;7*2^2) \\ \end{cases}\\ $$ $$ \begin{cases} x \equiv 3\;(mod\;8) \\ x \equiv 19\;(mod\;7) \\ \end{cases}\\ $$

chinese theorem: $$ ...\\ x \equiv 131\;(mod\;56) \\ x \equiv 19\;(mod\;56) \\ $$

Answer 1

one method to use is the Chinese remainder theorem to solve these congruences.

You were on the right track in the beginning, and we can see how $ x \equiv3\;(mod\;8)$ gives us $x=3+8k$.

We can then substitute our $3+8k$ for $x$ in the second congruence to get $$ 3+8k \equiv19\;(mod\;28)$$ Solving for $k$ we find $k \equiv 2\;(mod\;28)$, so $k=2+28h$.

If we substitute this $k$ back into our first equation for $x$, we get $$x=3+8(2+28h)$$ $$\implies x=3+16+56h$$ $$\implies x=19+56h$$ This ultimately gives us $x \equiv 19\;(mod\;56)$, the desired result.

I hope this helps!

Answer 2

$7\bmod14$ is not $3\bmod8$. You need to remove a factor of $4$ from the $\bmod28$ congruence to get a system of relatively prime moduli: $$x\equiv5\bmod7$$ Then use the Chinese remainder theorem to get the correct result.