The greatest common divisor is the smallest positive linear combination How to prove the following theorems about gcd?

Theorem 1: Let $a$ and $b$ be nonzero integers. Then the smallest positive linear combination of $a$ and $b$ is a common divisor of $a$ and $b$.
Theorem 2: Let $a$ and $b$ be nonzero integers. The gcd of $a$ and $b$ is the smallest positive linear combination of $a$ and $b$.

Progress
For Theorem 1 I have assumed that $d$ is the smallest possible linear combination of $a$ and $d$. Then $a = dq + r$. Solved it and found a contradiction. Is my method correct? Don't know what to do for Theorem 2.

Theorem 1 is equivalent to asking: Is the remainder $r$ a linear combination of $a, b$?
If $d$ would not divide $a$, by division theorem: $a=dq+r, 0\lt r\lt d$. Furthermore, $a=dq+r\implies r=a-dq$, which means $r$ is a linear combination of $a$ and $b$, and it less than $d$, a contradiction that $d$ is the smallest. By the same idea we can prove $d$ divides $b$, so $d$ is a common divisor of $a$ and $b$.
