Motivation
The Euclidean algorithm computes a greatest common divisor by repeated division with remainder. Correctness is only half of the analysis. We also want to know how many divisions it performs, as a function of the input. The answer has a precise extremal form. If and the algorithm performs divisions, then and must be at least two specific consecutive Fibonacci numbers. Those Fibonacci pairs attain the bound exactly.
The reason is structural. Each step writes a remainder as at least the sum of the next two remainders. The Fibonacci recurrence is that same inequality with equality. Once this is established, Fibonacci growth gives a logarithmic bound on the number of divisions.
A second distinction needs equal care. A logarithmic number of divisions is not a logarithmic number of bit operations. One division of large integers can be expensive. We keep the two measures separate throughout.
Definitions
Definition 1.2.1
(Greatest common divisor for all integers)
For integers not both zero, is the largest positive integer dividing both. Every integer divides , so the pair has no largest common divisor. We adopt the convention . With this convention, for every integer , and .
Definition 1.2.2
(The algorithm and the division count)
Given integers , first replace them by . If now , swap them, so that . The sign normalization and the swap are not divisions.
If , return . Zero divisions are performed. In particular, returns and no division by zero ever occurs.
If , set and . For , while , perform one division
The algorithm stops at the first index with . The division count is , and this count includes the final division with zero remainder. The output is .
Definition 1.2.3
(Fibonacci numbers)
Define , , and for . The sequence begins
The repeated value matters below. From onward the sequence is nondecreasing, and from onward it is strictly increasing.
Correctness, termination and Bézout coefficients
Theorem 1.2.4
(Euclid's invariant)
If , then .
Proof
(Common divisors of consecutive pairs)
Let divide both and . Then divides .
Conversely, if divides and , then divides .
The two pairs therefore have exactly the same set of common divisors. They have the same greatest element, or the same value under our convention.
The remainders satisfy . They are a strictly decreasing sequence of nonnegative integers, so a zero remainder appears after at most divisions. The algorithm therefore terminates. Applying the invariant along the chain gives
Theorem 1.2.5
(Extended Euclidean invariant)
Set , , , . Define
Then for every . In particular, .
Proof
(Induction on the index)
The cases and hold by the choice of initial values.
Suppose the identity holds for and . Then
For signed inputs, apply the result to the sorted pair of absolute values. First undo any swap of the two coefficients, so each again corresponds to the original input position. Then multiply each coefficient by the sign of its corresponding original input; a zero input contributes nothing.
The Fibonacci lower bound
Theorem 1.2.6
(Division-count lower bound)
Let , and suppose the algorithm performs divisions. Then
Proof
(Propagating backwards from the last nonzero remainder)
We prove for . The cases and are the two claims.
Case . We need and . First, . Second, gives . This case uses the hypothesis directly.
Case : base step . The last nonzero remainder is positive, so .
Case : base step . The final division is . Since , the preceding division has divisor and remainder , so . This forces . Hence .
Case : inductive step. Let and put , so that . In the division we have . For this is the hypothesis . For it holds because remainders strictly decrease. So , and
Proof X-ray
Why the bound runs upward and where a greater than $b$ enters
The proof reads the remainder chain from the bottom. A division with gives , the Fibonacci recurrence as an inequality, so lower bounds on two consecutive remainders give a lower bound on the one above them. That is why the induction needs two base cases: the last nonzero remainder is at least , and the one above it is at least , because forces .
The hypothesis enters only at the top division, where it gives (and, when , the bound ). Lower quotients are at least automatically, because the remainders strictly decrease. Reading the same chain for equality: every inequality is sharp exactly when , and all other quotients equal , and the chain then reproduces consecutive Fibonacci numbers.
The hypothesis cannot be dropped. If , the algorithm performs exactly one division, , so . The bound still holds, but fails for . In the proof, the inequality is precisely what breaks.
Theorem 1.2.7
(Consecutive Fibonacci inputs are extremal)
For each , the input takes exactly divisions. All quotients equal except the last, which equals .
Proof
(Care at the bottom of the sequence)
The quotient-1 divisions. For we have
The strict inequality holds because . So this is a legitimate division with remainder.
The chain. Starting from , the pairs move through . This uses one division for each , which is divisions.
The final division. The last pair is . One might write , but the remainder is not less than the divisor , so this is not a division with remainder. The correct division is .
Total. divisions.
With , the input uses divisions. Hence the lower bounds in the theorem are attained for every . For they are attained by . Every inequality in the backward proof becomes an equality exactly when , and all earlier quotients equal .
Concept lensAlgebraic
The remainder chain as a matrix product
Each division reads , where has rows and . Chaining the divisions gives
The entries are polynomials in the with nonnegative coefficients, so and are smallest when , and the other quotients equal ; powers of the matrix with rows and then produce consecutive Fibonacci numbers. Since , inverting the product yields the Bézout coefficients.
Logarithmic division bounds
Theorem 1.2.8
(Growth bounds)
For we have . Let . For we have .
Proof
(Induction using )
The first bound is proved in the exercise on below.
For the second bound, note that is the positive root of , and that . The base cases are and . For , induction gives
Applying the bounds. If and divisions occur, then . For this is the theorem. For it holds because and . Therefore
Deriving the form. Since , we have . Then
When , we have . So for every . Using rather than makes the bound meaningful at . When , exactly one division occurs, which is consistent with both bounds.
Division count versus bit complexity
Suppose both inputs have at most bits.
Number of divisions. We have , so .
Cost of one division. Each division involves numbers of at most bits. Ordinary schoolbook long division costs bit operations per division.
Total. A valid simple upper bound is therefore bit operations. This is an upper bound only. More careful accounting can improve it, but we do not pursue that here, and we claim no optimal bit complexity.
Input size is not just . The bound counts divisions and depends only on the smaller input. If is fixed and has bits, few divisions occur. The first division must still read and divide an -bit integer. The number of divisions is small, but the bit cost is not bounded by any function of alone.
Worked examples
Worked example 1.2.9
( with Bézout coefficients)
Divisions.
So and .
Back-substitution. From the second division, . From the first, . Substituting,
Check. and . Their difference is .
Extended invariant. With quotients , the table gives , and . The pair matches the back-substitution. The last pair satisfies , as the invariant requires.
Fibonacci bound. With , the theorem requires and . Both hold with a wide margin.
Worked example 1.2.10
(Consecutive Fibonacci input )
Here , so , and we predict divisions.
There are seven divisions and the gcd is . Six quotients equal , and the final quotient equals .
With , the theorem requires and . Both hold with equality. So no pair with and needs seven divisions.
Worked example 1.2.11
(Equality and the initial swap)
Equality. For , the single division gives and gcd .
Swap. For , normalization swaps the input to . That input takes divisions, with gcd .
A different convention. Suppose one omits the swap and divides immediately: . That extra step performs the swap with quotient . Under that convention the count is . Under ours the swap is not counted, so the count is .
Worked example 1.2.12
(A large first quotient)
For :
This is divisions.
The smallest needing three divisions is , attained by . The input is far from a worst case. Its first quotient removes almost all of in one step.
Large quotients make the remainders shrink quickly. The slowest shrinkage occurs when the quotients equal , as in the consecutive Fibonacci example.
Common mistakes
Counterexample mode
Logarithmic division count is not logarithmic bit cost
Claim. "The algorithm performs divisions, so it runs in time."
Refutation. Take and let be any integer with bits.
Few divisions. The first remainder lies in , so at most divisions occur. The division count stays bounded as grows.
Every bit matters. Flipping bit of changes by . That change is not divisible by , so it changes . A correct first division must therefore depend on every one of the bits.
Conclusion. The bit cost is at least proportional to , while . Counting divisions measures arithmetic steps, not bit work.
The following errors are also common.
- Dividing by zero. Pairs with , including , return immediately by convention.
- Claiming the algorithm is always linear in the input bits. The bound proved here is bit operations under schoolbook division. Nothing stronger is claimed.
Common mistake
(Dropping the final division)
Some authors do not count the final zero-remainder division. Their counts are one smaller than ours, so the Fibonacci index shifts. Always state the convention.
Common mistake
(Applying when )
The pair shows that this bound requires .
Common mistake
(Writing at the end of a Fibonacci chain)
The remainder must be strictly smaller than the divisor, so the correct final step is .
Exercises
Quick check
(Run the algorithm on . Count the divisions and find integers with .)
Solution
Divisions.
So and the gcd is .
Back-substitution. Start from . Since ,
Since ,
Check. . So and .
Table check. The coefficient table gives : and : . Its final pair agrees.
Theorem check. With , the theorem requires and . Both hold.
Quick check
(Count the divisions for and compare the result with the lower-bound theorem.)
Solution
Divisions.
So .
Comparison. The input is , so and the extremal theorem predicts , which matches. The lower bounds and hold with equality.
Quick check
(Under the stated conventions, determine the output and division count for and with , and for .)
Solution
. Normalization swaps the input to . The algorithm returns with zero divisions, and indeed .
. The algorithm returns with zero divisions.
. The algorithm returns , matching the convention . Zero divisions occur, and no division by zero is attempted.
In each case, a Bézout identity is immediate. For example, , and .
Quick check
(Show that always takes one division. Then explain exactly where the proof of fails, and which bound still holds.)
Solution
One division. The division algorithm gives , and the remainder satisfies . So .
Where the proof fails. In the case , the proof derived from . When that step is unavailable, and . The inequality also holds in the equality case: then and . The failed step is the separate deduction .
What still holds. The bound still holds. For , the inequality happens to be true, but it does not follow from the theorem.
Quick check
(For with an -bit integer, bound the number of divisions. Explain why the first quotient is large and why the bit cost is not bounded independently of .)
Solution
Bounding the count. Write with .
- If : one division in total.
- If : the next step is , so two divisions.
- If : the next steps are and , so three divisions.
Thus , consistent with .
The first quotient. We have . Since , this quotient has about bits.
Bit cost. As shown in the counterexample, the remainder depends on every bit of . Producing requires writing out roughly bits as well. So the first division costs at least on the order of bit operations. The division count is bounded, but the bit cost grows with .
Quick check
(Prove for . Then deduce for .)
Solution
Base cases. and .
Inductive step. For , monotonicity from index onward gives . Using the hypothesis for ,
Deduction. If and divisions occur, the lower-bound theorem gives
Taking gives , that is, .