[proofplan]
We show that the ideal generated by the list has a unique positive generator, and that this generator is exactly the [greatest common divisor](/page/Greatest%20Common%20Divisor). The positive generator is obtained as the least positive element of the generated ideal, and the [division algorithm](/theorems/725) shows that it divides every element of the ideal. This identifies the ideal with $d\mathbb{Z}$, where $d$ is the gcd, and the stated equivalence follows by comparing $c\mathbb{Z}$ with this principal ideal.
[/proofplan]
[step:Construct the positive generator of the generated ideal]
Define the generated ideal
\begin{align*}
I := (a_1,\dots,a_n) = \left\{\sum_{i=1}^{n} a_i x_i : x_1,\dots,x_n \in \mathbb{Z}\right\}.
\end{align*}
Since the integers $a_1,\dots,a_n$ are not all zero, there exists an index $j \in \{1,\dots,n\}$ such that $a_j \ne 0$. Thus $a_j \in I$, so $|a_j| \in I$ as well, because $I$ is closed under multiplication by $-1$. Therefore the set
\begin{align*}
S := I \cap \mathbb{N}
\end{align*}
is nonempty. By the [well-ordering principle](/theorems/721), $S$ has a least element. Denote this least element by $d \in \mathbb{N}$.
We claim that $I = d\mathbb{Z}$. Since $d \in I$ and $I$ is closed under integer multiplication, $d\mathbb{Z} \subset I$. Conversely, let $m \in I$. By the division algorithm applied to $m$ and the positive integer $d$, there exist $q,r \in \mathbb{Z}$ with
\begin{align*}
m = qd + r
\end{align*}
and $0 \le r < d$. Since $m \in I$ and $qd \in I$, closure under subtraction gives
\begin{align*}
r = m - qd \in I.
\end{align*}
If $r > 0$, then $r \in I \cap \mathbb{N}=S$ and $r < d$, contradicting the minimality of $d$. Hence $r=0$, so $m=qd \in d\mathbb{Z}$. Therefore $I \subset d\mathbb{Z}$, and so
\begin{align*}
I = d\mathbb{Z}.
\end{align*}
[guided]
We first turn the list of integers into an ideal whose positive generator can be studied. Define
\begin{align*}
I := (a_1,\dots,a_n) = \left\{\sum_{i=1}^{n} a_i x_i : x_1,\dots,x_n \in \mathbb{Z}\right\}.
\end{align*}
This is the set of all integer linear combinations of the listed integers.
Because the list is not identically zero, there is an index $j \in \{1,\dots,n\}$ such that $a_j \ne 0$. Taking $x_j=1$ and all other coefficients equal to $0$ shows that $a_j \in I$. Since $I$ is closed under multiplication by integers, $-a_j \in I$ whenever $a_j \in I$, and therefore $|a_j| \in I$. Thus the set
\begin{align*}
S := I \cap \mathbb{N}
\end{align*}
is nonempty. By the well-ordering principle, $S$ has a least element; call it $d$. Thus $d$ is a positive element of $I$, and no smaller positive integer lies in $I$.
The key point is to show that every element of $I$ is an integer multiple of $d$. The inclusion $d\mathbb{Z} \subset I$ follows from $d \in I$ and closure of $I$ under integer multiplication. For the reverse inclusion, take any $m \in I$. Applying the division algorithm to $m$ and the positive integer $d$, there exist $q,r \in \mathbb{Z}$ such that
\begin{align*}
m = qd + r
\end{align*}
with $0 \le r < d$. Since both $m$ and $qd$ lie in $I$, their difference also lies in $I$:
\begin{align*}
r = m - qd \in I.
\end{align*}
If $r$ were positive, then $r$ would be an element of $S = I \cap \mathbb{N}$ smaller than $d$, contradicting the defining minimality of $d$. Therefore $r=0$. Hence $m=qd$, so $m \in d\mathbb{Z}$. Since $m \in I$ was arbitrary, $I \subset d\mathbb{Z}$.
Combining the two inclusions gives
\begin{align*}
I = d\mathbb{Z}.
\end{align*}
[/guided]
[/step]
[step:Identify the positive generator as the greatest common divisor]
We show that the integer $d$ constructed above is $\gcd(a_1,\dots,a_n)$. For each $i \in \{1,\dots,n\}$, the integer $a_i$ lies in $I=d\mathbb{Z}$, so $d \mid a_i$. Thus $d$ is a common divisor of $a_1,\dots,a_n$.
Now let $e \in \mathbb{Z}$ be any common divisor of $a_1,\dots,a_n$. For every choice of integers $x_1,\dots,x_n \in \mathbb{Z}$, the divisibility assumptions $e \mid a_i$ imply
\begin{align*}
e \mid \sum_{i=1}^{n} a_i x_i.
\end{align*}
Since $d \in I$, there exist $y_1,\dots,y_n \in \mathbb{Z}$ such that
\begin{align*}
d = \sum_{i=1}^{n} a_i y_i.
\end{align*}
Therefore $e \mid d$. Hence every common divisor of $a_1,\dots,a_n$ divides $d$, while $d$ itself is a nonnegative common divisor. By the definition of the greatest common divisor,
\begin{align*}
d = \gcd(a_1,\dots,a_n).
\end{align*}
[/step]
[step:Compare $c\mathbb{Z}$ with the generated ideal]
First suppose
\begin{align*}
c = \gcd(a_1,\dots,a_n).
\end{align*}
By the previous step, the least positive generator $d$ of $I$ satisfies
\begin{align*}
d = \gcd(a_1,\dots,a_n).
\end{align*}
Thus $c=d$, and therefore
\begin{align*}
(a_1,\dots,a_n)=I=d\mathbb{Z}=c\mathbb{Z}.
\end{align*}
Conversely, suppose
\begin{align*}
(a_1,\dots,a_n)=c\mathbb{Z}.
\end{align*}
From the construction above, $I=d\mathbb{Z}$ with
\begin{align*}
d=\gcd(a_1,\dots,a_n).
\end{align*}
Hence $c\mathbb{Z}=d\mathbb{Z}$, where $c,d \in \mathbb{Z}_{\ge 0}$ and $d>0$. Since $d \in d\mathbb{Z}=c\mathbb{Z}$, we have $c \mid d$. Since $c \in c\mathbb{Z}=d\mathbb{Z}$, we have $d \mid c$. The nonnegative integers $c$ and $d$ therefore divide each other, so $c=d$. Consequently
\begin{align*}
c = \gcd(a_1,\dots,a_n).
\end{align*}
This proves both implications.
[/step]
