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?
Best Answer
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 $$