The reason you can change signs is that $-1$ is a unit (a number with a multiplicative inverse). In general, if $u$ is a unit, then we have that
$$\gcd(a,b) = \gcd(a,ub).$$
In doing the Euclidean algorithm, you are trying to compute the greatest common divisor by using the fact that for any $k$,
$$\gcd(a,b) = \gcd(a,b+ka)$$
and so, if $b = qa + r$, then
$$\gcd(a,b) = \gcd(a,b+(-q)a) = \gcd(a,r).$$
But since $\gcd(a,r) = \gcd(a,-r)$, you can then replace $r$ with $-r$ in order to compute the next division: after all, if $a=q_2r + r_2$, then $a = (-q_2)(-r)+r_2$, and what you really care about is $r_2$, not $q_2$ or $-q_2$.
(In fact, you can do better than change signs: you can multiply by any nonzero constant; so in the "next" step, you can always take the divisor to be monic if you want.)