Source: EECS 376 Homework 1 (Problem 6)
Tags: Euclidean algorithm, GCD, greatest common divisor, potential function, Fibonacci numbers, worst case, algorithm analysis, EECS 376
Difficulty: Intermediate
Prerequisites: Modular arithmetic (a mod b), basic understanding of recursion, familiarity with Big-O notation (see the companion Big-O study notes).
The Euclidean algorithm is one of the oldest known algorithms and one of the first you will analyse rigorously in EECS 376. It computes the greatest common divisor (GCD) of two integers and runs surprisingly fast. This homework asks you to trace the algorithm step by step, verify a potential function that proves its efficiency, and investigate what inputs produce the worst-case running time. The punchline: the worst cases are consecutive Fibonacci numbers, and the algorithm always terminates in at most O(log(x + y)) steps.
The Euclidean algorithm repeatedly replaces the larger input with the remainder of dividing the two inputs, until one reaches zero. The potential function si = a + b at each step decreases by a factor of at least 2/3 per recursive call, giving an O(log(a + b)) bound on the number of steps. Consecutive Fibonacci numbers are the worst-case inputs because they force the quotient qi to equal 1 at every step, producing the slowest possible decrease.
Greatest common divisor (GCD)
The largest positive integer that divides both a and b. For example, gcd(12, 8) = 4. In simple terms, the biggest number that fits evenly into both inputs.
Euclidean algorithm
A recursive procedure: Euclid(a, b) returns b if a = 0, otherwise returns Euclid(b mod a, a). It works because gcd(a, b) = gcd(b mod a, a). Think of it as repeatedly taking remainders until you hit zero.
Potential function
A quantity you track across iterations to prove that the algorithm makes progress. For the Euclidean algorithm, si = a + b at step i. At each recursive call, si+1 <= (2/3) * si, which guarantees termination in O(log(a + b)) steps.
Quotient (qi)
In the division a = qi * b + r, the quotient qi is how many times b fits into a. The remainder r = a mod b is what is left over. The potential decreases fastest when qi is large, and slowest when qi = 1.
Fibonacci numbers
The sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... where each number is the sum of the two preceding ones. Consecutive Fibonacci numbers produce the worst-case input for the Euclidean algorithm because every quotient equals 1.
Given two non-negative integers a and b (with a <= b by convention):
If a = 0, return b.
Otherwise, compute r = b mod a.
Return Euclid(r, a).
Each step replaces the pair (a, b) with (b mod a, a). The first argument strictly decreases, so the algorithm must terminate.
Define the potential at step i as si = ai + bi, where ai and bi are the two arguments at that step.
At each step, bi+1 = ai and ai+1 = bi mod ai. The key inequality: si+1 <= (2/3) * si.
Why? Write bi = qi * ai + ri where ri = bi mod ai. Then si+1 = ai + ri. Since ri < ai and ri <= bi - ai (because qi >= 1), we get si+1 = ai + ri <= ai + (bi - ai) = bi. Meanwhile, si+1 = ai + ri < 2 * ai. Combining: si+1 < min(bi, 2*ai) <= (2/3)(ai + bi) = (2/3)*si.
Since si decreases by at least a factor of 2/3 each step, after k steps we have sk <= (2/3)^k * s0. The algorithm terminates when si < 2, so k <= log_{3/2}(s0) = log_{3/2}(a + b).
i. Euclid(45, 162)
Step 0: Euclid(45, 162). s0 = 207. 162 = 3*45 + 27.
Step 1: Euclid(27, 45). s1 = 72. 45 = 1*27 + 18.
Step 2: Euclid(18, 27). s2 = 45. 27 = 1*18 + 9.
Step 3: Euclid(9, 18). s3 = 27. 18 = 2*9 + 0.
Step 4: Euclid(0, 9). Done. GCD = 9.
Recursive calls (excluding the initial swap if needed): 4. Check: each si+1 <= (2/3)*si holds (72/207 = 0.35, 45/72 = 0.63, 27/45 = 0.60, all <= 2/3).
ii. Euclid(101, 183)
Step 0: Euclid(101, 183). s0 = 284. 183 = 1*101 + 82.
Step 1: Euclid(82, 101). s1 = 183. 101 = 1*82 + 19.
Step 2: Euclid(19, 82). s2 = 101. 82 = 4*19 + 6.
Step 3: Euclid(6, 19). s3 = 25. 19 = 3*6 + 1.
Step 4: Euclid(1, 6). s4 = 7. 6 = 6*1 + 0.
Step 5: Euclid(0, 1). Done. GCD = 1.
Recursive calls: 5.
iii. Euclid(144, 233)
These are consecutive Fibonacci numbers, the worst case.
Step 0: Euclid(144, 233). s0 = 377. 233 = 1*144 + 89.
Step 1: Euclid(89, 144). s1 = 233. 144 = 1*89 + 55.
Step 2: Euclid(55, 89). s2 = 144. 89 = 1*55 + 34.
Step 3: Euclid(34, 55). s3 = 89. 55 = 1*34 + 21.
Step 4: Euclid(21, 34). s4 = 55. 34 = 1*21 + 13.
Step 5: Euclid(13, 21). s5 = 34. 21 = 1*13 + 8.
Step 6: Euclid(8, 13). s6 = 21. 13 = 1*8 + 5.
Step 7: Euclid(5, 8). s7 = 13. 8 = 1*5 + 3.
Step 8: Euclid(3, 5). s8 = 8. 5 = 1*3 + 2.
Step 9: Euclid(2, 3). s9 = 5. 3 = 1*2 + 1.
Step 10: Euclid(1, 2). s10 = 3. 2 = 2*1 + 0.
Step 11: Euclid(0, 1). Done. GCD = 1.
Recursive calls: 11. Notice every quotient is 1 (except the last), and the potential ratio si+1/si is approximately 0.618 (the golden ratio inverse), close to the 2/3 bound.
iv. Euclid(1234, 3456)
Step 0: Euclid(1234, 3456). s0 = 4690. 3456 = 2*1234 + 988.
Step 1: Euclid(988, 1234). s1 = 2222. 1234 = 1*988 + 246.
Step 2: Euclid(246, 988). s2 = 1234. 988 = 4*246 + 4.
Step 3: Euclid(4, 246). s3 = 250. 246 = 61*4 + 2.
Step 4: Euclid(2, 4). s4 = 6. 4 = 2*2 + 0.
Step 5: Euclid(0, 2). Done. GCD = 2.
Recursive calls: 5. Larger quotients (like 61) cause the potential to drop steeply, which is why this terminates quickly despite large inputs.
The potential decreases most slowly when qi = 1 at every step. When qi = 1, we have bi = 1 * ai + ri, so ri = bi - ai. The recurrence then becomes:
ai+1 = bi - ai
bi+1 = ai
Working backwards from the base case, this exactly produces Fibonacci numbers. If the algorithm ends at Fk and Fk+1, the starting inputs were Fn and Fn+1 for some larger n.
Consecutive Fibonacci numbers are the worst-case inputs for the Euclidean algorithm. The number of recursive calls for Euclid(Fn, Fn+1) is approximately n, which is roughly log_{phi}(Fn+1) where phi = (1 + sqrt(5))/2 is the golden ratio. This is close to the theoretical upper bound of log_{3/2}(a + b).
The Euclidean algorithm: Euclid(a, b) = b if a = 0, else Euclid(b mod a, a).
GCD identity: gcd(a, b) = gcd(b mod a, a).
Potential function: si = ai + bi. Satisfies si+1 <= (2/3) * si.
Upper bound on steps: Number of recursive calls <= log_{3/2}(a + b).
Fibonacci recurrence: F(n) = F(n-1) + F(n-2), with F(1) = F(2) = 1.
Fibonacci growth: F(n) is approximately phi^n / sqrt(5), where phi = (1 + sqrt(5))/2 ≈ 1.618.
The Euclidean algorithm is used in cryptography (RSA key generation requires computing GCDs and modular inverses), in simplifying fractions, and in solving linear Diophantine equations. The extended Euclidean algorithm (a variation) computes the modular inverse needed for public-key encryption.
Students sometimes think the Euclidean algorithm only works for positive integers. It works for non-negative integers; the base case is when one argument is 0.
A common mistake is forgetting to swap the arguments so that the smaller one comes first. The algorithm handles this implicitly (one step just swaps them), but it counts as an extra recursive call.
Students often confuse the quotient qi with the remainder ri. The remainder is what the algorithm passes forward; the quotient determines how fast the potential drops.
Some students think the worst case is large inputs. It is not. The worst case depends on the ratio structure (Fibonacci-like), not the absolute size of the inputs.
⚠️ Be prepared to trace the Euclidean algorithm step by step and compute si at each stage.
⚠️ You may be asked to verify the inequality si+1 <= (2/3)*si for specific inputs. Show the ratio explicitly.
⚠️ Know that consecutive Fibonacci numbers are the worst case and be able to explain why (qi = 1 at every step).
⚠️ The running time bound log_{3/2}(a + b) comes from the potential function argument. Be able to derive it from si+1 <= (2/3)*si.
Fill in the blank: gcd(0, n) = _____.
True or false: The Euclidean algorithm can take more than log_{3/2}(a + b) steps. _____
Fill in the blank: The worst-case inputs for the Euclidean algorithm are consecutive _____ numbers.
True or false: If qi = 5 at some step, the potential drops faster than if qi = 1. _____
Fill in the blank: gcd(48, 18) = _____.
Q: Compute gcd(84, 36) using the Euclidean algorithm. Show each step.
A: Euclid(36, 84): 84 = 236 + 12. Euclid(12, 36): 36 = 312 + 0. Euclid(0, 12). GCD = 12.
Q: What is the potential function for the Euclidean algorithm, and what property does it satisfy?
A: si = ai + bi at step i. It satisfies si+1 <= (2/3) * si, which guarantees termination in O(log(a + b)) steps.
Q: Why are consecutive Fibonacci numbers the worst-case inputs?
A: Because every quotient qi = 1, which produces the smallest possible decrease in the potential function at each step. This makes the algorithm take the maximum number of recursive calls relative to the input size.
Q: What is the GCD of 233 and 144?
A: They are consecutive Fibonacci numbers and share no common factor besides 1, so gcd(233, 144) = 1.
Q: If gcd(a, b) = d, what can you say about a and b?
A: Both a and b are multiples of d. Equivalently, a = d * m and b = d * n where gcd(m, n) = 1.
The Euclidean algorithm connects to modular arithmetic, which is foundational to number theory and cryptography. The extended Euclidean algorithm computes Bezout coefficients (integers x, y such that ax + by = gcd(a, b)), which are needed for modular inverses in RSA. The potential function analysis here is a preview of amortised analysis techniques you will see in data structures courses. The Fibonacci connection links to the golden ratio and the analysis of algorithms that follow Fibonacci-like recurrences.
Euclidean algorithm, GCD, greatest common divisor, modular arithmetic, remainder, quotient, potential function, amortised analysis, Fibonacci numbers, golden ratio, worst-case analysis, RSA, extended Euclidean algorithm, Bezout's identity, EECS 376, algorithm analysis, number theory