MHB How Do You Prove That sa + tb Divides gcd(a, b) in Bezout's Lemma?

[nicodemus1]

Good Day,

I have to prove Bezout's Lemma.

I have proven that since gcd (a, b) divides a and gcd (a, b) divides b, gcd (a, b) divides sa + tb.

I've made use of the well-ordering principle and Euclid's Algorithm to show that sa + tb divides a and sa + tb divides b.

What I can't prove is that sa + tb divides gcd (a, b).

Please help me here.

Thank you.

 

[Deveno]

Good Day,

I have to prove Bezout's Lemma.

I have proven that since gcd (a, b) divides a and gcd (a, b) divides b, gcd (a, b) divides sa + tb.

I've made use of the well-ordering principle and Euclid's Algorithm to show that sa + tb divides a and sa + tb divides b.

What I can't prove is that sa + tb divides gcd (a, b).

Please help me here.

Thank you.

since d = gcd(a,b) is the largest positive integer that divides both a and b,

and d divides sa + tb, d ≤ sa + tb, whence sa + tb = d, since sa + tb divides both a and b.

 

[nicodemus1]

Good Day,

Thank you for your reply.

However, I still don't get why sa + tb divides gcd(a, b).

Thanks & Regards,
Nicodemus

 

[Deveno]

the "g" in gcd stands for "greatest". the "cd" stands for "common divisor".

since sa + tb is a common divisor of a and b, it cannot be "greater than" the greatest common divisor of a and b, can it?

EVERY number divides it self.

specifically, the DEFINTION of gcd(a,b) is:

d: d|a and d|b and (for all c: if c|a and c|b then c|d).

we have shown that c = sa + tb divides both a and b. therefore c|d.

do you have a different definition of gcd(a,b)?