It is known that (quoted from CLRS, 3rd edition)
If $a$ and $b$ are any integers, not both zero, then $\text{gcd}(a, b)$ is the smallest positive element of the set $\{ax + by: x, y \in \mathbb{Z}\}$ of linear combinations of $a$ and $b$.
Generally, we can formulate the problem of computing $x = \text{gcd}(c_1, c_2, \ldots, c_n)$ as an integer programming ($P$), as done in JOTA1977:
\begin{align*} \max & \quad x, \\ \text{subject to } & \quad c_j/x = y_j, \qquad j = 1, 2, \ldots, n, \\ & \quad y_j \in \mathbb{Z}, \qquad j = 1, 2, \ldots, n. \end{align*}
Its dual ($D$) is given as:
\begin{align*} \min & \quad \sum_{j=1}^{n} c_j z_j, \\ \text{subject to } & \quad \sum_{j=1}^{n} c_j z_j > 0, \\ & \quad z_j \in \mathbb{Z}, \qquad j = 1, 2, \ldots, n. \end{align*}
Then JOTA1977 reads,
When the $c_j$'s are all integers and $c \neq 0$, it is noted by Greenberg (Ref. 3) that the greatest common divisor of the $c_j$'s is the minimum of $cz$, subject to $cz \ge 1$ and $z$ integer.
I have no access to Greenberg (Ref. 3).
I have computed the dual of the integer programming above and I got $yz \ge 1$ instead of $cz \ge 1$.
How to obtain the dual of the integer programming for $\text{gcd}$?
(Added 1: I compute the dual by the method of Lagrange Multipliers. (I use it in LP, but I am not sure whether this is valid for ILP.) Multiplying $c_j = x y_j$ by $z_i$, summing the $n$ equality constraints, and letting it be an upper bound for $x$: $x \le cz = yzx$.)
(Added 2: I realized that the integer programming above is not linear due to $c_j/x = y_j$.)
Converting Misha Lavrov's help comment into an answer:
Looking over the Meyer and Fleisher paper (1) it doesn't claim that Greenberg uses duality at all, so I assume that they are just citing a description of the Euclidean algorithm, and (2) they prove strong duality right there in Theorem 2.1.