1
$\begingroup$

I'm trying to solve the following system $$\cases{3x\equiv1\pmod{14}\\x\equiv1\pmod{8}\\3x\equiv9\pmod{5}}$$

My understanding is that, since $14, 8, 5$ aren't all coprime, I cannot apply the Chinese remainder theorem.

The first thing I did was solving the first and third equations independently, which yielded the following equivalent system:

$$\cases{x\equiv5\pmod{14}\\x\equiv1\pmod{8}\\x\equiv3\pmod{5}}$$

At this point I'm unsure how to proceed. I thought solving the system made up of the first two equation, and then a system made up of the solution to the first system with the third equation could work, but turns out it didn't. Here's what I tried:

$$\cases{x\equiv5\pmod{14}\\x\equiv1\pmod{8}\\} \iff x = 5+ 14k=1+8h \rightarrow7k-4h = -2 \iff k = 2+4y, h = 4-7y, \text{ with }y\in\mathbb{Z}$$ Therefore, $x = 33 - 56y \iff x\equiv33\pmod{56}$. Plugging this result back into the system, we now have $$\cases{x\equiv33\pmod{56}\\x\equiv3\pmod{5}\\} \iff x = 3+5k=33+56h \rightarrow5k-56h=30 \iff k = -330+56y, h = -30-5y, \text{ with }y\in\mathbb{Z}$$ Therefore, $x \equiv 1653\equiv 253 \pmod{280}$; however, this result is incorrect. What did I do wrong?

$\endgroup$
2
  • $\begingroup$ did you mean $h=4\color{red}+7y$ and $h=-30\color{red}+5y$? $\endgroup$ Apr 2 '20 at 18:55
  • $\begingroup$ there is also a formula for non-coprime moduli on wikipedia $\endgroup$
    – Nightgap
    Apr 2 '20 at 18:57
1
$\begingroup$

What did I do wrong?

At the end, you should have $x=3+5k=3+5(-330+56y)$

or $x=33+56h=33+56(-30-5y)$,

which means $x=-1647+280y$, so $x\equiv-1647\equiv33\pmod{280}$.

$\endgroup$
1
  • 1
    $\begingroup$ I think you forgot the minus sign in front of $330$ to get $1653=3+5(330)$ $\endgroup$ Apr 2 '20 at 18:38
1
$\begingroup$

I would encourage you to split up the given conditions and group according to powers of the same prime.

You have $$ 3x \equiv 1 \pmod 7 $$ $$ 3x \equiv 9 \pmod 5 $$ and related $$ 3x \equiv 1 \pmod 2 $$ $$ x \equiv 1 \pmod 8 $$

The redundant pair becomes, as $3 \equiv 1 \pmod 2,$ $$ x \equiv 1 \pmod 2 $$ $$ x \equiv 1 \pmod 8 $$ These are consistent, the highest power of the prime is $8=2^3,$ so these combine to $$ x \equiv 1 \pmod 8. $$ Then $x$ is 5 mod 7 and 3 mod 5, together $$ x \equiv 1 \pmod 8. $$ $$ x \equiv 3 \pmod 5. $$ $$ x \equiv 5 \pmod 7. $$ Now you can use CRT I get $$ x \equiv 33 \pmod {280} $$ as $$ 33 = 32 + 1 = 30 + 3 = 28 + 5 $$

$\endgroup$

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.