[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*}[/step]

[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: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]