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$.

For the converse you can use the Euclidean algorithm.  See Bezóut's identity . ..
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