I know that the GCD(a,b) can be written as a linear combination of a,b (ma + nb = GCD(ab)). How can I select which coefficient (m or n) is positive?
In other words, for example, if after executing extended euclidean division, I obtain the coefficient for b to be negative, how do I manipulate the linear combination so that the coefficient for b is no positive?
Let $g$ be the GCD of $a$ and $b$ and suppose we found the coefficients $m$ and $n$ such that,
$$ am+bn = g,$$
we want to find another set of coefficients $\alpha$ and $\beta$ which still satsify the above equation. Let $\beta = n+\delta$ and $\alpha = m - \eta$ then we can write,
$$ g = am+bn = a(m+\eta)+b(\beta-\delta) = a\alpha + b\beta + a\eta- b\delta, $$
clearly if we want to mantain the equality we must have $a\eta - b\delta = 0 $. This is equivalent to condition $a/b = \delta/\eta$.
An Example
The gcd of $9$ and $8$ is $1$ since, $9-8=1$. Using what we learned above we can change the coefficients of $8$ and $9$ by sending $$-1\rightarrow -1+9=8$$ and $$1\rightarrow 1-8=-7$$ giving us,
$$ (-7)9+(8)8 = -63+64=1.$$
Suppose $ma + nb = d$, where $d = \gcd(a,b)$. Since $ba + (-a)b = 0$, we have $(m+kb)a + (n-ka) b = d$ for any $k$. Now choose $k$ so that $n-ka$ has the sign you want.
