You wrote it yourself: the gcd is the smallest positive linear combination. Smallest positive linear combination is shorthand for smallest positive number which is a linear combination. It is true that $0$ is a linear combination of $12$ and $6$ with integer coefficients, but $0$ is not positive.
The proof is not difficult, but it is somewhat lengthy. We give full detail below.
Let $e$ be the smallest positive linear combination $as+bt$ of $a$ and $b$, where $s$ and $t$ are integers. Suppose in particular that $e=ax+by$.
Let $d=\gcd(a,b)$. Then $d$ divides $a$ and $b$, so it divides $ax+by$. Thus $d$ divides $e$, and therefore in particular $d\le e$.
We show that in fact $e$ is a common divisor of $a$ and $b$, which will imply that $e\le d$. That, together with our earlier $d\le e$, will imply that $d=e$.
So it remains to show that $e$ divides $a$ and $e$ divides $b$. We show that $e$ divides $a$. The proof that $e$ divides $b$ is essentially the same.
Suppose to the contrary that $e$ does not divide $a$. Then when we try to divide $a$ by $e$, we get a positive remainder. More precisely,
$$a=qe+r,$$
where $0\lt r\lt e$. Then
$$r=a-qe=a-q(ax+by)=a(1-qx)+b(-qy).$$
This means that $r$ is a linear combination of $a$ and $b$, and is positive and less than $e$. This contradicts the fact that $e$ is the smallest positive linear combination of $a$ and $b$.
Set $c=\gcd(a,b)$ and $d=\gcd(a,b-a)$ for convenience.
Step 1: Prove that $c$ is a common divisor of $a,b-a$. This proves $c\le d$.
Step 2: Prove that $d$ is a common divisor of $a,b$. This proves $d\le c$.
Best Answer
The procedure very briefly sketched in your comment is the standard way to prove Theorem 1.
For Theorem 2, the proof depends on exactly how the gcd of $a$ and $b$ is defined. Suppose it is defined in the naive way as the largest number which is a common divisor of $a$ and $b$.
We then need to show that there cannot be a larger common divisor of $a$ and $b$ than the smallest positive linear combination of these numbers.
Let $w$ be the smallest positive linear combination of $a$ and $b$, and let $d$ be their largest common divisor.
There exist integers $x$ and $y$ such that $w=ax+by$. Since $d$ divides $a$ and $b$, it follows that $d$ divides $ax+by$. So $d$ divides $w$, and therefore $d\le w$.
Your proof of Theorem 1 shows that $w$ is a positive common divisor of $a$ and $b$, so $w\le d$. It follows that $d=w$.
Remark: An alternate definition of the gcd is that it is a positive integer $d$ which is a common divisor of $a$ and $b$, and such that any common divisor of $a$ and $b$ divides $d$. Theorem 2 can also be proved in a straightforward way using that alternate (but equivalent) definition.