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. 

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".
