[proofplan] We prove the result by the minimal positive linear combination argument. Among all positive integers of the form $xa + yb$ with $x, y \in \mathbb{Z}$, choose the least one, call it $h$, and show that $h$ divides both $a$ and $b$ by the division algorithm. Then every common divisor of $a$ and $b$ divides $h$, so $h$ is exactly $\gcd(a,b)$. [/proofplan] [step:Choose the least positive integer linear combination of $a$ and $b$] Since $a,b \in \mathbb{N}$, the integer $a$ is positive. Define the set $S \subset \mathbb{N}$ by \begin{align*} S := \{xa + yb \in \mathbb{N} : x,y \in \mathbb{Z}\}. \end{align*} The set $S$ is nonempty because $a = 1 \cdot a + 0 \cdot b \in S$. By the [Well-Ordering Principle](/theorems/721), there exists a least element $h \in S$. Since $h \in S$, choose integers $x_0,y_0 \in \mathbb{Z}$ such that \begin{align*} h = x_0a + y_0b. \end{align*} [guided] We want a linear combination of $a$ and $b$ that is forced to have divisibility properties. The standard way to force this is to choose the smallest positive linear combination. Define \begin{align*} S := \{xa + yb \in \mathbb{N} : x,y \in \mathbb{Z}\}. \end{align*} This is the set of all positive integers that can be written as an integer linear combination of $a$ and $b$. It is nonempty because $a \in \mathbb{N}$ and \begin{align*} a = 1 \cdot a + 0 \cdot b. \end{align*} Thus $a \in S$. Since $S$ is a nonempty subset of $\mathbb{N}$, the Well-Ordering Principle gives a least element $h \in S$. By the definition of $S$, there exist integers $x_0,y_0 \in \mathbb{Z}$ such that \begin{align*} h = x_0a + y_0b. \end{align*} [/guided] [/step] [step:Prove that the least positive linear combination divides both inputs] [claim:$h$ divides both $a$ and $b$] The integer $h$ divides $a$ and $h$ divides $b$. [/claim] [proof] Suppose first that $h \nmid a$. By the [Division Algorithm](/theorems/725), applied to the positive integers $a$ and $h$, there exist integers $q,r \in \mathbb{Z}$ such that \begin{align*} a = qh + r, \qquad 0 < r < h. \end{align*} Using $h = x_0a + y_0b$, we compute \begin{align*} r &= a - qh \\ &= a - q(x_0a + y_0b) \\ &= (1 - qx_0)a + (-qy_0)b. \end{align*} Thus $r \in S$. But $0 < r < h$, contradicting the choice of $h$ as the least element of $S$. Therefore $h \mid a$. The same argument applied to $b$ gives $h \mid b$: if $h \nmid b$, the division algorithm gives integers $q',r' \in \mathbb{Z}$ with \begin{align*} b = q'h + r', \qquad 0 < r' < h, \end{align*} and then \begin{align*} r' &= b - q'h \\ &= b - q'(x_0a + y_0b) \\ &= (-q'x_0)a + (1 - q'y_0)b, \end{align*} so $r' \in S$ with $0 < r' < h$, again contradicting minimality. Hence $h \mid b$. [/proof] [guided] We prove that $h$ divides $a$; the proof for $b$ is the same calculation with $a$ replaced by $b$. Assume for contradiction that $h \nmid a$. Since $a$ and $h$ are positive integers, the division algorithm applies and gives integers $q,r \in \mathbb{Z}$ such that \begin{align*} a = qh + r, \qquad 0 < r < h. \end{align*} The remainder $r$ is positive and smaller than $h$. We now show that it is also an integer linear combination of $a$ and $b$, which would contradict the definition of $h$. Using the chosen representation $h = x_0a + y_0b$, we have \begin{align*} r &= a - qh \\ &= a - q(x_0a + y_0b) \\ &= (1 - qx_0)a + (-qy_0)b. \end{align*} Because $q,x_0,y_0 \in \mathbb{Z}$, the coefficients $1 - qx_0$ and $-qy_0$ are integers. Hence $r \in S$. But $0 < r < h$, contradicting that $h$ is the least element of $S$. Therefore $h \mid a$. The proof that $h \mid b$ is identical in structure. If $h \nmid b$, then the division algorithm gives integers $q',r' \in \mathbb{Z}$ with \begin{align*} b = q'h + r', \qquad 0 < r' < h. \end{align*} Substituting $h = x_0a + y_0b$ gives \begin{align*} r' &= b - q'h \\ &= b - q'(x_0a + y_0b) \\ &= (-q'x_0)a + (1 - q'y_0)b. \end{align*} Thus $r' \in S$ and $0 < r' < h$, again contradicting the minimality of $h$. Therefore $h \mid b$. [/guided] [/step] [step:Show that every common divisor of $a$ and $b$ divides $h$] Let $d \in \mathbb{N}$ be a common divisor of $a$ and $b$. Then there exist integers $\alpha,\beta \in \mathbb{Z}$ such that \begin{align*} a = d\alpha, \qquad b = d\beta. \end{align*} Using $h = x_0a + y_0b$, we obtain \begin{align*} h &= x_0a + y_0b \\ &= x_0d\alpha + y_0d\beta \\ &= d(x_0\alpha + y_0\beta). \end{align*} Since $x_0\alpha + y_0\beta \in \mathbb{Z}$, this proves $d \mid h$. [/step] [step:Identify the least positive linear combination with the [greatest common divisor](/wiki/greatest-common-divisor)] By the previous step, $h$ divides both $a$ and $b$, so $h$ is a common divisor of $a$ and $b$. Also, every positive common divisor of $a$ and $b$ divides $h$. Therefore $h$ satisfies the defining property of $\gcd(a,b)$, and hence \begin{align*} h = \gcd(a,b). \end{align*} Since $h = x_0a + y_0b$ with $x_0,y_0 \in \mathbb{Z}$, there exist integers $x,y \in \mathbb{Z}$, namely $x := x_0$ and $y := y_0$, such that \begin{align*} xa + yb = \gcd(a,b). \end{align*} [/step]