ITPEC FE Morning April 2021 Question 3

Euclidean Algorithm (GCD) — count how many times the remainder step executes.

Trace with x₀ = 175, x₁ = 77:

• •i=2: 175 mod 77 = 21
• •i=3: 77 mod 21 = 14
• •i=4: 21 mod 14 = 7
• •i=5: 14 mod 7 = 0 → stop, GCD = 7

Step (2) executes 4 times (i = 2, 3, 4, 5).

Why not others:
- (a) 3 — misses the final iteration where remainder becomes 0
- (c) 6 — too many; the algorithm converges quickly
- (d) 7 — confuses the GCD value (7) with the iteration count

Key rule: Count every execution of the remainder step, including the one that produces 0 and triggers the stop condition.

AI-generated — may contain errors