Question 4
Q4: Which of the following CANNOT be the greatest common divisor of two positive integers x and y?
(A) 1
(B) x
(C) y
(D) x -y
(E) x + y
Correct Answer
E
Solution
Given
We are given two positive integers x and y and are asked to find the GCD(x, y)
Approach
We know that
1 < = GCD of a set of integers < = Magnitude of the smallest integer of the set
We will use the above constraints on GCD to find the possible values which can’t be the GCD(x, y)
Working Out
In this the question the range of GCD(x, y) can be written as
1 < = GCD(x, y) < = Smaller of (x, y)
Let’s evaluate the options one by one:
(A) 1 – GCD can be equal to 1 if x, y don’t have any common prime factor
(B) x– GCD can be equal to x if x is the smaller integer and is a factor of y
(C) y– GCD can be equal to y if y is the smaller integer and is a factor of x
(D) x-y – GCD can be equal to the difference of x and y provided it is less than the magnitude of the smaller integer
(E) x + y – since x and y are given to be positive integers, the sum (x + y) will definitely be greater than the integers x and y and we know that GCD can’t be greater than the magnitude of the smallest integer. Hence x + y cannot be the GCD.
Answer: Option (E)
