Show that $gcd(a,b) |d $ and hence $gcd(a, b) \leq d$, where $d$ is the smallest number of the form $ma+nb$

Question

Show that if $d$ is the smallest element in the set $S = \{s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb \}$ such that $d = ax + by$ then $\gcd(a,b) |d $ and hence $\gcd(a, b) \leq d$

Answer 1

You can write $a$ as $q_1\gcd(a,b)$ and $b$ as $q_2\gcd(a,b)$ therefore $ma+mb=(mq_1+nq_2)\gcd(a,b)$ and it is obvious that for every $m,n$ it will be divisible by $\gcd(a,b)$. I'll leave it to you to prove that $\gcd(a,b)$ is the lowest value greater than zero it can take.