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!!
 A: The problem seems to be where you write "So now, solving (1), (2) and (3) is equivalent to solving..."
This isn't true. $$x \equiv 5 \;(\bmod 28)$$ is not enough - one of the implications is correct, but equivalence only holds with $$x \equiv 5 \;(\bmod 56 = 8 \cdot 7).$$ The reason for this is essentially the Chinese remainder theorem.
There is a similar problem later on. The solution of this system is actually determined modulo $lcm(7,8,18) = 504$.
A: 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)}$. 
