Smallest positive element of $ \{ax + by: x,y \in \mathbb{Z}\}$ is $\gcd(a,b)$

When I first saw this problem, I was pretty surprised at how the proof went, so I'll just get you started on it.

By the Division Theorem, we have: $$a=qe+r \text{ for } 0 \leq r < e$$ Now, we need to show $r=0$. To do this, we can use the fact that $e=ax+by$ for some $x,y \in \Bbb{Z}$ and that $a=1a+0b$, so: $$1a+0b=q(ax+by)+r \implies a(1-qx)-bqy=r$$ Now we can combine the fact that $r=au+bv$ for $u,v \in \Bbb{Z}$ and that $0 \leq r < e$ to prove $r=0$.