[proofplan] We give the extended Euclidean algorithm with coefficients attached to every remainder. The coefficient invariant says that each remainder is an integer linear combination of the original inputs $a$ and $b$. Euclidean division makes the positive remainders strictly decrease, so the algorithm terminates, and the final non-zero remainder is shown by back-substitution to divide both original inputs. Finally, every common divisor of $a$ and $b$ divides every integer linear combination of them, hence divides the final remainder. [/proofplan] [step:Handle the cases where one input is zero] Suppose first that $b = 0$. Since $(a,b)$ is not $(0,0)$, we have $a \neq 0$. Define $g := |a|$, set $u := 1$ if $a > 0$ and $u := -1$ if $a < 0$, and set $v := 0$. Then $g > 0$ and $ua + vb = ua = |a| = g$. Also $g \mid a$ and $g \mid 0 = b$. If $d \in \mathbb{Z}$ satisfies $d \mid a$ and $d \mid b$, then $d \mid a$, hence $d \mid |a| = g$. The case $a = 0$ and $b \neq 0$ is identical: define $g := |b|$, set $u := 0$, and set $v := 1$ if $b > 0$ and $v := -1$ if $b < 0$. Then $g > 0$, $ua + vb = |b| = g$, and every common divisor of $a$ and $b$ divides $g$. Thus it remains to treat the case $a \neq 0$ and $b \neq 0$. [/step] [step:Initialize signed positive remainders with Bézout coefficient pairs] Assume $a \neq 0$ and $b \neq 0$. Define signs $\varepsilon_a,\varepsilon_b \in \{-1,1\}$ by setting $\varepsilon_a = 1$ if $a > 0$ and $\varepsilon_a = -1$ if $a < 0$, and setting $\varepsilon_b = 1$ if $b > 0$ and $\varepsilon_b = -1$ if $b < 0$. Define the initial remainders $r_0,r_1 \in \mathbb{Z}$ and coefficient pairs $(s_0,t_0),(s_1,t_1) \in \mathbb{Z}^2$ by \begin{align*} r_0 := |a|. \end{align*} \begin{align*} r_1 := |b|. \end{align*} \begin{align*} (s_0,t_0) := (\varepsilon_a,0). \end{align*} \begin{align*} (s_1,t_1) := (0,\varepsilon_b). \end{align*} Then $r_0 > 0$, $r_1 > 0$, and the initial Bézout identities are \begin{align*} r_0 = s_0 a + t_0 b. \end{align*} \begin{align*} r_1 = s_1 a + t_1 b. \end{align*} [/step] [step:Run Euclidean division while preserving the coefficient invariant] For $k \geq 1$, as long as $r_k \neq 0$, we have $r_k > 0$ by the construction of the remainders. Therefore the Euclidean division theorem for integers applies to the dividend $r_{k-1}$ and the positive divisor $r_k$: choose integers $q_k,r_{k+1} \in \mathbb{Z}$ such that \begin{align*} r_{k-1} = q_k r_k + r_{k+1}. \end{align*} \begin{align*} 0 \leq r_{k+1} < r_k. \end{align*} Define the next coefficient pair $(s_{k+1},t_{k+1}) \in \mathbb{Z}^2$ by \begin{align*} s_{k+1} := s_{k-1} - q_k s_k. \end{align*} \begin{align*} t_{k+1} := t_{k-1} - q_k t_k. \end{align*} If $r_{k-1} = s_{k-1}a + t_{k-1}b$ and $r_k = s_k a + t_k b$, then \begin{align*} r_{k+1} = r_{k-1} - q_k r_k = (s_{k-1} - q_k s_k)a + (t_{k-1} - q_k t_k)b = s_{k+1}a + t_{k+1}b. \end{align*} Therefore, by induction on $k$, every generated remainder satisfies \begin{align*} r_j = s_j a + t_j b \end{align*} for its corresponding coefficient pair $(s_j,t_j) \in \mathbb{Z}^2$. [guided] At each stage we keep two pieces of information: the current remainder $r_j$ and a certificate that $r_j$ is built from the original inputs $a$ and $b$. That certificate is the pair $(s_j,t_j) \in \mathbb{Z}^2$, and the invariant is \begin{align*} r_j = s_j a + t_j b. \end{align*} The initialization gives this invariant for $j = 0$ and $j = 1$ because \begin{align*} r_0 = |a| = \varepsilon_a a = s_0a + t_0b \end{align*} and \begin{align*} r_1 = |b| = \varepsilon_b b = s_1a + t_1b. \end{align*} Now suppose the invariant is known for $r_{k-1}$ and $r_k$. Since the loop continues only when $r_k \neq 0$, and since generated remainders are non-negative, we have $r_k > 0$. The Euclidean division theorem for integers therefore gives integers $q_k$ and $r_{k+1}$ satisfying \begin{align*} r_{k-1} = q_k r_k + r_{k+1}. \end{align*} \begin{align*} 0 \leq r_{k+1} < r_k. \end{align*} Rearranging the division identity gives \begin{align*} r_{k+1} = r_{k-1} - q_k r_k. \end{align*} Substituting the two known Bézout expressions into the right-hand side gives \begin{align*} r_{k+1} = (s_{k-1}a + t_{k-1}b) - q_k(s_ka + t_kb). \end{align*} Collecting the coefficients of $a$ and $b$ gives \begin{align*} r_{k+1} = (s_{k-1} - q_k s_k)a + (t_{k-1} - q_k t_k)b. \end{align*} This is exactly why the algorithm defines \begin{align*} s_{k+1} := s_{k-1} - q_k s_k. \end{align*} \begin{align*} t_{k+1} := t_{k-1} - q_k t_k. \end{align*} Thus the new remainder also has a Bézout certificate. Since the update uses only integer addition and multiplication, the new coefficients remain integers. [/guided] [/step] [step:Use decreasing positive remainders to prove termination] Whenever the algorithm continues from index $k$, the next remainder satisfies \begin{align*} 0 \leq r_{k+1} < r_k. \end{align*} Thus the positive remainders form a strictly decreasing sequence of non-negative integers until a zero remainder occurs. A strictly decreasing sequence of non-negative integers cannot be infinite by the [well-ordering principle](/theorems/721) for the set of non-negative integers. Hence there exists an index $N \geq 1$ such that \begin{align*} r_N > 0. \end{align*} \begin{align*} r_{N+1} = 0. \end{align*} [/step] [step:Show the final non-zero remainder divides both original inputs] Let $g := r_N$, $u := s_N$, and $v := t_N$. Then $g > 0$, and the coefficient invariant gives \begin{align*} g = r_N = s_Na + t_Nb = ua + vb. \end{align*} Since $r_{N+1} = 0$, the last division identity is \begin{align*} r_{N-1} = q_N r_N. \end{align*} Thus $r_N \mid r_{N-1}$. Now move backward through the division identities. If $r_N$ divides both $r_k$ and $r_{k+1}$, then from \begin{align*} r_{k-1} = q_k r_k + r_{k+1} \end{align*} it follows that $r_N \mid r_{k-1}$. Backward induction gives $r_N \mid r_0$ and $r_N \mid r_1$. Since $r_0 = |a|$ and $r_1 = |b|$, we have $g \mid |a|$ and $g \mid |b|$. Therefore $g \mid a$ and $g \mid b$. [/step] [step:Show every common divisor divides the final remainder] Let $d \in \mathbb{Z}$ be any common divisor of $a$ and $b$. Then there exist integers $m,n \in \mathbb{Z}$ such that \begin{align*} a = dm, \qquad b = dn. \end{align*} Using the Bézout identity for $g$, we obtain \begin{align*} g = ua + vb = u(dm) + v(dn) = d(um + vn). \end{align*} Since $um + vn \in \mathbb{Z}$, this proves $d \mid g$. [/step] [step:Extract the finite algorithm and return the computed triple] The construction is algorithmic: first handle the two zero-input cases explicitly; otherwise compute $r_0,r_1,s_0,t_0,s_1,t_1$ from the signs of $a$ and $b$, repeatedly perform Euclidean division, and update the coefficient pair by \begin{align*} (s_{k+1},t_{k+1}) = (s_{k-1} - q_k s_k, t_{k-1} - q_k t_k). \end{align*} The termination step proves that this loop stops after finitely many iterations. When it stops, the algorithm returns \begin{align*} (g,u,v) := (r_N,s_N,t_N). \end{align*} The previous steps prove that this returned triple satisfies $g > 0$, $g \mid a$, $g \mid b$, every common divisor of $a$ and $b$ divides $g$, and $g = ua + vb$. This proves both the existence statement and the constructive algorithmic statement. [/step]