elementary number theory - Solve the following system of simultaneous congruences:

$$\begin{gather} 3x\equiv1 \pmod 7 \tag 1\\ 2x\equiv10 \pmod {16} \tag 2\\ 5x\equiv1 \pmod {18} \tag 3 \end{gather}$$

Hi everyone, just a little bit stuck on this one. I think I am close, but I must be getting tripped up somewhere. Here is what I have so far:

from (2), $2x=10+16k \implies x=5+8k$

Putting this into (1):

$$\begin{align*} 3(5+8k) \equiv 1 \pmod 7 &= 15+24k \equiv 1 \pmod 7 \\ &= 24k \equiv -14 \pmod 7 \end{align*}$$

By co-prime cancellation, I get $12k\equiv -7 \pmod 7$

And since $12k \equiv 5k \pmod 7 \implies 5k \equiv -2k \pmod 7$ and $-7 \equiv 0 \pmod 7$, we conclude that
$-2k \equiv 0 \pmod 7 \implies -2k = 7l$ for some integer $l$.

Multiplying by $-4 \implies 8k = -28l$

It follows that, $x = 5 + 8k = 5-28l \implies x \equiv 5 (mod \space -28)$

So now, solving (1), (2) and (3) is equivalent to solving:

$x \equiv 5 (mod \space -28)$ (4)

$5x\equiv1 (mod\space 18)$ (3)

Then substitute $x = 5-28l$ into (3),

$5(5-28l) \equiv 1 (mod \space 18)$

= $25 - 140l \equiv 1 (mod \space 18)$

= $140l \equiv 24 (mod \space 18)$

And since $140l \equiv 14l (mod \space 18) \implies 14l \equiv -4l (mod \space 18)$ and $24 \equiv 6 (mod \space 18)$

we have, $-4l \equiv 6 (mod \space 18) \implies -4l = 6 + 18M$ for some integer M.

Multiplying by 7 $\implies -28l = 42 + 126M$

Finally, substituting this back into x, $x = 5-28l \implies x = 5+42+126M = 47+126M \implies x \equiv 47 (mod \space 126)$

But when I substitute $x = 47$ back into my original equations, it works for (1) and (3), but fails for (2).

Can anyone tell me where I went wrong? Many thanks!!

Answer

This is not an answer, but a guide to a simplification. The first congruence is fine. Note that the second congruence is equivalent to $x\equiv 5\pmod{8}$. Any solution of this congruence must be odd.

Now look at the third congruence. Note that as long as we know that $x$ is odd, we automatically have $5x\equiv 1\pmod{2}$. So in the presence of the second congruence, the third one can be replaced by $5x\equiv 1\pmod{9}$.

Thus we are looking at the congruences $3x\equiv 1 \pmod{7}$, $x\equiv 5\pmod{8}$, and $5x\equiv 1\pmod{9}$. Now the moduli are pairwise relatively prime. Relatively prime moduli are easier to handle, there is less risk of error.

There will be a unique solution modulo $(7)(8)(9)$. In particular, your final modulus of $126$ cannot be right.

It is probably worthwhile to simplify the congruences still further. Note that the congruence $3x\equiv 1\pmod{7}$ has the solution $x\equiv 5\pmod{7}$. And the congruence $5x\equiv 1\pmod{9}$ is equivalent to $x\equiv 2\pmod{9}$.

We got lucky, ended up with $x\equiv 5\pmod{7}$ and $x\equiv 5\pmod{8}$, which has as only solution $x\equiv 5\pmod{56}$.

So we are trying to solve $x\equiv 5\pmod{56}$, $x\equiv 2\pmod{9}$.

One can find a solution by a short search. Or else we want $x=56a+5=9b+2$. That gives $9b=56a+3$, so $3$ must divide $a$, say $a=3c$. We arrive at $56c+1=3b$. Clearly $c=1$ works, so $a=168$. The solution is therefore $x\equiv 173\pmod{(56)(9)}$.