Divisibility and the Euclidean Algorithm

Divisibility and its basic laws, the greatest common divisor, and Euclid's method of finding it by repeated division, with proofs that it stops and that it is correct. Bezout's identity, that the gcd is a combination of the two numbers, proved through the extended Euclidean algorithm; the integer combinations of two numbers as the multiples of their gcd; relatively prime integers and cancellation; solving linear equations in integers; and Lamé's bound on the number of steps, with Fibonacci numbers as the worst case.

A rectangular floor measures 1729 by 1001 units, and it is to be covered by square tiles, all of the same size, with no cutting. What is the largest tile that works?

A square of side $s$ fits exactly along both edges when $s$ divides both 1729 and 1001. So the largest tile has side equal to the greatest common divisor of the two numbers. Listing divisors finds it:

  • divisors of 1729: 1, 7, 13, 19, 91, 133, 247, 1729;
  • divisors of 1001: 1, 7, 11, 13, 77, 91, 143, 1001.

The common divisors are 1, 7, 13 and 91, so the answer is 91. But listing divisors is hopeless for numbers with hundreds of digits, which are routine in cryptography. Euclid's method finds the same answer with five divisions. A small extension of it writes 91 as an integer combination of 1729 and 1001, and that turns out to matter as much as the answer itself.

First we set up divisibility and its laws, and define the greatest common divisor. Then we prove Euclid's key lemma and turn it into an algorithm that stops and is correct. Next we run the algorithm backwards to get Bezout's identity, and collect what it gives: cancellation, and every common divisor dividing the gcd. Finally we solve linear equations in integers and ask how fast the algorithm is.

This article builds on the division algorithm and covers §1.2 of the course text (Hungerford, 2014). It is the course's home for the gcd, Bezout's identity and linear equations in integers. The next article uses them to prove unique factorization into primes, and later units cite them for inverses modulo $n$ and for polynomials.

Divisibility

Definition. Let $a$ and $b$ be integers with $b \neq 0$. We say $b$ divides $a$, written $b \mid a$, if $a = bk$ for some integer $k$. Then $b$ is a divisor (or factor) of $a$, and $a$ is a multiple of $b$. If $b$ does not divide $a$, we write $b \nmid a$.

For example, $7 \mid 1729$ because $1729 = 7 \cdot 247$, and $11 \nmid 1729$ because dividing gives $1729 = 11 \cdot 157 + 2$, and by the uniqueness of the remainder no other quotient can leave remainder 0. In general, for $b > 0$, $b \mid a$ exactly when the remainder on dividing $a$ by $b$ is 0. Negative divisors are allowed: $-7 \mid 1729$ because $1729 = (-7)(-247)$. Some texts also allow $0 \mid 0$; the condition $b \neq 0$ here follows the course text and avoids having to treat that case separately.

The symbol $b \mid a$ is a statement, true or false, and not a number. It should not be confused with the fraction $b/a$. The statement $7 \mid 1729$ is true; the number $7/1729$ is about 0.004.

Each law comes from writing a divisibility statement as an equation, $b = ak$, and then multiplying, adding or comparing sizes.

Lemma (laws of divisibility). Let $a$, $b$ and $c$ be integers.

  1. If $a \neq 0$, then $a \mid a$, $a \mid 0$, $1 \mid a$ and $-a \mid a$. More generally, $b \mid a$ if and only if $-b \mid a$.
  2. If $a \mid b$ and $b \mid c$, then $a \mid c$.
  3. If $a \mid b$ and $a \mid c$, then $a \mid (bu + cv)$ for all integers $u$ and $v$.
  4. If $a \mid b$ and $b \neq 0$, then $\lvert a \rvert \le \lvert b \rvert$.
  5. If $a \mid b$ and $b \mid a$, then $a = \pm b$.

Proof. (1) $a = a \cdot 1$, $0 = a \cdot 0$, $a = 1 \cdot a$ and $a = (-a)(-1)$. If $a = bk$ then $a = (-b)(-k)$, and conversely. (2) Write $b = ak$ and $c = bm$. Then $c = a(km)$, and $km$ is an integer. (3) Write $b = ak$ and $c = am$. Then $bu + cv = a(ku + mv)$. (4) Write $b = ak$. Since $b \neq 0$, $k \neq 0$, so $\lvert k \rvert \ge 1$ and $\lvert b \rvert = \lvert a \rvert \lvert k \rvert \ge \lvert a \rvert$. (5) Both $a$ and $b$ are nonzero, since each is a divisor. By (4), $\lvert a \rvert \le \lvert b \rvert$ and $\lvert b \rvert \le \lvert a \rvert$, so $\lvert a \rvert = \lvert b \rvert$, which means $a = b$ or $a = -b$. $\blacksquare$

Law (3) is used more than any other. An integer of the form $bu + cv$ with $u, v \in \mathbb{Z}$ is called an (integer) linear combination of $b$ and $c$. The law says that a common divisor of two integers divides every linear combination of them. For instance, 7 divides 1729 and 1001, so it divides $1729 \cdot 2 - 1001 \cdot 3 = 455$, and indeed $455 = 7 \cdot 65$.

Check your understanding. Both 7 and 10 divide the sum $1729 + 1001 = 2730$. Does law (3) say that 7 divides 1729? That 10 does?

No to both: law (3) runs in one direction only. A divisor of the sum need not divide either number. Here 7 happens to divide both, while 10 divides neither, since they end in 9 and 1.

The greatest common divisor

Definition. Let $a$ and $b$ be integers, not both zero. The greatest common divisor of $a$ and $b$, written $\gcd(a, b)$, is the largest integer $d$ such that $d \mid a$ and $d \mid b$.

The course text writes $(a, b)$ for the same number. The definition makes sense: 1 is always a common divisor, and if, say, $a \neq 0$, every common divisor is at most $\lvert a \rvert$ by law (4). A nonempty set of integers bounded above has a largest element, so the greatest common divisor exists, and it is at least 1. Two immediate consequences of law (1) are used repeatedly. Since $a$ and $-a$ have the same divisors, $\gcd(a, b) = \gcd(\lvert a \rvert, \lvert b \rvert)$, so signs never matter. And if $a \neq 0$ then $\gcd(a, 0) = \lvert a \rvert$, because every divisor of $a$ divides 0, and the largest divisor of $a$ is $\lvert a \rvert$.

Integers $a$ and $b$ with $\gcd(a, b) = 1$ are relatively prime (or coprime). For example, $\gcd(19, 11) = 1$, and $\gcd(1729, 1001) = 91$, as the listing above showed. The definition says what the gcd is, but finding it from the definition means listing divisors. Can we avoid that?

Euclid's idea

Listing divisors works directly from the definition. Euclid's method instead replaces the pair of numbers by a smaller pair with the same common divisors, and repeats. It rests on one lemma.

Lemma. Let $a$, $b$, $q$ and $r$ be integers with $a = bq + r$. Then the common divisors of $a$ and $b$ are exactly the common divisors of $b$ and $r$. Consequently, if $b \neq 0$, then $\gcd(a, b) = \gcd(b, r)$.

The idea is that $r = a - bq$ and $a = bq + r$ are each linear combinations of the other pair, so law (3) carries every common divisor across in both directions.

Proof. Let $c$ be a common divisor of $a$ and $b$. Since $r = a \cdot 1 + b \cdot (-q)$ is a linear combination of $a$ and $b$, law (3) gives $c \mid r$, so $c$ is a common divisor of $b$ and $r$. Conversely, if $c$ divides $b$ and $r$, then $c$ divides the linear combination $a = b q + r \cdot 1$, so $c$ is a common divisor of $a$ and $b$. The two sets of common divisors are therefore equal. When $b \neq 0$, both greatest common divisors are defined, and as the largest elements of the same set they are equal. $\blacksquare$

The lemma holds for any $q$. It is most useful when $r$ is the remainder of $a$ on division by $b$, because then $0 \le r < b$ and the second pair is smaller than the first. For 1729 and 1001, the first division is $1729 = 1001 \cdot 1 + 728$, so $\gcd(1729, 1001) = \gcd(1001, 728)$, and the problem has shrunk. With $q = 2$ instead, $1729 = 1001 \cdot 2 + (-273)$, and the lemma still applies: $\gcd(1001, -273) = 91$ as well.

The Euclidean algorithm

Let $a \ge b > 0$. Set $r_0 = a$ and $r_1 = b$. As long as the latest remainder $r_i$ is not zero, divide the one before it by it:

$$r_{i-1} = r_i \, q_i + r_{i+1}, \qquad 0 \le r_{i+1} < r_i.$$

Stop at the first $i$ for which $r_{i+1} = 0$, and call that index $n$. The algorithm outputs $r_n$, the last nonzero remainder.

Theorem (Euclidean algorithm). The procedure stops after at most $b$ divisions, and its output $r_n$ equals $\gcd(a, b)$.

The idea in two sentences: the remainders keep shrinking, so they reach 0; and every division keeps the gcd, by the lemma. When the remainder reaches 0, the gcd of the last pair, $\gcd(r_n, 0)$, is plainly $r_n$.

Proof. Each remainder is strictly smaller than the one before it, so $b = r_1 > r_2 > r_3 > \cdots \ge 0$ is a strictly decreasing sequence of nonnegative integers. Such a sequence starting at $b$ has at most $b + 1$ terms, so some remainder is 0 after at most $b$ divisions, and the procedure stops. By the lemma, each division preserves the greatest common divisor, so

$$\gcd(a, b) = \gcd(r_0, r_1) = \gcd(r_1, r_2) = \cdots = \gcd(r_n, r_{n+1}) = \gcd(r_n, 0) = r_n. \qquad \blacksquare$$

The bound of $b$ divisions is very crude; the true number is far smaller, as the last section of this article shows. For any integers $a$ and $b$, not both zero, the algorithm applies after replacing them by their absolute values and putting the larger first. None of these changes affects the greatest common divisor. (If one of them is 0, the answer is the absolute value of the other with no division needed.)

Back to the floor. For 1729 and 1001:

$$\begin{aligned} 1729 &= 1001 \cdot 1 + 728, \\ 1001 &= 728 \cdot 1 + 273, \\ 728 &= 273 \cdot 2 + 182, \\ 273 &= 182 \cdot 1 + 91, \\ 182 &= 91 \cdot 2 + 0. \end{aligned}$$

The last nonzero remainder is 91, after five divisions. Every pair along the way, $(1729, 1001)$, $(1001, 728)$, $(728, 273)$, $(273, 182)$ and $(182, 91)$, has the same common divisors, 1, 7, 13 and 91, which the script for this article checks directly.

The algorithm has a geometric reading that matches the tiling problem. Cut the largest possible squares off a rectangle, and repeat on what is left. That performs exactly these divisions: the quotient says how many squares of each size fit, and the remainder is the width of the strip left over. The last square to be cut tiles everything before it.

The Euclidean algorithm on 1729 and 1001 as a rectangle cut into squares. One square of side 1001 leaves a 728 by 1001 strip, which takes one square of side 728; the remaining 728 by 273 strip takes two squares of side 273, and so on. Notice that the numbers of squares of each size (1, 1, 2, 1, 2) are the quotients, and that the smallest square, of side 91, fits exactly into every larger one: 91 is the greatest common divisor.
The Euclidean algorithm on 1729 and 1001 as a rectangle cut into squares. One square of side 1001 leaves a 728 by 1001 strip, which takes one square of side 728; the remaining 728 by 273 strip takes two squares of side 273, and so on. Notice that the numbers of squares of each size (1, 1, 2, 1, 2) are the quotients, and that the smallest square, of side 91, fits exactly into every larger one: 91 is the greatest common divisor.

This is close to how Euclid stated it. In the Elements, Book VII, Proposition 2 finds the "greatest common measure" of two numbers by subtracting the smaller from the larger "continually". Proposition 1 shows that if the process ends at the unit, the numbers are relatively prime (Euclid, ed. Joyce, 1996). Repeated subtraction of the smaller number is division done slowly: subtracting 273 from 728 twice before 273 exceeds what is left is the division $728 = 273 \cdot 2 + 182$. Euclid's proof of Proposition 2 already contains the argument of the lemma above. His corollary states that any number dividing two numbers divides their greatest common measure, which is proved below as a consequence of Bezout's identity.

The algorithm finds 91. Can its equations tell us more?

Bezout's identity

The equations of the Euclidean algorithm can be read backwards. The fourth equation says $91 = 273 - 182$. The third says $182 = 728 - 2 \cdot 273$; substituting,

$$91 = 273 - (728 - 2 \cdot 273) = 3 \cdot 273 - 728.$$

The second says $273 = 1001 - 728$, so $91 = 3 \cdot 1001 - 4 \cdot 728$. The first says $728 = 1729 - 1001$, so

$$91 = 3 \cdot 1001 - 4 \cdot (1729 - 1001) = 1729 \cdot (-4) + 1001 \cdot 7.$$

The greatest common divisor is a linear combination of the two numbers. This is always true, and it is the most useful fact about greatest common divisors.

Theorem (Bezout's identity). Let $a$ and $b$ be integers, not both zero, and let $d = \gcd(a, b)$. There exist integers $u$ and $v$ such that

$$d = au + bv.$$

The idea is the back-substitution above, organized forward. Each remainder is the one two steps back minus a multiple of the one just before it. So if both earlier remainders are combinations of $a$ and $b$, the new one is too, and the last nonzero remainder is $d$.

Proof. First suppose $a \ge b > 0$ and run the Euclidean algorithm, with remainders $r_0 = a$, $r_1 = b$, $r_2, \ldots, r_n = d$. We show by induction that every remainder is a linear combination of $a$ and $b$: for each $i$ there are integers $s_i$ and $t_i$ with $r_i = a s_i + b t_i$. For $i = 0$ and $i = 1$, take $(s_0, t_0) = (1, 0)$ and $(s_1, t_1) = (0, 1)$. Suppose the claim holds for $r_{i-1}$ and $r_i$. The division step gives $r_{i+1} = r_{i-1} - q_i r_i$, so

$$r_{i+1} = (a s_{i-1} + b t_{i-1}) - q_i (a s_i + b t_i) = a\,(s_{i-1} - q_i s_i) + b\,(t_{i-1} - q_i t_i),$$

which is a linear combination with $s_{i+1} = s_{i-1} - q_i s_i$ and $t_{i+1} = t_{i-1} - q_i t_i$. By induction the claim holds for every remainder, in particular for $r_n = d$.

The remaining cases reduce to this one. If one of the numbers is 0, say $b = 0$, then $d = \lvert a \rvert = a \cdot (\pm 1) + b \cdot 0$. If both are nonzero, apply the first case to $\lvert a \rvert$ and $\lvert b \rvert$ (in whichever order puts the larger first), which have the same greatest common divisor, to get $d = \lvert a \rvert u' + \lvert b \rvert v'$. Since $\lvert a \rvert = \pm a$ and $\lvert b \rvert = \pm b$, changing the signs of $u'$ and $v'$ as needed gives $d = au + bv$. $\blacksquare$

The coefficients are not unique. Since $1729 \cdot 11 - 1001 \cdot 19 = 0$, adding 11 to $u$ and subtracting 19 from $v$ changes nothing, so $(u, v) = (7, -12)$ and $(18, -31)$ also give 91. The course text proves Bezout's identity differently. It takes the smallest positive linear combination of $a$ and $b$ and shows that it is the greatest common divisor (Hungerford, 2014, Theorem 1.2; Judson, 2026, Theorem 2.2.2 argues the same way). That proof is shorter, but it does not say how to find $u$ and $v$. The proof above does, and it is an algorithm in its own right.

The extended Euclidean algorithm

The recurrences in the proof compute $u$ and $v$ alongside the remainders, with no back-substitution. Each row records a remainder $r_i$ and the coefficients that express it, $r_i = 1729\, s_i + 1001\, t_i$. The quotient $q_i = \lfloor r_{i-1} / r_i \rfloor$ in row $i$ is used to form row $i + 1$ from rows $i - 1$ and $i$. The rule is the same in all three columns: the new value is the value two rows up minus $q_i$ times the value one row up.

$i$ $r_i$ $s_i$ $t_i$ $q_i$
0 1729 1 0
1 1001 0 1 1
2 728 1 $-1$ 1
3 273 $-1$ 2 2
4 182 3 $-5$ 1
5 91 $-4$ 7 2
6 0 11 $-19$

Row 5 is the answer, $91 = 1729 \cdot (-4) + 1001 \cdot 7$, the same coefficients the back-substitution found. Each row can be checked independently: row 4 says $1729 \cdot 3 - 1001 \cdot 5 = 5187 - 5005 = 182$. The final row, with remainder 0, is the relation $1729 \cdot 11 - 1001 \cdot 19 = 0$ used above to produce other pairs of coefficients; note that $11 = 1001/91$ and $19 = 1729/91$.

In Python, keeping only the two most recent rows:

def extended_gcd(a, b):
    """Return (d, s, t) with d = gcd(a, b) = a*s + b*t, for a, b >= 0 not both 0."""
    r0, s0, t0 = a, 1, 0
    r1, s1, t1 = b, 0, 1
    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 - q * r1
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1
    return r0, s0, t0

extended_gcd(1729, 1001) returns (91, -4, 7), and the script for this article checks the function against Python's math.gcd and the identity $d = as + bt$ for every pair $0 \le a, b < 200$. The function also works when $a < b$: the first pass then swaps the two numbers, with quotient 0.

What Bezout's identity gives

Why does writing 91 as a combination matter as much as finding 91? Four consequences follow, each used later in the course.

The combinations of two numbers are the multiples of their gcd

Theorem. Let $a$ and $b$ be integers, not both zero, with $d = \gcd(a, b)$. An integer is a linear combination of $a$ and $b$ if and only if it is a multiple of $d$:

$$\{\, au + bv : u, v \in \mathbb{Z} \,\} = \{\, dk : k \in \mathbb{Z} \,\}.$$

In particular, $d$ is the smallest positive linear combination of $a$ and $b$.

The idea: $d$ divides every combination, by law (3), and scaling Bezout's identity makes every multiple of $d$ a combination.

Proof. If $m = au + bv$, then $d \mid m$ by law (3), since $d$ divides $a$ and $b$. Conversely, by Bezout's identity $d = au_0 + bv_0$ for some $u_0$ and $v_0$, so any multiple $dk = a(u_0 k) + b(v_0 k)$ is a linear combination. The smallest positive multiple of $d$ is $d$ itself. $\blacksquare$

Two measuring rods of lengths 1729 and 1001, laid end to end in either direction, can mark off exactly the lengths that are multiples of 91. The script for this article confirms that the positive combinations up to 1000 are exactly $91, 182, \ldots, 910$. So the rods can mark off 637, which is $7 \cdot 91$, but never 600, which leaves remainder 54 on division by 91.

In the language of ideals, the set of all combinations of $a$ and $b$ is the ideal they generate. The theorem says that this ideal is generated by the single element $d$. This is the first sign that every ideal of $\mathbb{Z}$ is principal.

Every common divisor divides the gcd

Corollary. Let $a$ and $b$ be integers, not both zero, and $d = \gcd(a, b)$.

  1. If $c \mid a$ and $c \mid b$, then $c \mid d$.
  2. Conversely, a positive integer $d'$ that divides $a$ and $b$, and is divisible by every common divisor of $a$ and $b$, equals $\gcd(a, b)$.

The idea for (1) is that $d$ is a combination of $a$ and $b$, and a common divisor divides every combination.

Proof. (1) Write $d = au + bv$; then $c \mid d$ by law (3). (2) Since $d$ is a common divisor of $a$ and $b$, the hypothesis on $d'$ gives $d \mid d'$. Since $d'$ is a common divisor, part (1) gives $d' \mid d$. By law (5), $d' = \pm d$, and both are positive, so $d' = d$. $\blacksquare$

Part (1) is the corollary to Euclid's Proposition VII.2. It says that the greatest common divisor is greatest not only in size but in the stronger sense of divisibility: every common divisor is a factor of it. On the running pair, the common divisors 1, 7, 13 and 91 all divide 91. Part (2) shows that this property characterizes the gcd. It is the version of the definition that generalizes to rings where "largest" has no meaning, such as rings of polynomials (Hungerford, 2014, Corollary 1.3).

Relatively prime integers

Corollary. Integers $a$ and $b$ are relatively prime if and only if $au + bv = 1$ for some integers $u$ and $v$.

Proof. If $\gcd(a, b) = 1$, Bezout's identity gives the combination. Conversely, if $au + bv = 1$, then every common divisor of $a$ and $b$ divides 1 by law (3), so it is 1 or $-1$, and the greatest is 1. $\blacksquare$

The coefficient $u$ in $au + bv = 1$ will reappear as the inverse of $a$ in arithmetic modulo $b$, the key computation in the RSA cryptosystem. For now, its use is a cancellation law.

Theorem. Let $a$, $b$ and $c$ be integers. If $a \mid bc$ and $\gcd(a, b) = 1$, then $a \mid c$.

The idea is to multiply $1 = au + bv$ by $c$. That writes $c$ as a combination of $a$ and $bc$, two numbers that $a$ divides.

Proof. Write $1 = au + bv$. Multiplying by $c$ gives $c = a(cu) + (bc)v$. The integer $a$ divides $a(cu)$, and it divides $bc$ by hypothesis, so it divides their linear combination $c$ by law (3). $\blacksquare$

The hypothesis $\gcd(a, b) = 1$ cannot be dropped: $10 \mid 4 \cdot 15$, but $10 \nmid 15$, because 10 shares the factor 2 with 4. The theorem is Hungerford's Theorem 1.4, and with $a$ a prime it becomes Euclid's lemma, the key to unique factorization.

Check your understanding. Suppose $19 \mid 1001c$ for some integer $c$. Must 19 divide $c$? And if $91 \mid 1729c$, must 91 divide $c$?

The first, yes: $1001 = 7 \cdot 11 \cdot 13$ shares no factor with 19, so $\gcd(19, 1001) = 1$ and the theorem applies. The second, no: $\gcd(91, 1729) = 91$, and $c = 1$ already gives $91 \mid 1729$ with $91 \nmid 1$.

Linear equations in integers

The rods measured lengths of the form $1729x + 1001y$. Turned around, that is an equation: which integer equations $ax + by = c$ have integer solutions $x$ and $y$, and what are all the solutions? Bezout's identity answers both questions.

Theorem. Let $a$ and $b$ be integers, not both zero, $d = \gcd(a, b)$, and $c$ an integer. The equation $ax + by = c$ has a solution in integers if and only if $d \mid c$. If $(x_0, y_0)$ is one solution, the solutions are exactly

$$x = x_0 + \frac{b}{d}\, k, \qquad y = y_0 - \frac{a}{d}\, k, \qquad k \in \mathbb{Z}.$$

Here is the plan. Existence is the theorem on combinations. Two solutions differ by a solution of $ax + by = 0$, and cancellation forces that difference to be a multiple of $(b/d, -a/d)$.

Proof. The left side $ax + by$ is a linear combination of $a$ and $b$, so by the theorem on combinations a solution exists exactly when $c$ is a multiple of $d$.

For the description of all solutions, suppose $b \neq 0$ (the case $b = 0$, $a \neq 0$ is the same with the roles of $x$ and $y$ swapped). Let $a' = a/d$ and $b' = b/d$, which are integers. Dividing Bezout's identity $d = au + bv$ by $d$ gives $1 = a'u + b'v$, so $\gcd(a', b') = 1$ by the corollary on relatively prime integers.

The pairs in the formula are solutions: $a(x_0 + b'k) + b(y_0 - a'k) = ax_0 + by_0 + (ab' - ba')k = c + 0$, because $ab' = ab/d = ba'$.

Conversely, let $(x, y)$ be any solution. Subtracting $ax_0 + by_0 = c$ from $ax + by = c$ gives $a(x - x_0) = b(y_0 - y)$, and dividing by $d$,

$$a'(x - x_0) = b'(y_0 - y).$$

So $b'$ divides $a'(x - x_0)$, and since $\gcd(b', a') = 1$, the cancellation theorem gives $b' \mid (x - x_0)$, say $x - x_0 = b'k$. Substituting, $a'b'k = b'(y_0 - y)$, and canceling the nonzero integer $b'$ gives $y_0 - y = a'k$. Hence $x = x_0 + b'k$ and $y = y_0 - a'k$. $\blacksquare$

Example. Solve $1729x + 1001y = 455$. Here $d = 91$ and $455 = 5 \cdot 91$, so solutions exist. Multiplying Bezout's identity $1729 \cdot (-4) + 1001 \cdot 7 = 91$ by 5 gives the solution $(x_0, y_0) = (-20, 35)$. With $b/d = 11$ and $a/d = 19$, all solutions are

$$x = -20 + 11k, \qquad y = 35 - 19k.$$

Taking $k = 2$ gives the solution with the smallest nonnegative $x$, namely $(2, -3)$: indeed $1729 \cdot 2 - 1001 \cdot 3 = 3458 - 3003 = 455$. The equation $1729x + 1001y = 100$ has no integer solutions at all, because 91 does not divide 100. Equations of this kind are called linear Diophantine equations. Solving them is the same problem as solving the linear congruences of modular arithmetic.

Check your understanding. Which solution of $1729x + 1001y = 455$ has the smallest positive $y$?

Since $y = 35 - 19k$ falls by 19 at each step, the smallest positive value is $35 - 19 = 16$, at $k = 1$. Then $x = -20 + 11 = -9$, and $1729 \cdot (-9) + 1001 \cdot 16 = -15561 + 16016 = 455$.

How fast is the Euclidean algorithm?

The termination proof above allows up to $b$ divisions, but the example needed only five for numbers in the thousands. In 1844 Gabriel Lamé published a bound that is close to exact. His note begins by observing that the arithmetic textbooks of his time bounded the number of divisions by half the smaller number. It proves instead that the number is less than five times the number of decimal digits of the smaller number (Lamé, 1844). The argument runs through the Fibonacci numbers $F_1 = F_2 = 1$, $F_{k+1} = F_k + F_{k-1}$, which give the worst case.

Proposition. Let $a > b > 0$. If the Euclidean algorithm on $a$ and $b$ performs $n$ divisions, then $b \ge F_{n+1}$ and $a \ge F_{n+2}$.

The idea: since every quotient is at least 1, each dividend is at least the sum of the next two numbers in the chain, which is how Fibonacci numbers grow.

Proof. By induction on $n$. If $n = 1$, then $b \ge 1 = F_2$ and $a \ge b + 1 \ge 2 = F_3$. Let $n \ge 2$ and assume the statement for $n - 1$ divisions. The first division $a = bq + r$ cannot leave $r = 0$, since then the algorithm would stop after one division. So $0 < r < b$, and the algorithm continues exactly as it would on the pair $(b, r)$, performing $n - 1$ further divisions. By the induction hypothesis, $r \ge F_n$ and $b \ge F_{n+1}$. Since $a > b$, the quotient $q$ is at least 1, so

$$a = bq + r \ge b + r \ge F_{n+1} + F_n = F_{n+2}. \qquad \blacksquare$$

The bound is attained by consecutive Fibonacci numbers. For $k \ge 2$, $F_{k+2} = F_{k+1} \cdot 1 + F_k$ with $0 < F_k < F_{k+1}$. So every quotient is 1 until the pair reaches $(F_3, F_2) = (2, 1)$, and the algorithm on $(F_{n+2}, F_{n+1})$ performs exactly $n$ divisions. The pair $(13, 8)$ takes five divisions, with quotients 1, 1, 1, 1, 2, and $(144, 89)$ takes ten. A brute-force search in the script confirms that for every $n$ up to 14, the smallest $b$ for which some $a > b$ needs $n$ divisions is $F_{n+1}$.

Check your understanding. The next Fibonacci pair after $(13, 8)$ is $(21, 13)$. Predict the number of divisions and the quotients.

Six divisions, with quotients 1, 1, 1, 1, 1, 2: the pair steps down through $(13, 8), (8, 5), (5, 3), (3, 2)$ to $(2, 1)$, and the last division leaves remainder 0. No pair with a smaller $b$ needs six.

To turn the proposition into a bound in terms of digits, compare the Fibonacci numbers with powers of the golden ratio $\varphi = (1 + \sqrt{5})/2 \approx 1.618$, which satisfies $\varphi^2 = \varphi + 1$. By induction, $F_k \ge \varphi^{k-2}$ for all $k \ge 2$: this holds for $k = 2$ and $k = 3$ ($1 \ge 1$ and $2 \ge 1.618$), and if it holds for $k - 1$ and $k$, then

$$F_{k+1} = F_k + F_{k-1} \ge \varphi^{k-2} + \varphi^{k-3} = \varphi^{k-3}(\varphi + 1) = \varphi^{k-3}\varphi^2 = \varphi^{k-1}.$$

So if the algorithm performs $n$ divisions, $b \ge F_{n+1} \ge \varphi^{n-1}$, that is,

$$n \le 1 + \log_\varphi b.$$

If $b$ has $h$ decimal digits, then $b < 10^h$, so $n - 1 < h / \log_{10}\varphi \approx 4.785\,h$. For $h \ge 5$ this gives $n < 4.785h + 1 \le 5h$. For $h = 1, 2, 3, 4$ it gives $n < 5.78, 10.57, 15.35, 20.14$, so again $n \le 5h$. Hence:

Lamé's bound. The number of divisions in the Euclidean algorithm is at most five times the number of decimal digits of the smaller number.

Lamé stated the bound with "less than", and on his own count that is right. For consecutive Fibonacci numbers his note counts the divisions down to the remainder 1, leaving out the final division, which leaves remainder 0. The argument above gives $n - 1 < 4.785h < 5h$ for the divisions before the last. Counting every division, including the final one, the bound is reached: $(13, 8)$ needs exactly $5 = 5 \cdot 1$ divisions, $(144, 89)$ needs $10$, and $(1597, 987)$ needs $15$. An exhaustive search over all $b < 1000$ in the script finds no pair that exceeds $5h$. For the running example the bound allows 20 divisions and five were needed.

The practical meaning is that the number of steps grows with the number of digits, not with the size of the numbers. Doubling the length of the inputs at most doubles the number of divisions. This is why the algorithm and its extension remain efficient for the integers of several hundred digits used in RSA. There, listing divisors, or even trying all of them up to the square root, is out of the question.

Where it leads

What we have learned

Euclid's algorithm finds $\gcd(1729, 1001) = 91$ in five divisions without listing a divisor. It works because each division keeps the common divisors, and by Lamé's bound its steps grow only with the number of digits. Run backwards, it gives Bezout's identity, $91 = 1729 \cdot (-4) + 1001 \cdot 7$, and from that come cancellation and every solution of a linear equation in integers.

Cancellation matters most when the divisor is a prime. What does that say about factoring 1729 and 1001 into primes, and why are those factorizations unique? That is Primes and the Fundamental Theorem of Arithmetic.

References

  • Euclid. Elements, Book VII, Propositions 1 and 2. In D. E. Joyce (ed.), Euclid's Elements (1996), Clark University, online at mathcs.clarku.edu/~djoyce/elements/. Proposition 2 finds the greatest common measure by continual subtraction; its corollary is the statement that every common divisor divides the greatest common divisor. record · 2 pages
  • Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §1.2. Brooks/Cole, Cengage Learning. The course text: the greatest common divisor as a linear combination (Theorem 1.2), its characterization by divisibility (Corollary 1.3), and the cancellation theorem (Theorem 1.4). record · 44 pages
  • Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §2.2, including §2.2.1 on the Euclidean algorithm. Free online at judsonbooks.org. record · 44 pages
  • Lamé, G. (1844). Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes rendus hebdomadaires des séances de l'Académie des sciences, 19, 867–870. record