Difficulty: Introductory to Intermediate | Prerequisites: Modular arithmetic basics, familiarity with the concept of divisibility, the termination notes from Problem 1.
The Euclidean algorithm is one of the oldest known algorithms, and it serves as the first serious case study in EECS 376 for analysing an algorithm's running time using a potential function. It computes the greatest common divisor (GCD) of two integers. Understanding how to trace it, measure its iterations, and identify its worst-case inputs sets the template for every running-time analysis that follows in the course.
The Euclidean algorithm repeatedly replaces the larger number with the remainder of dividing it by the smaller, until one of them hits zero. It runs in O(log(x + y)) iterations. Consecutive Fibonacci numbers are the worst-case inputs, producing the most iterations for their size.
Greatest common divisor (GCD)
The largest positive integer that divides both x and y. Written gcd(x, y). Think of it as the biggest "building block" that tiles both numbers evenly.
Euclidean algorithm
An algorithm that computes gcd(x, y) by repeatedly replacing (x, y) with (y, x mod y) until the remainder is zero. The last non-zero remainder is the GCD.
Potential s_i
In the EECS 376 analysis, s_i = x_i + y_i, the sum of the two arguments at iteration i. This potential decreases by a factor of at least 2/3 each iteration.
Iteration
One application of the replacement step: (x, y) becomes (y, x mod y). Counting iterations tells you how many division operations the algorithm performs.
Fibonacci numbers
The sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... where each term is the sum of the two preceding terms. Consecutive Fibonacci numbers are the worst-case inputs for the Euclidean algorithm.
Given integers x > y >= 0:
If y = 0, return x (that is the GCD).
Otherwise, compute r = x mod y (the remainder when x is divided by y).
Replace (x, y) with (y, r) and repeat.
The algorithm terminates because y strictly decreases each iteration (the remainder r is always less than y), and y is always non-negative.
The algorithm swaps the arguments on the first step when x < y:
(55, 33): 55 mod 33 = 22, s = 88
(33, 22): 33 mod 22 = 11, s = 55
(22, 11): 22 mod 11 = 0, s = 33
(11, 0): done. GCD = 11.
Three iterations. At each step, s_{i+1} <= (2/3) s_i holds.
These are consecutive Fibonacci numbers, which produce the maximum number of iterations:
(987, 610): r = 377, s = 1597
(610, 377): r = 233, s = 987
(377, 233): r = 144, s = 610
(233, 144): r = 89, s = 377
(144, 89): r = 55, s = 233
(89, 55): r = 34, s = 144
(55, 34): r = 21, s = 89
(34, 21): r = 13, s = 55
(21, 13): r = 8, s = 34
(13, 8): r = 5, s = 21
(8, 5): r = 3, s = 13
(5, 3): r = 2, s = 8
(3, 2): r = 1, s = 5
(2, 1): r = 0, s = 3
(1, 0): done. GCD = 1.
Fourteen iterations. Each quotient is 1, so the remainder is as large as possible relative to the divisor, making progress as slow as it can be.
Define s_i = x_i + y_i (the sum of the two arguments at iteration i). The key claim proved in lecture is:
s_{i+1} <= (2/3) · s_i
This means the potential shrinks by at least a factor of 2/3 each step. Starting from s_0 = x + y, after k iterations we have s_k <= (2/3)^k · (x + y). The algorithm terminates when one argument reaches zero, so it runs at most log_{3/2}(x + y) iterations.
When the inputs are consecutive Fibonacci numbers F_{n+1} and F_n, every quotient is exactly 1 and every remainder is the preceding Fibonacci number. This means the potential decreases as slowly as the bound allows. No other pair of inputs of comparable size produces more iterations.
GCD recurrence:
gcd(x, y) = gcd(y, x mod y), with base case gcd(x, 0) = x
Potential bound per iteration:
s_{i+1} <= (2/3) · s_i, where s_i = x_i + y_i
Upper bound on iterations:
Number of iterations <= log_{3/2}(x + y) = O(log(x + y))
The Euclidean algorithm is used every time your browser establishes an HTTPS connection: the RSA key-generation step needs to find GCDs to verify that two large primes are coprime. It also appears in simplifying fractions, computing least common multiples for scheduling problems, and in computer algebra systems that reduce rational expressions.
Students sometimes think the algorithm requires x > y at the start. It does not: if x < y, the first iteration simply swaps them (since x mod y = x when x < y).
A frequent error is confusing the quotient with the remainder. The GCD depends on the remainder sequence, not the quotient sequence. The quotients matter only when you extend the algorithm to find Bezout coefficients.
Some students believe larger inputs always mean more iterations. They do not: gcd(1000000, 2) terminates in one iteration because 1000000 mod 2 = 0. What matters is the ratio structure of the inputs, not their raw size.
Students occasionally claim the worst case is when one input is prime. Being prime is neither necessary nor sufficient for worst-case behaviour. The worst case is consecutive Fibonacci numbers, regardless of primality.
⚠️ Be able to trace the Euclidean algorithm step by step and compute s_i at each stage. This is a standard exam question.
⚠️ Know why consecutive Fibonacci numbers are the worst case. The examiner may ask you to find inputs that maximise iterations for a given size.
⚠️ The 2/3 factor in the potential bound is derived in lecture. Make sure you can reproduce the argument: it splits into two cases depending on whether the quotient is 1 or at least 2.
What is gcd(48, 18)? (6)
True or false: The Euclidean algorithm always terminates in at most log_2(x + y) iterations. (False: the bound is log_{3/2}(x + y), which is larger.)
Fill in the blank: The worst-case inputs for the Euclidean algorithm are consecutive ___ numbers. (Fibonacci)
True or false: gcd(x, 0) = 0 for all x. (False: gcd(x, 0) = x.)
Q: Trace the Euclidean algorithm on (1005, 1296). How many iterations does it take? What is the GCD?
A: (1296, 1005): r = 291, s = 2301. (1005, 291): r = 132, s = 1296. (291, 132): r = 27, s = 423. (132, 27): r = 24, s = 159. (27, 24): r = 3, s = 51. (24, 3): r = 0, s = 27. (3, 0): done. GCD = 3, in 6 iterations.
Q: Why does the potential s_i decrease by a factor of at least 2/3 each iteration?
A: Let q be the quotient and r the remainder, so x = qy + r. Then s_{i+1} = y + r. If q >= 2, then y + r <= y + y = 2y <= x <= s_i, so s_{i+1}/s_i <= 2/3 (since y < s_i and r < y). If q = 1, then r = x - y and s_{i+1} = y + (x - y) = x, while s_i = x + y, so s_{i+1}/s_i = x/(x + y) < 2/3 because y > x/2 (since q = 1 implies y > x - y, i.e. y > x/2).
Q: Give a pair of inputs less than 100 that produces the maximum number of iterations of the Euclidean algorithm.
A: (55, 89), which are consecutive Fibonacci numbers. This gives 9 iterations, the maximum for inputs of this size.
The Euclidean algorithm is the foundation for the Extended Euclidean algorithm (Problem 3 in this homework), which additionally finds Bezout coefficients. Those coefficients are essential for computing modular inverses, which in turn power RSA encryption. The potential function technique used here to bound iterations reappears in amortised analysis later in the course.
Euclidean algorithm, GCD, greatest common divisor, gcd analysis, potential function, Fibonacci worst case, log_{3/2} bound, modular arithmetic, remainder, EECS 376, algorithm analysis, iteration count, Lame's theorem