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. 
 A: \begin{align}
d & = mx + ny \\[8pt]
& = m(x+kn) + n(y- km)
\end{align}
Choose $k$ so as to make $x+kn$ negative. Then  let $x+kn, y-km$ be the new $x,y.$
A: 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$.
A: Conceptually it is clearer arithmetically, where it boils down to: a solvable linear congruence $\!\bmod n$  has a negative solution (stronger: it has a solution in any $\,n\,$ consecutive integers).
Note that this linear diophantine equation is equivalent to a linear congruence, viz,
$$\exists\, x,y\!:\ mx+ny = d\iff \exists\, x\!:\ m\:\!x \equiv d\!\!\!\pmod{\!n}\qquad$$
But if $\,x_0\,$ is a root of the congruence then so too is every $\,x\equiv x_0\pmod{\!n}\,$
because $\ x\equiv x_0\ \,\smash{\overset{\rm\color{#c00}{PR}}\Longrightarrow}\ \, mx\equiv mx_0\equiv d,\ $ by $\,\rm\color{#c00}{PR} =$ Congruence Product Rule.
Every interval of $\,n\,$ consecutive integers is a complete system of residues$\bmod n,\,$ so it contains a solution $\,x\equiv x_0\pmod{\!n}.\,$ In particular there is a negative solution (e.g. in  $\,-n\le x\le -1).$
The argument generalizes to higher degree polynomials: if $\,x_0\,$ is a root of a polynomial $\,f(x)\,$ with integer coef's then the Polynomial Congruence Rule yields  $\,x\equiv x_0\Rightarrow P(x)\equiv P(x_0)\equiv 0,\,$ hence if $\,P\,$ has root $\!\bmod n\,$ then it has a root in every complete residue system.
The degree $1$ case is even more arithmetically conceptual using fractional language, namely

*

*existing modular fractions $\,x\equiv d/m\pmod{\!n}\,$ have reps in every complete residue system - just as does any integer

Beware $ $ This "fraction" is multi-valued if $\, c:=\gcd(m,n) > 1\,$ (and nonexistent if $\,c\nmid d),\,$ see here for further discussion of such general modular "fractions".
