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?

Don't do that with such computations! For each of these congruence equations, you just have to find the modular inverse of the coefficient (which happens to be a modular unit since it is coprime to the modulus).
Example for the first congruence:
The modular inverse of $4\bmod 15$ is none other than itself since $4^2=16\equiv 1\mod 15$. So multiply both sides of the congruence equation by $4$:
$$4x\equiv 7\mod 15\implies 4^2x\equiv \color{red}x\equiv 4\cdot 7=28\color{red}{\equiv 13\mod 15}.$$
