2

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

Shyvert
  • 177

2 Answers2

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!

swolo
  • 342
  • 1
    I have never used it in this way. Does it have any sort of conditions to consider? – Shyvert Apr 11 '20 at 17:48
  • 1
    Not particularly. As long as the congruences are true, which you can check after solving, this can be used for any number of equivalence statements, not just 2 in this example. If this answered your question don't forget to approve the answer so it doesn't stay unanswered! – swolo Apr 11 '20 at 17:53
  • 1
    @Shyvert Beware that while the stated answer is correct, the derivation is not. The correct solution of $, 8k\equiv 16\pmod{28}$ is $,k = 2\pmod{\color{#c00}7},,$ which back-substituted yields the claimed result. – Bill Dubuque Apr 11 '20 at 18:36
0

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

Parcly Taxel
  • 103,344