1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This is a consequence of Bezout's lemma, have you heard of it? $\endgroup$ – user160738 Mar 12 '17 at 20:28
  • $\begingroup$ I just looked it up. Would the case for subtraction work in a similar way as addition? $\endgroup$ – Lanous Mar 12 '17 at 20:32
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Mar 12 '17 at 20:33
  • $\begingroup$ It's starting to make a little more sense now, thanks $\endgroup$ – Lanous Mar 12 '17 at 20:35
  • 1
    $\begingroup$ @StellaBiderman "HCF" is "GCD" - it stands for "highest common factor" rather than "greatest common divisor." $\endgroup$ – Thomas Andrews Mar 12 '17 at 20:39
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.