Show that for any $s \in S$ where $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}$, we have $d|s$ where $d$ is the smallest element

Question

Explain why the set $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb $} has a smallest element, call it d, so we know there exists $x,y \in \mathbb{Z}$ such that $d = ax + by$, and show that for any $s \in S$, we have $d|s$.

My Work:

I am assuming that since $S \in \mathbb{N}$ we know that it has a smallest element because of the well ordering principle, therefore we know there exists $d$ such that $d = ax + by$. For the second part, I am going to assume a contradiction such that $d\not| s$. If we apply the division algorithm we get $q,r \in \mathbb{Z}$ such that $s = qd + r$ with $ 0 \leq r < d$. And then somehow show that $r \in S$

Answer 1

Hint $\,\ r = s\!-\!qd = am\!+\!bn-q(ax\!+\!by) = a(m\!-\!qx)+b(n\!-\!qy)\in S.$

Alternatively, $S$ is closed under subtraction, so also under mod = iterated subtraction, i.e. $\ s\ {\rm mod}\ d\, =\, s-qd = ((s-d)-d)- \cdots -d.\ $ Again, see my comment on your prior question for the conceptual background.

Answer 2

HINT: $$s=ma+nb$$ and $$d=xa+yb$$ so what does $$r=s-qd$$ equal? Why must it therefore be in $S$? Nevmind the guy above stole it... aw well