GCD to Linear Diophantine Equation without Euclid Algorithm

Is there a technique other than performing Euclid's algorithm in reverse that can elegantly show that if GCD$(a,b) = d$ then there exist integers $x$ and $y$ such that $ax + by = d$?

-

1 Answer

HINT: Consider the smallest positive integer that can be written as $ax+by$

-
This is perfect. Thanks. But apparently there is a time limit on quickly an answer can be accepted so I up-voted for the moment. – dcdo Sep 30 '12 at 15:37
@dcdo See here for full details and conceptual elaboration. – Bill Dubuque Sep 30 '12 at 16:05