ITPEC FE Subject A October 2025 Question 6

Euclidean Algorithm (GCD) — trace a flowchart to count loop iterations.

Given a = 56, b = 48, the algorithm computes GCD using repeated modulo:

• •Iteration 1: r = 56 mod 48 = 8 → a ← 48, b ← 8 → r ≠ 0 → continue
• •Iteration 2: r = 48 mod 8 = 0 → a ← 8, b ← 0 → r = 0 → exit

Point A is passed 2 times (once per loop iteration).

Why not others:
- (a) 1 — the loop runs more than once since 48 mod 8 still needs to be computed
- (c) 4 — too many iterations; the algorithm converges quickly
- (d) 8 — confuses the GCD result (8) with the iteration count

Key rule: Euclidean algorithm — GCD(a, b): repeat r = a mod b, then a ← b, b ← r until r = 0. The answer is the last non-zero a.

AI-generated — may contain errors