0

I was reading the proof related to GCD from the Khan Academy website I understand the algebra but I cannot understand the reasoning of the following sentence.

Let $C=A-B.$ Then $\gcd(A,B)$ must be less than or equal to, $\gcd(B,C),$ because $\gcd(B,C)$ is the “greatest” common divisor of $B$ and $C.$

How is the $\gcd(A, B)$ less than the $\gcd(B, C)?$ I can understand it could be equal to due to the $B$ being common in both, but I cant understand why it would be less. Could someone please explain?

Mark
  • 649
Har
  • 155
  • 1
    They do have to be equal, but of course the statement is then true (the fact that a stronger statement is also true doesn't invalidate the given statement). – lulu Dec 26 '17 at 13:32

1 Answers1

1

Let $c=\gcd(A,B)$ and $d=\gcd(B,A-B).$ So, $$c\mid A,B \implies c \mid A-B.$$ Thus, $c \mid B,A-B.$ Hence, $c \leq d.$

Also, $$d\mid B,A-B \implies d\mid A.$$ Thus, $d \mid A,B.$ Hence, $d\leq c.$

So, indeed $c=d.$ (but that also means that $c\leq d$.)

Sahiba Arora
  • 10,847