0

Lemma: Suppose $m\geq{n}>0$. Then $hcf(m,n) = hcf(m-n, n).$

Proof: Suppose $d|m$ and $d|n$. So there are $a,b$ with $da=m$, $db=n$ and $a\geq{b}$. So $d(a-b)=m-n$. Thus $d|m-n$. So $hcf(m,n)\leq{hcf(m-n,n)}$. The other inequality is similar so $hcf(m,n)=hcf(m-n,n)$ $\blacksquare$.

I have no idea where the inequality $hcf(m,n)\leq{hcf(m-n,n)}$ comes from, in fact I was thinking the inequality would be the other way round since $m-n<n$. Can someone please enlighten me on this inequality?

Note: For you American folks, $hcf(m,n)$ is the same as $gcd(m,n)$.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
Nostradamus
  • 37
  • 1
  • The key idea is that $\{n,m\}$ and $\{n,m-n\}$ have the same set of common divisors $d$ so the same *greatest* common divisor - see [here](https://math.stackexchange.com/a/95825/242) in the linked dupe. – Bill Dubuque Jul 22 '22 at 17:34
  • 1
    @BillDubuque Why is r congruent to 0 in the second line of the linked dupe? – Nostradamus Jul 22 '22 at 17:40
  • If $\,\color{#c00}{b\equiv 0}\,$ then $\,0\equiv q\color{#c00}b+r\equiv q\color{#c00}0+r\equiv r,\,$ i.e. $r\equiv 0,\,$ by [Congruence Sum & Product Rules](https://math.stackexchange.com/q/879251/242). – Bill Dubuque Jul 22 '22 at 17:50
  • [Geometrically](https://math.stackexchange.com/a/1994546/242), if we rename to customary variables, then the equivalent systems of equations is $\ x\equiv 0, y\equiv 0\iff x\equiv 0,\, y+mx\equiv 0.\,$ This says the the origin $\, (x,y) \equiv (0,0)\,$ can be specified either as the intersection of the $y$ axis $(x\equiv 0)$ with the $x$ axis $(y\equiv 0)$ or, equivalently, as the intersection of the $y$ axis $(x\equiv 0)$ with the line $\, y\equiv -mx.\,$ – Bill Dubuque Jul 22 '22 at 17:50

0 Answers0