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)?

 

[CellCoree]

Hello,

Thank you for reaching out for assistance in proving Bezout's Lemma. It seems like you have already made significant progress in your proof by utilizing the well-ordering principle and Euclid's Algorithm. To prove that sa + tb divides gcd (a, b), you can use the fact that gcd (a, b) is the largest common divisor of a and b. This means that any other common divisor, such as sa + tb, must also divide gcd (a, b). You can use this logic to show that sa + tb divides gcd (a, b) by considering the prime factorization of gcd (a, b) and showing that all its prime factors are also present in sa + tb.

I hope this helps you in completing your proof. Good luck!