Let \(d = \gcd(a, b)\), and lets define two sets (\(S\) and \(T\)):
$$\begin{align}S &= \{as+bt | s,t \in \mathbb{Z} \} \\ T &= \{nd| n \in \mathbb{Z}\} \end{align}$$
Since \(d\) is the smallest linear combination of \(a\) and \(b\) (let's call it \(ax+by\)) then \(T \subseteq S\):
$$\begin{align} d &= ax + by \in S \\ 2d &= a(2x) + b(2y) \in S \\ 3d &= a(3x) + b(3y) \in S \end{align}$$
Since \(d = \gcd(a, b)\), then \(d|a\) and \(d|b\). ∴ \(a = kd\) and \(b = hd\):
$$\begin{align} S &= \{as + bt\} \\ &= \{ d(ks) + d(ht) \} \\ &= \{ (ks+ht)d \} \end{align}$$
∴ \(S \subseteq T\). Since \(T \subseteq S\) and \(S \subseteq T\), then \(S = T\).