[proofplan] We construct the [greatest common divisor](/page/Greatest%20Common%20Divisor) as the least positive integer linear combination of $a$ and $b$. The [division algorithm](/theorems/725) then shows that this least positive linear combination divides both $a$ and $b$. Every common divisor of $a$ and $b$ divides every integer linear combination of $a$ and $b$, so it divides the constructed integer. Finally, two nonnegative integers satisfying the same universal divisibility property divide each other, forcing equality. [/proofplan] [step:Choose the least positive integer linear combination of $a$ and $b$] Define the set \begin{align*} S := \{ax + by : x,y \in \mathbb{Z},\ ax + by > 0\} \subset \mathbb{Z}_{>0}. \end{align*} The set $S$ is nonempty. Indeed, since $a$ and $b$ are not both zero, at least one of $a$ and $b$ is nonzero. If $a \ne 0$, choose $\varepsilon \in \{-1,1\}$ such that $\varepsilon a = |a|$; then $a\varepsilon + b0 = |a| > 0$, so $|a| \in S$. If $a = 0$, then $b \ne 0$, and choosing $\delta \in \{-1,1\}$ such that $\delta b = |b|$ gives $a0 + b\delta = |b| > 0$, so $|b| \in S$. By the [well-ordering principle](/theorems/721) for nonempty subsets of $\mathbb{Z}_{>0}$, the set $S$ has a least element. Let $c \in S$ denote this least element. Then $c > 0$, and there exist $x_0,y_0 \in \mathbb{Z}$ such that \begin{align*} c = ax_0 + by_0. \end{align*} [guided] The goal is to find a candidate for the greatest common divisor using only divisibility in $\mathbb{Z}$. The standard construction is to look at all positive integer linear combinations of $a$ and $b$, because common divisors automatically divide such combinations. Define \begin{align*} S := \{ax + by : x,y \in \mathbb{Z},\ ax + by > 0\} \subset \mathbb{Z}_{>0}. \end{align*} We first verify that this set is nonempty. Since $a$ and $b$ are not both zero, at least one is nonzero. If $a \ne 0$, choose $\varepsilon \in \{-1,1\}$ so that $\varepsilon a = |a|$. Then \begin{align*} a\varepsilon + b0 = |a| > 0, \end{align*} so $|a| \in S$. If $a = 0$, then $b \ne 0$, and choosing $\delta \in \{-1,1\}$ so that $\delta b = |b|$ gives \begin{align*} a0 + b\delta = |b| > 0, \end{align*} so $|b| \in S$. Thus $S$ is a nonempty subset of the positive integers. By the well-ordering principle for nonempty subsets of $\mathbb{Z}_{>0}$, there is a least element of $S$. Denote this least element by $c$. Since $c \in S$, we have $c > 0$, and by the definition of $S$ there exist integers $x_0,y_0 \in \mathbb{Z}$ such that \begin{align*} c = ax_0 + by_0. \end{align*} This equation is the Bezout-type representation that will make the universal property work. [/guided] [/step] [step:Use the division algorithm to prove that $c$ divides $a$ and $b$] Apply the division algorithm to $a$ with positive divisor $c$. There exist $q,r \in \mathbb{Z}$ such that \begin{align*} a = qc + r \quad \text{and} \quad 0 \le r < c. \end{align*} Using $c = ax_0 + by_0$, we compute \begin{align*} r = a - qc = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0). \end{align*} Thus $r$ is an integer linear combination of $a$ and $b$. If $r > 0$, then $r \in S$, contradicting the minimality of $c$ because $r < c$. Hence $r = 0$, so $a = qc$, and therefore $c \mid a$. The same argument applied to $b$ gives integers $q',r' \in \mathbb{Z}$ such that \begin{align*} b = q'c + r' \quad \text{and} \quad 0 \le r' < c. \end{align*} Then \begin{align*} r' = b - q'c = b - q'(ax_0 + by_0) = a(-q'x_0) + b(1 - q'y_0). \end{align*} If $r' > 0$, then $r' \in S$, contradicting $r' < c$ and the minimality of $c$. Therefore $r' = 0$, so $b = q'c$, and hence $c \mid b$. [/step] [step:Show that every common divisor of $a$ and $b$ divides $c$] Let $d \in \mathbb{Z}$ satisfy $d \mid a$ and $d \mid b$. By the definition of divisibility, there exist $m,n \in \mathbb{Z}$ such that \begin{align*} a = dm \quad \text{and} \quad b = dn. \end{align*} Using the representation $c = ax_0 + by_0$, we obtain \begin{align*} c = ax_0 + by_0 = dmx_0 + dny_0 = d(mx_0 + ny_0). \end{align*} Since $mx_0 + ny_0 \in \mathbb{Z}$, this proves $d \mid c$. Therefore $c$ satisfies the stated universal property. [/step] [step:Prove uniqueness from mutual divisibility and nonnegativity] Suppose $c,e \in \mathbb{Z}_{\ge 0}$ both satisfy the stated property. Since $e \mid a$ and $e \mid b$, the universal property of $c$ gives $e \mid c$. Since $c \mid a$ and $c \mid b$, the universal property of $e$ gives $c \mid e$. Thus there exist $u,v \in \mathbb{Z}$ such that \begin{align*} c = eu \quad \text{and} \quad e = cv. \end{align*} The constructed property also forces neither $c$ nor $e$ to be zero: if $c = 0$, then $c \mid a$ and $c \mid b$ imply $a = 0$ and $b = 0$, contrary to the hypothesis, and the same argument applies to $e$. Hence $c,e \in \mathbb{Z}_{>0}$. From $c = eu$ and $e = cv$, both divisibilities between positive integers imply \begin{align*} c \le e \quad \text{and} \quad e \le c. \end{align*} Therefore $c = e$. This proves uniqueness of the nonnegative integer satisfying the stated divisibility property. [/step]