# Solving a congruence system when the Chinese remainder theorem cannot be applied

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?

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

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

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

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