How do you make the coefficients of the simple linear combination of the gcd positive?

Question

I was trying to convert a simple linear combination (and gcd):

$$\gcd(a,b) = ax + by$$

To have positive coefficients.

I did read the following here but didn't really understand it and was looking for a much simpler solution/answer.

In particular I had the example where:

$$1=-(-8)50 - 19(21)$$

but I wanted to make the (-8) positive and also the -19 positive. I was told to subtract 21 from 8 and add 50 to -19 but didn't really know how to do this in general or why that was right.

In particular, if the equation is of the form:

$$(-c)n + jk =1$$

but I want $c$ and $j$ to be positive, is there any processing I can do to make them both positive?

I guess what I am trying to understand more deeply, what is special about:

$$1=-(-8)50 - 19(21)$$

that is not special about other ways of expressing the gcd as a linear combination?

Assuming that I understand what is special about $1=-(-8)50 - 19(21)$, can we make a more general argument about $(-c)n + jk =1$, or even better, about:

$$(-c)n + jk =d$$

does the sign of d even matter?

Answer 1

Let $a$ and $b$ be positive integers. Then we cannot find integers $x$ and $y$, both positive, such that $\gcd(a,b)=ax+by$.

For if $x$ and $y$ are positive, then $ax+by\ge a+b\gt\gcd(a,b)$.

Remark: If the gcd of $a$ and $b$ is $1$, and $c$ is large enough (greater than $ab-a-b$) then we can find non-negative $x$ and $y$ such that $ax+by=c$. You can find proofs in various places. I wrote one recently on MSE. Similarly, whatever the gcd is, if $c$ is large enough and divisible by the gcd, then there exist non-negative $x$ and $y$ such that $ax+by=c$.

Answer 2

If $a,b$ are positive numbers (as in your example, $a=50$, $b=21$) and you want $x,y$ to be positive, this cannot work, because $$ax+by\ge a+b>a\ge\gcd(a,b)\ .$$ If one of $a,b$ is positive and the other is negative then it will work. For example, if $a=50$ and $b=-21$ then take $x=8$, $y=19$, so that $$ax+by=8\times50+19\times(-21)=1\ .$$ In general, suppose that $a$ is positive and $b$ is negative. If one solution of the equation is $x=x_0$, $y=y_0$, then the complete solution is $$x=x_0-t\frac{b}{g}\ ,\quad y=y_0+t\frac{a}{g}\ ,\quad t\in\Bbb Z\ ,$$ and even if $x_0$ or $y_0$ is negative, you can keep increasing $t$ until both $x$ and $y$ are positive.