let $d = \gcd(m,n), m, n > 0$ Bézout gives $d = mx + ny, x, y \in \mathbb{Z}$ prove that.. ... prove that it is always possible to choose $x < 0$. 
I did $m = qn + r$ and $\gcd(m,n) = \gcd(n, \operatorname{rem}(m, n)) = \gcd(n, r)$
But I do not know where to go from here. 

If we suppose $x, y$ are given and $x>0$, we know the other solutions in integers of the equation  $\;mX+nY=d\;$ are given by
$$X=x-kn,\quad Y=y+kn\qquad( k\in \mathbf Z),$$
so choose $k$ so large as to ensure that $x'=x-kn<0$.
