[proofplan]
We identify the ideal $(a,b)$ with the set of all integer linear combinations of $a$ and $b$. Since $a$ and $b$ are not both zero, this ideal contains a positive integer; we take its smallest positive element $m$. The Euclidean division argument shows that $m$ divides both $a$ and $b$, while any common divisor of $a$ and $b$ divides every element of $(a,b)$, hence divides $m$. Thus $m=\gcd(a,b)$ and $(a,b)=m\mathbb{Z}$, from which the stated equivalence and the smallest-positive-combination formulation follow.
[/proofplan]
[step:Choose the smallest positive integer combination]
Define the subset $I \subset \mathbb{Z}$ by
\begin{align*}
I := (a,b) = a\mathbb{Z} + b\mathbb{Z} = \{ax + by : x,y \in \mathbb{Z}\}.
\end{align*}
Since $a$ and $b$ are not both zero, at least one of $|a|$ and $|b|$ is a positive element of $I$. Indeed, if $a>0$, then $|a|=a=a1+b0\in I$, while if $a<0$, then $|a|=-a=a(-1)+b0\in I$; the same argument with $b$ in place of $a$ applies when $b\ne 0$. Define the set of positive elements of $I$ by
\begin{align*}
I_{>0} := I \cap \mathbb{Z}_{>0}, \qquad \mathbb{Z}_{>0}:=\{n\in\mathbb{Z}:n>0\}.
\end{align*}
Thus $I_{>0}$ is nonempty. By the [well-ordering principle](/theorems/721) for positive integers, there is a least element $m \in I_{>0}$.
Since $m \in I$, there exist $x_0,y_0 \in \mathbb{Z}$ such that
\begin{align*}
m = ax_0 + by_0.
\end{align*}
[/step]
[step:Show the least positive combination divides both generators]
We prove that $m \mid a$ and $m \mid b$. By Euclidean division applied to $a$ by the positive integer $m$, there exist $q,r \in \mathbb{Z}$ such that
\begin{align*}
a = qm + r
\end{align*}
and $0 \le r < m$. Since $a \in I$ and $m \in I$, and since $I$ is closed under integer linear combinations, the integer
\begin{align*}
r = a - qm
\end{align*}
also belongs to $I$. If $r > 0$, then $r \in I_{>0}$ and $r < m$, contradicting the minimality of $m$. Therefore $r=0$, so $a=qm$ and $m \mid a$.
The same argument applied to $b$ gives $m \mid b$.
[guided]
The purpose of this step is to turn the minimality of $m$ into a divisibility statement. We know $m$ is an integer linear combination of $a$ and $b$, but we must prove the stronger assertion that $m$ divides each generator $a$ and $b$.
Apply Euclidean division to $a$ by the positive integer $m$. This gives integers $q,r \in \mathbb{Z}$ satisfying
\begin{align*}
a = qm + r
\end{align*}
with $0 \le r < m$. Rearranging gives
\begin{align*}
r = a - qm.
\end{align*}
Now $a \in I$ because $a = a1 + b0$, and $m \in I$ by construction. Since $I = a\mathbb{Z}+b\mathbb{Z}$ is closed under integer linear combinations, $a-qm \in I$. Hence $r \in I$.
There are only two possibilities. If $r>0$, then $r$ is a positive element of $I$ that is smaller than $m$, contradicting the definition of $m$ as the least positive element of $I$. Therefore $r=0$. Substituting back into the division equation gives
\begin{align*}
a = qm,
\end{align*}
so $m \mid a$.
Repeating the identical Euclidean division argument with $b$ in place of $a$ gives integers $q',r' \in \mathbb{Z}$ with
\begin{align*}
b = q'm + r'
\end{align*}
and $0 \le r' < m$. Since $r'=b-q'm \in I$, minimality again forces $r'=0$. Thus $b=q'm$, and $m \mid b$.
[/guided]
[/step]
[step:Show every common divisor divides the least positive combination]
Let $d \in \mathbb{Z}$ be a common divisor of $a$ and $b$. Then there exist $\alpha,\beta \in \mathbb{Z}$ such that
\begin{align*}
a = d\alpha
\end{align*}
and
\begin{align*}
b = d\beta.
\end{align*}
For arbitrary $x,y \in \mathbb{Z}$, we have
\begin{align*}
ax + by = d\alpha x + d\beta y = d(\alpha x + \beta y),
\end{align*}
so $d$ divides every element of $I$. Since $m \in I$, it follows that $d \mid m$.
Together with $m \mid a$ and $m \mid b$, this shows that $m$ is a positive common divisor of $a$ and $b$ divisible by every common divisor of $a$ and $b$. Therefore
\begin{align*}
m = \gcd(a,b).
\end{align*}
[/step]
[step:Identify the generated ideal with the gcd ideal]
We prove that $I=m\mathbb{Z}$. First, since $m \in I$ and $I$ is closed under multiplication by integers, every multiple of $m$ lies in $I$. Hence
\begin{align*}
m\mathbb{Z} \subset I.
\end{align*}
Conversely, since $m \mid a$ and $m \mid b$, there exist $\alpha,\beta \in \mathbb{Z}$ such that
\begin{align*}
a = m\alpha
\end{align*}
and
\begin{align*}
b = m\beta.
\end{align*}
For every element $z \in I$, choose $x,y \in \mathbb{Z}$ such that $z=ax+by$. Then
\begin{align*}
z = m\alpha x + m\beta y = m(\alpha x+\beta y),
\end{align*}
so $z \in m\mathbb{Z}$. Therefore $I \subset m\mathbb{Z}$, and hence
\begin{align*}
I = m\mathbb{Z}.
\end{align*}
Since the preceding step proved $m=\gcd(a,b)$, we obtain
\begin{align*}
(a,b)=\gcd(a,b)\mathbb{Z}.
\end{align*}
[/step]
[step:Derive the equivalence for an arbitrary nonnegative generator]
Let $c \in \mathbb{Z}_{\ge 0}$.
If $c=\gcd(a,b)$, then the identity just proved gives
\begin{align*}
(a,b)=c\mathbb{Z}.
\end{align*}
Conversely, suppose
\begin{align*}
(a,b)=c\mathbb{Z}.
\end{align*}
From the previous step,
\begin{align*}
(a,b)=m\mathbb{Z},
\end{align*}
where $m=\gcd(a,b)$ and $m>0$. Hence
\begin{align*}
c\mathbb{Z}=m\mathbb{Z}.
\end{align*}
Since $m \in c\mathbb{Z}$, we have $c \mid m$. Since $c \in m\mathbb{Z}$, we have $m \mid c$. The integers $c$ and $m$ are both nonnegative, and $m>0$, so mutual divisibility gives $c=m$. Therefore
\begin{align*}
c=\gcd(a,b).
\end{align*}
[/step]
[step:Extract the smallest positive linear combination formulation]
By definition,
\begin{align*}
(a,b)=\{ax+by:x,y\in\mathbb{Z}\}.
\end{align*}
The element $m$ was chosen as the smallest positive element of this set, and the proof above showed that
\begin{align*}
m=\gcd(a,b).
\end{align*}
Therefore $\gcd(a,b)$ is the smallest positive integer of the form $ax+by$ with $x,y \in \mathbb{Z}$. This proves the equivalent formulation and completes the proof.
[/step]
