1
$\begingroup$

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?

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

2 Answers 2

4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ How do you prove the last inequality? $a+b > gcd(a,b)$, i.e. the strictly less than? $\endgroup$ Commented Sep 17, 2014 at 6:35
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Sep 17, 2014 at 6:42
  • $\begingroup$ Andre, you mind providing the link where you provide the proof for your remark? Not sure what/how to search for it... $\endgroup$ Commented Sep 17, 2014 at 15:54
  • $\begingroup$ @Pinocchio: I am adding the limk to the answer. $\endgroup$ Commented Sep 17, 2014 at 17:42
3
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .