Greatest common divisor

HOME

Math Central

Quandaries & Queries

Question from Marie, a student:

How do I prove this?

Let h be the greatest common divisor of the positive integers a and b.
Show that there exist integers p and q (not necessarily positive) such that pa + qb = h.

Thanks

Marie,

Do you know the Euclidean Algorithm? The result that you wants comes from using it to find the gcd of a and b and then reversing the steps.

Penny

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.