[proofplan] We consider the positive integers that occur as integer linear combinations of $a$ and $b$, and choose the least such integer $d$. The key point is to show that $d$ divides both $a$ and $b$: if division by $d$ left a nonzero remainder, that remainder would be a smaller positive integer linear combination of $a$ and $b$, contradicting the choice of $d$. Once $d$ is known to be a common divisor, every common divisor of $a$ and $b$ divides every integer linear combination of them, hence divides $d$; this identifies $d$ with $\gcd(a,b)$. [/proofplan] [step:Choose the least positive integer linear combination] Define the set \begin{align*} S := \{ma + nb \in \mathbb{Z} : m,n \in \mathbb{Z},\ ma + nb > 0\}. \end{align*} Since $(a,b) \neq (0,0)$, at least one of $a$ and $b$ is nonzero. If $a \neq 0$, then either $a$ or $-a$ belongs to $S$; if $b \neq 0$, then either $b$ or $-b$ belongs to $S$. Hence $S$ is a nonempty subset of the positive integers. By the well-ordering property of the positive integers, $S$ has a least element. Let $d \in S$ denote this least element. By the definition of $S$, there exist integers $u_0,v_0 \in \mathbb{Z}$ such that \begin{align*} d = u_0a + v_0b. \end{align*} [guided] We want to find a positive integer linear combination of $a$ and $b$ that is as small as possible. Define \begin{align*} S := \{ma + nb \in \mathbb{Z} : m,n \in \mathbb{Z},\ ma + nb > 0\}. \end{align*} This set consists exactly of the positive integers representable in the form $ma+nb$ with integer coefficients. We verify that $S$ is nonempty. Since $(a,b) \neq (0,0)$, at least one of $a$ and $b$ is nonzero. If $a \neq 0$, then one of $a$ and $-a$ is positive, and both are integer linear combinations of $a$ and $b$: \begin{align*} a = 1\cdot a + 0\cdot b, \qquad -a = (-1)\cdot a + 0\cdot b. \end{align*} Thus $S$ is nonempty in this case. The same argument using \begin{align*} b = 0\cdot a + 1\cdot b, \qquad -b = 0\cdot a + (-1)\cdot b \end{align*} handles the case $b \neq 0$. Therefore $S$ is a nonempty subset of the positive integers. By the well-ordering property, $S$ has a least element. We call this least element $d$. Since $d \in S$, the definition of $S$ gives integers $u_0,v_0 \in \mathbb{Z}$ satisfying \begin{align*} d = u_0a + v_0b. \end{align*} This is the candidate that will become $\gcd(a,b)$. [/guided] [/step] [step:Show that the least positive combination divides both integers] We first show that $d \mid a$. Apply integer division of $a$ by the positive integer $d$: there exist $q,r \in \mathbb{Z}$ such that \begin{align*} a = qd + r, \qquad 0 \le r < d. \end{align*} Substituting $d = u_0a + v_0b$ gives \begin{align*} r &= a - qd \\ &= a - q(u_0a + v_0b) \\ &= (1-qu_0)a + (-qv_0)b. \end{align*} Thus $r$ is an integer linear combination of $a$ and $b$. If $r>0$, then $r \in S$, while $r<d$, contradicting the minimality of $d$. Therefore $r=0$, so $a=qd$ and $d \mid a$. The same argument applied to $b$ gives integers $q',r' \in \mathbb{Z}$ such that \begin{align*} b = q'd + r', \qquad 0 \le r' < d. \end{align*} Since \begin{align*} r' &= b - q'd \\ &= b - q'(u_0a + v_0b) \\ &= (-q'u_0)a + (1-q'v_0)b, \end{align*} the remainder $r'$ is an integer linear combination of $a$ and $b$. Minimality of $d$ again forces $r'=0$. Hence $d \mid b$. Thus $d$ is a positive common divisor of $a$ and $b$. [guided] The essential point is that division by $d$ cannot leave a positive remainder, because such a remainder would be a smaller positive integer linear combination of $a$ and $b$. First divide $a$ by the positive integer $d$. There exist integers $q,r \in \mathbb{Z}$ such that \begin{align*} a = qd + r, \qquad 0 \le r < d. \end{align*} We already know that $d$ has the form \begin{align*} d = u_0a + v_0b \end{align*} for some $u_0,v_0 \in \mathbb{Z}$. Substituting this expression into the formula for the remainder gives \begin{align*} r &= a - qd \\ &= a - q(u_0a + v_0b) \\ &= (1-qu_0)a + (-qv_0)b. \end{align*} Because $1-qu_0$ and $-qv_0$ are integers, this shows that $r$ is an integer linear combination of $a$ and $b$. Now use the defining minimality of $d$. If $r>0$, then $r$ belongs to $S$. But the division inequality gives $r<d$, contradicting that $d$ is the least element of $S$. Hence $r=0$. Therefore \begin{align*} a = qd, \end{align*} so $d \mid a$. The same argument works for $b$. Divide $b$ by $d$: there are integers $q',r' \in \mathbb{Z}$ with \begin{align*} b = q'd + r', \qquad 0 \le r' < d. \end{align*} Using $d = u_0a + v_0b$, we compute \begin{align*} r' &= b - q'd \\ &= b - q'(u_0a + v_0b) \\ &= (-q'u_0)a + (1-q'v_0)b. \end{align*} Thus $r'$ is also an integer linear combination of $a$ and $b$. If $r'>0$, then $r' \in S$ and $r'<d$, again contradicting the minimality of $d$. Therefore $r'=0$, so \begin{align*} b = q'd, \end{align*} and $d \mid b$. We have proved that $d$ is positive and divides both $a$ and $b$, so $d$ is a positive common divisor of $a$ and $b$. [/guided] [/step] [step:Identify the least positive combination with the greatest common divisor] Let $c \in \mathbb{Z}$ be any common divisor of $a$ and $b$. Then there exist $\alpha,\beta \in \mathbb{Z}$ such that \begin{align*} a = c\alpha, \qquad b = c\beta. \end{align*} Using $d = u_0a + v_0b$, we obtain \begin{align*} d &= u_0a + v_0b \\ &= u_0c\alpha + v_0c\beta \\ &= c(u_0\alpha + v_0\beta). \end{align*} Hence $c \mid d$. Since $d$ is a positive common divisor of $a$ and $b$, and every common divisor of $a$ and $b$ divides $d$, the positive greatest common divisor is $d$. Therefore \begin{align*} \gcd(a,b) = d = u_0a + v_0b. \end{align*} Taking $u := u_0$ and $v := v_0$ gives the desired integers. [guided] We have shown that $d$ is a common divisor. To prove that it is the greatest common divisor, we must show that no common divisor is larger in the divisibility sense. Let $c \in \mathbb{Z}$ be any common divisor of $a$ and $b$. By definition of divisibility, there are integers $\alpha,\beta \in \mathbb{Z}$ such that \begin{align*} a = c\alpha, \qquad b = c\beta. \end{align*} Because $d$ is an integer linear combination of $a$ and $b$, we substitute these two formulas: \begin{align*} d &= u_0a + v_0b \\ &= u_0c\alpha + v_0c\beta \\ &= c(u_0\alpha + v_0\beta). \end{align*} Since $u_0\alpha + v_0\beta \in \mathbb{Z}$, this proves $c \mid d$. Thus every common divisor of $a$ and $b$ divides $d$. Since $d$ is itself a positive common divisor of $a$ and $b$, $d$ is exactly the positive greatest common divisor: \begin{align*} \gcd(a,b) = d. \end{align*} Combining this with the representation chosen earlier gives \begin{align*} \gcd(a,b) = d = u_0a + v_0b. \end{align*} Therefore the required Bézout coefficients are $u := u_0$ and $v := v_0$. [/guided] [/step] [step:Derive the coprime characterization] If $\gcd(a,b)=1$, the first part gives integers $u,v \in \mathbb{Z}$ such that \begin{align*} ua + vb = \gcd(a,b) = 1. \end{align*} Conversely, suppose there exist $u,v \in \mathbb{Z}$ such that \begin{align*} ua + vb = 1. \end{align*} Since $\gcd(a,b)$ divides both $a$ and $b$, it divides the integer linear combination $ua+vb$. Hence $\gcd(a,b) \mid 1$. Because $\gcd(a,b)$ is positive, this implies \begin{align*} \gcd(a,b)=1. \end{align*} This proves the equivalence. [/step]