Find $4x \equiv 7 \pmod{15}$ and $3x \equiv 5 \pmod{16}$ (different exercises) This is how I solved each:
$$4x \equiv 7\pmod {15} \\
4x - 7 \equiv 0\pmod{15} \\
4x-7 = 15k \Leftrightarrow 4x-15k= 7 \\
$$ 
$$15 = 4*3+3 \\
4=3*1+1\\
3=3*1+0$$
$$1 = 4-3*1 \\
3 = 15-4*3 \\
1 = 4 - (15-4*3)*1 \\
1 = 4-15+4*3 \\
1 = 4*4-15*1 \\
$$
$$7 = (7*4)*4-(7*1)*15$$
$7*4*4 = 112$ which is congruent with 7 in mod 15. Yet my book says the answer is 13. What went wrong?
The second one:
$$3x - 5 \equiv 0 \pmod{16} \\
3x-5=16k\\
3x-16k=5 \\$$ 
$$16=3*5+1\\
3=1*3+0$$
$$1 = 16-3*5 \\
5=16*5-3*5*5$$
Yet $3*5*5-5$ is not congruent with zero in mod 16. What went wrong?

To correctly  pattern-match $\,\color{#c00}x\,$ in the above $\,\rm\color{#0a0}{scaled}\,$ Bezout equations do as follows. 
$\qquad\ \begin{align}
\ -7\cdot \color{#90f}{15}&\ +\ 4\cdot 7\cdot 4\,\  =\ \color{#0a0} 7\ \ [=\ \color{#0a0}{7\ {\rm times}} {\rm \ Bezout\ of\ } \gcd(15,4)=1\,]\\[.2em]
\Rightarrow\ \bmod \color{#90f}{15}&\!:\,\ \  \ \  4\cdot\color{#c00}{ 7\cdot 4} \ \equiv\ \ 7\\
\rm so &\,\ \ \ \ \ \ \ 4\ \cdot\  \color{#c00} x\ \ \, \equiv\, \ \ 7\ \ \ {\rm for}\ \ \ \color{#c00}{x\equiv 7\cdot 4}\equiv 13  \\[.6em]
\ 5\cdot \color{#90f}{16}&\, + 3\cdot 5(-5)\, =\, \color{#0a0}5\ \ [=\ \color{#0a0}{5\ {\rm times}} {\rm \ Bezout\ of\ } \gcd(16,3)=1\,]\\[.2em]
\Rightarrow\ \bmod \color{#90f}{16}&\!:\,\ \  3\cdot\color{#c00}{ 5(-5)}\, \equiv\ 5\\
\rm so &\,\ \ \ \ \   3\ \cdot\  \color{#c00} x\ \ \ \,\equiv\ \ \ \ 5\ \ \  {\rm for}\ \ \ \color{#c00}{x\equiv 5(-5)}\equiv 7
\end{align}$
Simpler $\bmod 15\!:\,\ 4x\equiv7\iff x \equiv \dfrac{7}{4}\equiv \dfrac{-8}4\equiv -2\equiv 13$
Similarly $\bmod 16\!:\,\ 3x\equiv 5\iff x\equiv \dfrac{5}3\equiv\dfrac{21}3\equiv 7\ $ where we subtracted or added the modulus to the numerator to make the division exact, a special case of Inverse Reciprocity.
Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.
