Is this a valid proof that $\{ax + by|x,y \in \Bbb Z\}= \{n\times \gcd(a, b) |n\in \Bbb Z\}$? I'm trying to prove that $\{ax + by|x,y \in \Bbb Z\}= \{n\times \gcd(a, b) |n\in \Bbb Z\}$, but I'm unsure on the . The main proposition I'm using to solve this is that $\exists x,y, ax+by = \gcd(a, b)$. However, I'm having trouble with the exact mathematical presentation of the proof. I don't have a formal education in proofs, and so that's why I ask; is this a valid proof of this proposition?
$$\{n\times \gcd(a, b) |n\in \Bbb Z\}$$
$$= \{n\times (as + bt) |n,s,t\in \Bbb Z\}$$
$$= \{a(ns) + b(nt) |n,s,t\in \Bbb Z\}$$
And, because we know that $ns=x\in \Bbb Z$ and $nt=y \in \Bbb Z$, we can conclude that:
$$= \{ax + by |x,y\in \Bbb Z\}$$
The main issue I'm having is with the first step: is that equality even valid? It seems that 
$= \{n\times (as + bt) |n,s,t\in \Bbb Z\}$ has more elements than $\{n\times \gcd(a, b) |n\in \Bbb Z\}$.

Since there exist $x_0,y_0 \in \mathbb Z$ such that $ax_0 + by_0 = \gcd(a,b)$, 
for any $n \in \mathbb Z$ you have
$$n \gcd(a,b) = a(nx_0) + b(ny_0) \in \{ax+by|x,y \in {\mathbb Z}\}$$
For the other direction you want to say that for all $x,y \in \mathbb Z$, $ax + by$ is a multiple of $\gcd(a,b)$.  This is because there exist $n_1, n_2 \in \mathbb Z$ such that $a = n_1 \gcd(a,b)$ and $b = n_2 \gcd(a,b)$, and then
$ax + by = \ldots \gcd(a,b)$.
