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

  • Thread starter Thread starter nicodemus1
  • Start date Start date
AI Thread Summary
To prove Bezout's Lemma, it's established that gcd(a, b) divides both a and b, leading to the conclusion that gcd(a, b) also divides sa + tb. The discussion emphasizes that since sa + tb is a common divisor of a and b, it cannot exceed the greatest common divisor, d. The definition of gcd(a, b) asserts that any common divisor must divide the gcd itself. Therefore, since sa + tb divides both a and b, it follows that sa + tb must also divide gcd(a, b). The key takeaway is that any common divisor of a and b, including sa + tb, is inherently a divisor of their gcd.
nicodemus1
Messages
16
Reaction score
0
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.
 
Mathematics news on Phys.org
nicodemus said:
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.
 
Good Day,

Thank you for your reply.

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

Thanks & Regards,
Nicodemus
 
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)?
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top