GMAT Practice Question: For positive integers a and b, the remainder when a is divided by b...
Question
For positive integers a and b, the remainder when a is divided by b is equal to the remainder when b is divided by a. Which of the following could be a value of a b ? I. 24 II. 30 III. 36
- II only
- III only
- I and II only
- II and III only
- I, II, and III
Topics: number theory, divisibility, remainders
Solution
Step 1
We translate \textbf{"the remainder when a is divided by b is equal to the remainder when b is divided by a"} into equal-remainder equations with integer quotients.
a = qb + r b = pa + r q,p \text{ are integers} 0 \le r r \text{ is less than } b r \text{ is less than } a
Step 2
We compare the sizes of the two numbers to see when a common remainder can occur; we avoid the two unequal cases.
\text{If } a \text{ is less than } b, \text{ then } a = 0 \times b + a \text{, so the remainder is } a \text{Also } b = pa + r \text{ with } 0 \le r \text{ and } r \text{ is less than } a \text{Equal remainders would force } r = a \text{, which is impossible since } r \text{ is less than } a \text{If } a \text{ is greater than } b, \text{ then } b = 0 \times a + b \text{, so the remainder is } b \text{Also } a = qb + r \text{ with } 0 \le r \text{ and } r \text{ is less than } b \text{Equal remainders would force } r = b \text{, which is impossible since } r \text{ is less than } b \text{So the only possibility is } a = b \text{, giving remainder } 0
Step 3
With the two numbers equal, the product is the same factor multiplied by itself. We now test the options.
ab = a \times a = a^2
Step 4
Option I: check whether 24 can be written as the same integer times itself.
4^2 = 16 5^2 = 25 24 \text{ is between } 16 \text{ and } 25 \text{, so it is not of the form } c \times c
Step 5
Option II: check whether 30 can be written as the same integer times itself.
5^2 = 25 6^2 = 36 30 \text{ is between } 25 \text{ and } 36 \text{, so it is not of the form } c \times c
Step 6
Option III: check whether 36 can be written as the same integer times itself.
6^2 = 36 \text{Choose } a = 6 \text{ and } b = 6 \text{ to get } ab = 36
Answer
III only
