This is the proof I have:
Lets see why $\gcd(a, b) $ is the smallest positive linear combination of $a$ and $b$:
Let $LC = \{ s'a + t'b : s', t' \in \mathbb{Z}, s'a + t'b > 0 \}$. By the definition $\gcd(a,b) \mid a$ and $\gcd(a,b) \mid b$. Hence, it divides any linear combination of a and b i.e. $\forall (s'a + t'b) \in LC$, $ \gcd(a,b) \mid s'a + t'b $. Thus, $\gcd(a,b) \leq s'a + t'b $. But notice $\gcd(a,b)$ is itself a linear combination of $a$ and $b$. Thus, $\gcd(a,b) \in LC$. Therefore, $\gcd(a,b)$ cannot be larger than any $s'a + t'b$, because if it was larger then it wouldn't divide it. Therefore, it must be small than all elements of $LC$.
So I was wondering if this proof was correct or if there was a way to explain it in a better or more concise way. I only use as a given that we know Euclid's algorithm and hence know that there is some linear combination that expresses the gcd just not the smallest.