\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!!
Best 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)}$.