How do I prove this very basic gcd equivalence for the case where there is no common divisor except 1?

Question

I want to prove the basic property of gcd that for some integer $a,b$ $gcd(a,b) = 1$ iff there exists some integers $k$ and $l$ in $ak + bl = 1$. I've been using this basic property for a long time and always assumed it to be true, but cannot find a basic proof for this.

I would express the gcd as the smallest linear combination of a and b, but this will force me to conclude that since 1 is the smallest linear combination, then the iff condition is satisfied. But this doesn't seem to be the right approach however intuitive, since I did not prove the implication both ways. Is there a way I could formally prove this?

Answer 1

One direction is easy, namely if $ax+by=1$, then the gcd is $1$.

For the converse you can use the Euclidean algorithm. See Bezóut's identity . ..

Answer 2

If I understand which direction you are trying to prove:

Suppose $d>0$ divides both $a$ and $b$, with $a=ed$ and $b=fd$.

Then given that $ak + bl = 1$, we have $(ke+fl)d=1$, so $d$ divides $1$, meaning that $d \le 1$. Combined with $d>0$ this gives $d=1$.

Answer 3

The proof is rather long. but if you're interested you could look in this book which is a number theory book. http://www.fuchs-braun.com/media/532896481f9c1c47ffff8077fffffff0.pdf The theorem is called theorem 1.3 and it is stated and proven on page seven