Prove that for any integers x,y there are integers a,b such that gcd(x,y) = ax + by

Question

How would I go about proving that: For any integers x,y there are integers a,b such that gcd(x,y) = ax + by?

One thing I noticed is that when x is a multiple of y or vice versa, the smaller number is automatically the gcd; thus, in those situations, the value multiplied by the smaller number would be 1 and the value multiplied by the larger number would be 0 and we would have an "a,b" which would be "1,0" or "0,1". However, in other cases it's a bit more complicated, and we also have negative integers, of course.

Any help would be greatly appreciated!

This property is called Bezout's identity. http://en.wikipedia.org/wiki/B%C3%A9zout's_identity — Ojas, Nov 16 '14 at 21:48

score 1 · Answer 1 · answered Nov 16 '14 at 21:56

1

A non constructive proof: consider the set $$ X=\{ax+by: x,y\in\mathbb{Z}, ax+by>0\} $$ and prove that

$X\ne\emptyset$;
if $d$ is the minimum element in $X$, then $d=\gcd(a,b)$.

answered Nov 16 '14 at 21:56

egreg

238,574

Thanks a lot, very helpful! – user193093 Nov 16 '14 at 23:46

score 0 · Accepted Answer · answered Nov 16 '14 at 21:48

0

This is called the Bezout lemma and one proof is here

answered Nov 16 '14 at 21:48

Adhvaitha

5,441

Thank you, very helpful. – user193093 Nov 16 '14 at 23:45

Prove that for any integers x,y there are integers a,b such that gcd(x,y) = ax + by

2 Answers2