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.

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. 
