[proofplan]
The proof has two parts, corresponding to the two assertions in the theorem. First, we show the algorithm terminates by exhibiting a strictly decreasing sequence of non-negative integers — the remainders. Second, we show the final non-zero remainder equals $\gcd(a, b)$ by proving the gcd is preserved at each division step: the identity $r_j = r_{j-2} - q_j r_{j-1}$ implies $\gcd(r_{j-2}, r_{j-1}) = \gcd(r_{j-1}, r_j)$, and iterating this from the initial pair $(a, b)$ down to the terminating pair $(r_{k-1}, r_k)$ telescopes to $\gcd(a, b) = r_k$.
[/proofplan]
[step:Set up the recursion and show it terminates in finitely many steps]
Write $r_{-1} := a$ and $r_0 := b$, so the division algorithm produces the recursion
\begin{align*}
r_{j-2} &= q_j\, r_{j-1} + r_j, & 0 &\leq r_j < r_{j-1}, \qquad j = 1, 2, 3, \dots,
\end{align*}
continuing as long as $r_{j-1} > 0$. The constraint $0 \leq r_j < r_{j-1}$ forces
\begin{align*}
b = r_0 > r_1 > r_2 > \cdots \geq 0.
\end{align*}
The sequence $(r_j)_{j \geq 0}$ is a strictly decreasing sequence in $\mathbb{N} \cup \{0\}$, which is well-ordered. It must therefore reach $0$ in at most $r_0 = b$ steps. Let $k \geq 0$ be the largest index with $r_k > 0$; then $r_{k+1} = 0$, and the algorithm terminates at this step with final division
\begin{align*}
r_{k-1} &= q_{k+1}\, r_k + 0.
\end{align*}
[guided]
The question is whether the recursion ever halts. Writing $r_{-1} := a$ and $r_0 := b$ to unify notation, the division algorithm produces
\begin{align*}
r_{j-2} &= q_j\, r_{j-1} + r_j, & 0 &\leq r_j < r_{j-1}, \qquad j = 1, 2, 3, \dots.
\end{align*}
The key structural feature is the strict inequality $r_j < r_{j-1}$, enforced by the division algorithm's requirement that the remainder be strictly smaller than the divisor. This gives
\begin{align*}
b = r_0 > r_1 > r_2 > \cdots \geq 0.
\end{align*}
Why must this sequence hit $0$? The values $r_j$ lie in the set $\{0, 1, 2, \dots, b\}$, which is finite, and the sequence is strictly decreasing — so it cannot continue forever without revisiting a value. More formally, $\mathbb{N} \cup \{0\}$ is well-ordered: every non-empty subset has a least element. A strictly decreasing sequence of non-negative integers can have at most $b + 1$ terms before it must hit $0$.
Let $k \geq 0$ be the largest index for which $r_k > 0$. Then $r_{k+1} = 0$ and the last division step reads
\begin{align*}
r_{k-1} &= q_{k+1}\, r_k + 0,
\end{align*}
which confirms that $r_k$ divides $r_{k-1}$ exactly. The algorithm halts at step $k+1$.
[/guided]
[/step]
[step:Prove the invariant $\gcd(r_{j-2}, r_{j-1}) = \gcd(r_{j-1}, r_j)$ at each division step]
Fix $j$ with $1 \leq j \leq k$ and consider the $j$-th division
\begin{align*}
r_{j-2} &= q_j\, r_{j-1} + r_j.
\end{align*}
We show the set of common divisors of $(r_{j-2}, r_{j-1})$ equals the set of common divisors of $(r_{j-1}, r_j)$, which forces the equality of gcds.
Let $d \in \mathbb{Z}$ with $d \mid r_{j-2}$ and $d \mid r_{j-1}$. Since divisibility is closed under integer linear combinations, $d \mid (r_{j-2} - q_j r_{j-1}) = r_j$. Conversely, let $d \mid r_{j-1}$ and $d \mid r_j$; then $d \mid (q_j r_{j-1} + r_j) = r_{j-2}$. Hence the common divisors agree, and in particular the greatest common divisor agrees:
\begin{align*}
\gcd(r_{j-2}, r_{j-1}) &= \gcd(r_{j-1}, r_j).
\end{align*}
[guided]
We want to show the gcd is preserved at each step of the recursion. Fix $j$ with $1 \leq j \leq k$ and consider the $j$-th division
\begin{align*}
r_{j-2} &= q_j\, r_{j-1} + r_j.
\end{align*}
The strategy is to show the underlying sets of common divisors are identical; the gcd, being the largest element of this set, is then automatically preserved.
Suppose $d \in \mathbb{Z}$ is a common divisor of $r_{j-2}$ and $r_{j-1}$, meaning $d \mid r_{j-2}$ and $d \mid r_{j-1}$. Rewriting the division equation as
\begin{align*}
r_j &= r_{j-2} - q_j r_{j-1},
\end{align*}
we see $r_j$ is an integer linear combination of $r_{j-2}$ and $r_{j-1}$. Since $d$ divides both summands, $d \mid r_j$. Thus $d$ is a common divisor of $r_{j-1}$ and $r_j$.
Conversely, suppose $d$ is a common divisor of $r_{j-1}$ and $r_j$. The division equation in the original form,
\begin{align*}
r_{j-2} &= q_j r_{j-1} + r_j,
\end{align*}
expresses $r_{j-2}$ as an integer linear combination of $r_{j-1}$ and $r_j$, so $d \mid r_{j-2}$. Hence $d$ is a common divisor of $r_{j-2}$ and $r_{j-1}$.
The two sets of common divisors are therefore equal, and their greatest element — the gcd — is the same:
\begin{align*}
\gcd(r_{j-2}, r_{j-1}) &= \gcd(r_{j-1}, r_j).
\end{align*}
[/guided]
[/step]
[step:Telescope the invariant from $(a,b)$ down to $(r_{k-1}, r_k)$ and evaluate at termination]
Applying Step 2 successively for $j = 1, 2, \dots, k$,
\begin{align*}
\gcd(a, b) = \gcd(r_{-1}, r_0) = \gcd(r_0, r_1) = \gcd(r_1, r_2) = \cdots = \gcd(r_{k-1}, r_k).
\end{align*}
The terminating equation $r_{k-1} = q_{k+1}\, r_k$ from Step 1 shows $r_k \mid r_{k-1}$, so the common divisors of $r_{k-1}$ and $r_k$ are exactly the divisors of $r_k$. The greatest such divisor is $r_k$ itself:
\begin{align*}
\gcd(r_{k-1}, r_k) &= r_k.
\end{align*}
Combining, $\gcd(a, b) = r_k$, as claimed. This completes the proof that Euclid's algorithm terminates and returns the greatest common divisor of $a$ and $b$.
[/step]
