ITPEC FE Subject A April 2026 Question 7
For integers x and y (x > y ≥ 0), a function F(x, y) is defined as below:
What is the value F(231, 15)? Here, “x mod y” represents the remainder after division of x by y.
Explanation
3 — F is Euclid's algorithm, so F(231, 15) is the greatest common divisor of 231 and 15.
Replace (x, y) with (y, x mod y) until y = 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 is x = 3
Check: 231 = 3 × 7 × 11 and 15 = 3 × 5, so the only common factor is 3.
Answer (b)
Why not others:
- •(a) 2 — divides neither 231 nor 15, both odd
- •(c) 5 — divides 15 but not 231
- •(d) 7 — divides 231 but not 15
Key rule: A recursion of the form F(y, x mod y) that stops at y = 0 is the GCD, and a GCD must divide both arguments, which rules out candidates immediately.
Algorithm and Programming · AI-written, may contain errors
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.