# Show that if $a, b$ are positive integers and $d=hcf(a,b)$, then there are positive integers $s,t$ such that $d=sa-tb$

Note: "hfc" stands for "highest common factor" and is synonymous with "greatest common divisor"

Show that if $a, b$ are positive integers and $d=hcf(a,b)$, then there are positive integers $s,t$ such that $d=sa-tb$.

This is a problem assigned in my undergrad foundations class. I am unsure of how to proceed. How do I assume that $a,b$ are positive integers in the sense of a proof? Am I using the fact that $d|sa$ or $d|tb$.

• This is a consequence of Bezout's lemma, have you heard of it? – user160738 Mar 12 '17 at 20:28
• I just looked it up. Would the case for subtraction work in a similar way as addition? – Lanous Mar 12 '17 at 20:32
• Well, Bezout says there are integer $x,y$ so that $ax+by=d$. What you are trying to prove is that $x$ can be made positive and $y$ negative. – Thomas Andrews Mar 12 '17 at 20:33
• It's starting to make a little more sense now, thanks – Lanous Mar 12 '17 at 20:35
• @StellaBiderman "HCF" is "GCD" - it stands for "highest common factor" rather than "greatest common divisor." – Thomas Andrews Mar 12 '17 at 20:39

Theorem (Bezut's Lemma): Let $a,b\in\mathbb{Z}$ such that $gcd(a,b)=d$. Then there exists $x,y\in\mathbb{Z}$ such that $ax+by=d$.
In your problem, we want all of these integers to be positive. Notice that $d\leq\min(a,b)$, so $d\leq |ax|,d\leq |by|$ and if $xy\neq 0$ at least one of $ax,by$ are negative. However, if both were the sum would be too, so exactly one is negative. WLOG let it be $by$ that is negative. We know that both $a$ and $b$ are positive by hypothesis, so $x$ is positive and $y$ is negative. Thus we can write $x=s$ and $y=-t$ for $s,t\in\mathbb{N}$. Thus $d=as-bt$.
Now for when $xy=0$. WLOG let $y=0$. In this case we get $d=ax$, so $d$ is a multiple of $a$. But $d$ is a divisor of $a$, so $d=a$. Thus $d=1a-0b$.