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$?
HINT: Consider the smallest positive integer that can be written as $ax+by$
Sign up using Google
Sign up using Facebook
Sign up using Stack Exchange
2 years ago