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$.
Answer
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$.
No comments:
Post a Comment