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?

  • 1
    $\begingroup$ 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). $\endgroup$
    – lulu
    Dec 26 '17 at 13:32

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


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.