[proofplan] We encode [Euclid's algorithm](/page/Euclidean%20Algorithm) as a finite remainder chain whose last non-zero term is the algorithm output. The central point is that each division identity $s_{k-1} = q_k s_k + s_{k+1}$ preserves the set of common positive divisors of the adjacent pair. Iterating this preservation shows that the common divisors of $a$ and $b$ are exactly the divisors of the final non-zero remainder, which is precisely the defining property of $\gcd(a,b)$. [/proofplan] [step:Construct the finite chain of Euclidean remainders] Let $s_0 := a$ and $s_1 := b$. Since $a,b \in \mathbb{N}$ and $a > b$, both $s_0$ and $s_1$ are positive integers. Applying the [Division Algorithm](/theorems/725) recursively, Euclid's algorithm produces integers $q_k \in \mathbb{N}$ and remainders $s_{k+1} \in \mathbb{N} \cup \{0\}$ such that \begin{align*} s_{k-1} &= q_k s_k + s_{k+1}, \qquad 0 \le s_{k+1} < s_k, \end{align*} for each stage $k$ for which $s_k \neq 0$. The positive remainders strictly decrease: \begin{align*} s_1 > s_2 > \cdots > s_m > s_{m+1} = 0 \end{align*} for some integer $m \ge 1$. Indeed, if the algorithm never reached a zero remainder, then the positive remainders would form an infinite strictly decreasing sequence in $\mathbb{N}$, contradicting the [Well-Ordering Principle](/theorems/721). Euclid's algorithm outputs $s_m$, the last non-zero remainder. [guided] Define the first two terms of the remainder chain by $s_0 := a$ and $s_1 := b$. The hypotheses $a,b \in \mathbb{N}$ and $a > b$ ensure that $s_0$ and $s_1$ are positive integers, with $s_1 < s_0$. At any stage where the current divisor $s_k$ is non-zero, the Division Algorithm applies to the positive integers $s_{k-1}$ and $s_k$. It gives a quotient $q_k \in \mathbb{N}$ and a remainder $s_{k+1} \in \mathbb{N} \cup \{0\}$ satisfying \begin{align*} s_{k-1} &= q_k s_k + s_{k+1}, \qquad 0 \le s_{k+1} < s_k. \end{align*} The inequality $0 \le s_{k+1} < s_k$ is the termination mechanism. As long as the remainder is non-zero, the positive integers \begin{align*} s_1, s_2, s_3, \ldots \end{align*} strictly decrease. A strictly decreasing sequence of positive integers cannot continue indefinitely, by the [Well-Ordering Principle](/theorems/721): otherwise the set of its values would have a least element, but the next term of the sequence would be a smaller positive integer in the same set. Therefore there is an integer $m \ge 1$ such that \begin{align*} s_1 > s_2 > \cdots > s_m > s_{m+1} = 0. \end{align*} The algorithm stops at this first zero remainder and outputs the previous term $s_m$, the last non-zero remainder. [/guided] [/step] [step:Prove that each Euclidean division preserves common divisors] For $x \in \mathbb{N}$ and $y \in \mathbb{N} \cup \{0\}$, define the common-divisor set \begin{align*} C(x,y) := \{d \in \mathbb{N} : d \mid x \text{ and } d \mid y\}. \end{align*} Fix an index $k \in \{1,\ldots,m\}$. Since \begin{align*} s_{k-1} &= q_k s_k + s_{k+1}, \end{align*} we have \begin{align*} C(s_{k-1},s_k) = C(s_k,s_{k+1}). \end{align*} Indeed, if $d \in C(s_{k-1},s_k)$, then $d \mid s_{k-1}$ and $d \mid q_k s_k$, so $d \mid s_{k-1} - q_k s_k = s_{k+1}$; hence $d \in C(s_k,s_{k+1})$. Conversely, if $d \in C(s_k,s_{k+1})$, then $d \mid q_k s_k$ and $d \mid s_{k+1}$, so $d \mid q_k s_k + s_{k+1} = s_{k-1}$; hence $d \in C(s_{k-1},s_k)$. [guided] For $x \in \mathbb{N}$ and $y \in \mathbb{N} \cup \{0\}$, define \begin{align*} C(x,y) := \{d \in \mathbb{N} : d \mid x \text{ and } d \mid y\}. \end{align*} This set records exactly the positive common divisors of $x$ and $y$, and it is also defined when the second argument is $0$, as occurs at the last step of the algorithm. We prove that one line of Euclid's algorithm does not change this set of possible divisors. Fix $k \in \{1,\ldots,m\}$. The $k$-th division identity is \begin{align*} s_{k-1} &= q_k s_k + s_{k+1}. \end{align*} First suppose $d \in C(s_{k-1},s_k)$. Then $d \mid s_{k-1}$ and $d \mid s_k$. Since divisibility is preserved under multiplication by an integer, $d \mid q_k s_k$. Since divisibility is preserved under subtraction of two multiples of $d$, we get \begin{align*} d \mid s_{k-1} - q_k s_k = s_{k+1}. \end{align*} Together with $d \mid s_k$, this gives $d \in C(s_k,s_{k+1})$. Conversely, suppose $d \in C(s_k,s_{k+1})$. Then $d \mid s_k$ and $d \mid s_{k+1}$. Hence $d \mid q_k s_k$, and divisibility is preserved under addition of two multiples of $d$, so \begin{align*} d \mid q_k s_k + s_{k+1} = s_{k-1}. \end{align*} Together with $d \mid s_k$, this gives $d \in C(s_{k-1},s_k)$. Therefore \begin{align*} C(s_{k-1},s_k) = C(s_k,s_{k+1}). \end{align*} The reason this identity is the key point is that it lets us move through the algorithm without losing or gaining any common divisors. [/guided] [/step] [step:Iterate divisor preservation until the last non-zero remainder] Applying the previous step for $k = 1,2,\ldots,m$ gives \begin{align*} C(a,b) &= C(s_0,s_1) \\ &= C(s_1,s_2) \\ &= \cdots \\ &= C(s_m,s_{m+1}) \\ &= C(s_m,0). \end{align*} Since $s_m \in \mathbb{N}$, a positive integer $d$ divides both $s_m$ and $0$ exactly when $d \mid s_m$. Therefore \begin{align*} C(a,b) = \{d \in \mathbb{N} : d \mid s_m\}. \end{align*} [/step] [step:Conclude that the output satisfies the defining property of the greatest common divisor] The equality \begin{align*} C(a,b) = \{d \in \mathbb{N} : d \mid s_m\} \end{align*} has two consequences. First, $s_m \in C(a,b)$, so $s_m \mid a$ and $s_m \mid b$. Second, if $d \in \mathbb{N}$ satisfies $d \mid a$ and $d \mid b$, then $d \in C(a,b)$, hence $d \mid s_m$. Thus $s_m$ is a positive common divisor of $a$ and $b$ divisible by every positive common divisor of $a$ and $b$. By the defining property of the [greatest common divisor](/page/Greatest%20Common%20Divisor), \begin{align*} s_m = \gcd(a,b). \end{align*} Since Euclid's algorithm outputs $s_m$, the output of Euclid's algorithm applied to $a$ and $b$ is $\gcd(a,b)$. [/step]