ITPEC FE Subject A April 2026 Question 7
ITPEC FE Subject A April 2026 — Question 7 of 60
3 — the recursion is Euclid's algorithm, so F(x, y) returns the greatest common divisor.
Each step replaces the pair with (y, x mod y) until the second argument reaches 0:
- •
F(231, 15)— 231 mod 15 = 6 →F(15, 6) - •
F(15, 6)— 15 mod 6 = 3 →F(6, 3) - •
F(6, 3)— 6 mod 3 = 0 →F(3, 0) - •
y = 0, so the result isx= 3
Answer (b)
Why not others:
- (a) 2 — divides neither 231 (odd) nor 15
- (c) 5 — divides 15 but not 231, so it is not a common divisor
- (d) 7 — divides 231 (231 = 3 × 7 × 11) but not 15
Key rule: Recognising F(y, x mod y) with a base case of y = 0 identifies GCD instantly — the answer must divide both numbers, which alone eliminates three of the options here.
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.