[proofplan]
The strategy is to extract the least positive element $d$ of $I$ and show that $I = d\mathbb{Z}$ by two inclusions. The inclusion $d\mathbb{Z} \subseteq I$ is immediate from closure of $I$ under integer multiplication. The reverse inclusion $I \subseteq d\mathbb{Z}$ is the content of the argument: given $a \in I$, the division algorithm produces a remainder $r$ with $0 \leq r < d$; because $r$ is itself an integer linear combination of elements of $I$, the minimality of $d$ forces $r = 0$. Uniqueness of $d$ follows because a positive generator of $d\mathbb{Z}$ is unique.
[/proofplan]
[step:Verify that $I$ is closed under integer linear combinations]
Define the map
\begin{align*}
I : \mathbb{Z} \setminus \{0\} &\to \mathcal{P}(\mathbb{Z}) \\
(a_1, \ldots, a_n) &\mapsto \{\lambda_1 a_1 + \cdots + \lambda_n a_n : \lambda_1, \ldots, \lambda_n \in \mathbb{Z}\},
\end{align*}
where we fix a tuple $(a_1, \ldots, a_n)$ not all zero and write $I$ for the value of this map. We verify two closure properties.
First, $I$ is closed under addition: if $b = \sum_i \lambda_i a_i$ and $b' = \sum_i \lambda'_i a_i$, then
\begin{align*}
b + b' &= \sum_{i=1}^n (\lambda_i + \lambda'_i) a_i \in I.
\end{align*}
Second, $I$ is closed under multiplication by any $\mu \in \mathbb{Z}$: if $b = \sum_i \lambda_i a_i$, then
\begin{align*}
\mu b &= \sum_{i=1}^n (\mu \lambda_i) a_i \in I.
\end{align*}
In particular, $0 = \sum_i 0 \cdot a_i \in I$, and whenever $b \in I$, also $-b \in I$.
[/step]
[step:Exhibit a positive element of $I$]
Since not all $a_i$ are zero, fix an index $k$ with $a_k \neq 0$. Then either $a_k > 0$ (in which case $a_k \in I$ is positive) or $a_k < 0$ (in which case, by the closure under negation established in the previous step, $-a_k \in I$ is positive). Hence the set
\begin{align*}
I_+ &:= \{m \in I : m > 0\}
\end{align*}
is non-empty.
[/step]
[step:Extract the least positive element $d$ of $I$]
The set $I_+$ is a non-empty subset of the positive integers. By the well-ordering principle for $\mathbb{N}$, $I_+$ has a least element; call it $d$. By construction $d \in I$ and $d \geq 1$.
[guided]
We want a single positive generator for $I$, and the candidate is the smallest positive element. The well-ordering principle — every non-empty subset of $\mathbb{N} = \{1, 2, 3, \ldots\}$ has a least element — is exactly the tool to produce it. We verified in the previous step that $I_+$ is non-empty, so well-ordering applies and yields $d := \min I_+$. Since $d \in I_+$, both $d \in I$ and $d \geq 1$ hold. Why does well-ordering give us exactly what we need? Because minimality is what we will use in the division-algorithm step: any element of $I$ strictly smaller than $d$ must be zero, since no positive element of $I$ is smaller than $d$.
[/guided]
[/step]
[step:Establish the inclusion $d\mathbb{Z} \subseteq I$]
Let $\lambda \in \mathbb{Z}$. Since $d \in I$ and $I$ is closed under multiplication by integers (Step 1), $\lambda d \in I$. Therefore every element of $d\mathbb{Z} = \{\lambda d : \lambda \in \mathbb{Z}\}$ lies in $I$, giving
\begin{align*}
d\mathbb{Z} &\subseteq I.
\end{align*}
[/step]
[step:Apply the division algorithm to prove $I \subseteq d\mathbb{Z}$]
Let $a \in I$ be arbitrary. By the [Division Algorithm for Integers](/theorems/???), since $d \geq 1$, there exist unique integers $q, r$ with
\begin{align*}
a &= q d + r, \qquad 0 \leq r < d.
\end{align*}
We show $r = 0$. Rearranging, $r = a - q d$. Now $a \in I$ and $q d \in d\mathbb{Z} \subseteq I$ (by the previous step), and $I$ is closed under addition and negation (Step 1), so $r = a + (-q d) \in I$.
Suppose for contradiction that $r > 0$. Then $r \in I_+$ with $r < d$, contradicting the minimality of $d$ as the least element of $I_+$. Therefore $r = 0$, whence $a = q d \in d\mathbb{Z}$.
Since $a \in I$ was arbitrary,
\begin{align*}
I &\subseteq d\mathbb{Z}.
\end{align*}
[guided]
The key idea is that if $I$ contained any element $a$ that was not a multiple of $d$, then the "defect" — the remainder $r$ when $a$ is divided by $d$ — would be a strictly smaller positive element of $I$, contradicting the minimality of $d$.
Why is $r \in I$? We assembled $r$ from two pieces both lying in $I$: the element $a$ itself is in $I$ by assumption, and $q d$ is in $I$ because $d \in I$ and $I$ is closed under multiplication by the integer $q$. The closure of $I$ under addition (applied to $a$ and $-q d$) then yields $r = a - q d \in I$.
Once we know $r \in I$ and $0 \leq r < d$, the dichotomy is stark: either $r = 0$ (good, it gives $a \in d\mathbb{Z}$), or $r > 0$, which would make $r$ a positive element of $I$ strictly less than the minimum of $I_+$. The latter is impossible, so $r = 0$.
Why does this argument need the division algorithm specifically? The division algorithm is what guarantees the existence of $q$ and $r$ with the crucial size constraint $0 \leq r < d$. Without that constraint, subtracting a multiple of $d$ from $a$ could yield any integer, and the minimality of $d$ would give no contradiction.
[/guided]
[/step]
[step:Combine the two inclusions and establish uniqueness]
From the inclusions $d\mathbb{Z} \subseteq I$ and $I \subseteq d\mathbb{Z}$ we conclude
\begin{align*}
I &= d\mathbb{Z}.
\end{align*}
For uniqueness, suppose $d'$ is another positive integer with $I = d'\mathbb{Z}$. Then $d \in I = d'\mathbb{Z}$, so $d' \mid d$, and $d' \in I = d\mathbb{Z}$, so $d \mid d'$. Two positive integers that divide each other are equal, so $d = d'$.
This completes the proof that there exists a unique positive integer $d \geq 1$ with $I = d\mathbb{Z}$.
[/step]
