The Euclidean Algorithm

The Euclidean Algorithm is the computational backbone of elementary number theory and remains indispensable in modern computing. In cryptography, the Extended Euclidean Algorithm — a light extension of this procedure that also tracks Bezout coefficients — is used to compute modular inverses in RSA key generation and in elliptic-curve cryptography. In computer algebra systems, it underlies polynomial gcd computation (via an analogous algorithm on polynomials over a field), which in turn is essential for simplifying rational functions and factoring. In simplifying fractions, the algorithm reduces $a/b$ to lowest terms by dividing numerator and denominator by $\gcd(a,b)$. In the analysis of algorithms, it is the textbook example for proving termination via a strictly decreasing well-ordered quantity, and Lamé's theorem connecting its worst-case behavior to Fibonacci numbers is a classic result in complexity analysis. It also appears in continued fraction expansions: the sequence of quotients $q_1, q_2, \dots$ produced by the algorithm applied to $a$ and $b$ is exactly the continued fraction expansion of $a/b$, linking gcd computation to Diophantine approximation.

Ask the tutor: How does tracking coefficients through the Euclidean Algorithm's steps produce the Bezout coefficients $x, y$ with $ax+by=\gcd(a,b)$?

Think of $\gcd(a,b)$ as a shared "unit of measurement" for two lengths $a$ and $b$. If you lay the shorter length $b$ down along the longer length $a$ as many times as it fits, a leftover piece $r$ remains with $r < b$. Any ruler that measures both $a$ and $b$ exactly must also measure this leftover piece exactly — and conversely, any ruler measuring $b$ and $r$ exactly also measures $a$. So the pair $(a,b)$ and the pair $(b,r)$ have exactly the same common measuring-sticks, hence the same greatest one. This is the entire content of the algorithm: replace $(a,b)$ by the strictly smaller pair $(b,r)$, and repeat. Since remainders are nonnegative integers that strictly decrease at every step, the process cannot continue forever — it must hit a remainder of $0$, at which point the previous remainder is the answer. A second way to see it: picture the Euclidean algorithm as repeatedly subtracting the smaller number from the larger (division is just repeated subtraction done all at once). Geometrically, this is the ancient process of finding the largest square tile that exactly tiles an $a \times b$ rectangle — lay down $b\times b$ squares along the length $a$, leave a strip of width $r < b$, then tile that strip with squares of the next size down, and so on.

lemma[Invariance of gcd under division with remainder] If $a = qb + r$ for integers $a,b,q,r$ with $b \neq 0$, then

::: Proof of Lemma. Let $d = \gcd(a,b)$ and $d' = \gcd(b,r)$. (Both exist: $b\neq 0$ guarantees $\gcd(a,b)$ exists by definition of gcd; and since $b \neq 0$, $\gcd(b,r)$ exists as well, as $b$ alone is a nonzero common divisor candidate — more precisely, gcd of two integers not both zero always exists, and here $b \neq 0$.) We show $d \mid d'$'s defining set of common divisors matches, by showing the set of common divisors of $(a,b)$ equals the set of common divisors of $(b,r)$. ($\subseteq$) Suppose $c \mid a$ and $c \mid b$. Since $r = a - qb$, and $c$ divides both terms on the right (as $c\mid a$, and $c \mid b \Rightarrow c \mid qb$), it follows $c \mid r$. So $c$ is a common divisor of $b$ and $r$. ($\supseteq$) Suppose $c \mid b$ and $c \mid r$. Since $a = qb + r$, and $c$ divides both terms on the right, it follows $c \mid a$. So $c$ is a common divisor of $a$ and $b$. Thus the common divisors of $(a,b)$ are exactly the common divisors of $(b,r)$; in particular these two sets have the same maximum element, so $d = d'$. $\blacksquare$ (Lemma)

Step 1: Termination. Consider the sequence of remainders $r_0, r_1, r_2, \dots$ produced as long as they are defined (i.e. as long as the previous remainder is nonzero). By the Division Algorithm's conclusion applied at each step,

Hence, as long as no remainder in the sequence is zero, we get a strictly decreasing chain of nonnegative integers

(Here we use $r_1 < |r_0|$ from the first division, and thereafter $r_{k+1} < r_k$ since $r_k \ge 0$ for $k\ge 1$ so $|r_k| = r_k$.) A strictly decreasing sequence of nonnegative integers cannot be infinite: by the well-ordering principle, any nonempty set of nonnegative integers has a least element, and a strictly decreasing infinite sequence would produce a subset with no least element (take the sequence itself as the set — for any term, a later term is smaller), a contradiction. Therefore the sequence $r_1, r_2, r_3, \dots$ must reach $0$ after finitely many terms. Let $n+1$ be the first index with $r_{n+1} = 0$ (if $r_1 = 0$ already, then $n = 0$). This proves termination, establishing part 1.

Step 2: Correctness. We prove by induction on $k$, for $k = 0, 1, \dots, n$, the statement

Base case $k = 0$: $P(0)$ asserts $\gcd(r_{-1}, r_0) = \gcd(a,b)$, which is immediate since $r_{-1} = a, r_0 = b$ by definition. Inductive step: Suppose $P(k)$ holds for some $0 \le k < n$, i.e. $\gcd(r_{k-1}, r_k) = \gcd(a,b)$, and $r_k \neq 0$ (guaranteed since $k < n$ implies the division defining $r_{k+1}$ took place, requiring $r_k \neq 0$). By construction,

so applying the Lemma with $(a,b,q,r) = (r_{k-1}, r_k, q_{k+1}, r_{k+1})$ gives

Combined with the inductive hypothesis $\gcd(r_{k-1},r_k) = \gcd(a,b)$, we conclude

which is exactly $P(k+1)$. This completes the induction, valid for all $k$ from $0$ to $n$. In particular, $P(n)$ gives

Case $n = 0$: Then $P(0)$ directly gives $\gcd(a,b) = \gcd(r_{-1},r_0) = \gcd(a,b)$ trivially — but we want to identify this with $|b|$. Since $r_1 = 0$, by definition of gcd, $\gcd(b, 0) = |b|$ (as every integer divides $0$, so the common divisors of $b$ and $0$ are exactly the divisors of $b$, whose greatest element is $|b|$, assuming $b \neq 0$). And $P(0)$ says $\gcd(a,b) = \gcd(r_{-1},r_0) = \gcd(a,b)$ — to close the loop, note $n=0$ means $r_1 = 0$ was reached on the first division $a = q_1 b + r_1$, and the Lemma applied directly gives $\gcd(a,b) = \gcd(b, r_1) = \gcd(b,0) = |b|$. This matches the claimed output $|r_0| = |b|$. Case $n \ge 1$: Since $r_{n+1} = 0$ is the first zero remainder, we know $r_n \neq 0$ (else $n$ would not be the last valid index with a nonzero remainder producing a further division — more precisely $r_n \ne 0$ by minimality of $n+1$ as the first zero index, since $r_n$ is not zero as $n < n+1$). Now since $r_{n+1} = 0$, the same computation as above (Lemma applied to $r_{n-1} = q_{n+1} r_n + r_{n+1}$) gives

using $r_n \ge 0$ (indeed $r_n > 0$) from the Division Algorithm. Combining with $P(n)$: $\gcd(a,b) = \gcd(r_{n-1},r_n) = r_n$. This proves $\gcd(a,b) = r_n$, the last nonzero remainder, completing part 2 and the theorem. $\blacksquare$

Example 1: $\gcd(2024, 748)$. We apply the algorithm, dividing the larger by the smaller at each stage and tracking quotient and remainder explicitly.

The last nonzero remainder is $44$. By the theorem, $\gcd(2024, 748) = 44$. Check: $2024 = 44 \cdot 46$ and $748 = 44 \cdot 17$, and $\gcd(46,17)=1$ since $17$ is prime and does not divide $46$. So indeed $44$ is the greatest common divisor — consistent with the algorithm's output.

Example 2: $\gcd(-357, 1155)$, illustrating a negative input. Since $\gcd$ is typically defined via divisibility (which does not care about sign), we may take $a = -357$, $b = 1155$, or equivalently work with $\gcd(357, 1155)$ since the set of common divisors of $\{a,b\}$ is unaffected by replacing an argument with its absolute value (any $c \mid a \iff c \mid -a$). We proceed with $r_{-1} = 1155$, $r_0 = 357$ (ordering so the Division Algorithm applies cleanly with a positive divisor):

The last nonzero remainder is $21$, so $\gcd(357, 1155) = 21$, and hence $\gcd(-357, 1155) = 21$ as well. Check: $357 = 21 \cdot 17$ and $1155 = 21 \cdot 55$, with $\gcd(17, 55) = 1$ (since $17$ is prime and $17 \nmid 55$). This confirms $21$ is correct.