ITPEC IP October 2023 Question 9

The loop repeatedly subtracts the smaller value from the larger until x equals y; both then equal 14. Trace the pairs (x, y):

(98, 42) → (56, 42) → (14, 42) → (14, 28) → (14, 14)

At each step, if x > y, x becomes x − y; otherwise y becomes y − x. When equality is reached, the iteration's end condition is satisfied. Thus final x is 14. This is the subtraction form of Euclid's algorithm, so the common final value is gcd(98, 42) = 14.

Answer (b)

Why not others:
- 0 would arise only if subtraction continued after equality
- 28 and 56 are intermediate values, not the termination value

Key rule: In subtractive Euclid, stop when the two positive values become equal; that value is their greatest common divisor.

AI-generated — may contain errors