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

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?

• Think about solving the equation $ax + by = 0$.
– user14972
Commented Sep 17, 2014 at 17:50

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

• How do you prove the last inequality? $a+b > gcd(a,b)$, i.e. the strictly less than? Commented Sep 17, 2014 at 6:35
• We have $\gcd(a,b)\le \min(a,b)$. For any common divisor of $a$ and $b$ must divide the smaller one, so can be no bigger than the smaller one. Commented Sep 17, 2014 at 6:42
• Andre, you mind providing the link where you provide the proof for your remark? Not sure what/how to search for it... Commented Sep 17, 2014 at 15:54
• @Pinocchio: I am adding the limk to the answer. Commented Sep 17, 2014 at 17:42

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.

• Sorry if this is obvious, but what is g? does the equation still work if g=1? Commented Sep 17, 2014 at 15:59
• $g$ is $\gcd(a,b)$. Yes it works if $g=1$. Commented Sep 17, 2014 at 20:07