Question

What is the largest number that divides 70 and 125, leaving remainders 5 and 8 respectively?

Options

• 13

• 9

• 3

• 585

Answer 1

13

Explanation:

If a number divides 70 and 125, leaving remainders 5 and 8, then it divides 70 – 5 = 65 and 125 – 8 = 117. 

So, the required number is gcd(65, 117). 

Using the Euclidean algorithm:

117 = 65 × 1 + 52

65 = 52 × 1 + 13

52 = 13 × 4 + 0

So, gcd = 13.