3
$\begingroup$

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 Answers 1

3

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

  • 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