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

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?

One direction is easy, namely if $ax+by=1$, then the gcd is $1$.
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$.