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$?
GCD to Linear Diophantine Equation without Euclid Algorithm
3
$\begingroup$
elementary-number-theory
diophantine-equations
self-learning
1 Answers
3
HINT: Consider the smallest positive integer that can be written as $ax+by$
-
1This is perfect. Thanks. But apparently there is a time limit on quickly an answer can be accepted so I up-voted for the moment. – 2012-09-30
-
0@dcdo [See here](http://math.stackexchange.com/a/203450/242) for full details and conceptual elaboration. – 2012-09-30
-
0Sorry, I don't get it. Smallest positive integer can be a.1 + b.1 = a + b. Then? – 2018-10-12
-
0@sud_ $x$ and $y$ don't have to be positive, just $ax+by$. If the smallest such number is $d'$, show that $d$ divides $d'$ and that $d'$ divides both $a$ and $b$. See the link in Bill's comment for more details. – 2018-10-13