The GATE Grind

GATE 2018 MN – Question 4

General Aptitude · 1 mark · Multiple choice

What would be the smallest natural number which when divided either by 20 or by 42 or
by 76 leaves a remainder of 7 in each case?

  1. 3047
  2. 6047
  3. 7987
  4. 63847

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 7987

Explanation

Let the number be N. The common remainder condition says N−7 is divisible by 20,42,76. Their prime factorizations are $20=2^2\cdot5$, $42=2\cdot3\cdot7$, $76=2^2\cdot19$, giving
$$L=\operatorname{LCM}(20,42,76)=2^2\cdot3\cdot5\cdot7\cdot19=7980.$$
Thus the positive solutions have form N=7+kL with nonnegative integer k.

There is a wording gap: literally N=7 itself has remainder 7 for all three divisors, with quotient zero, and is the smallest natural solution. The official answer instead assumes a nonzero common multiple, k≥1, giving N=7987, **C**. This is also the smallest listed option satisfying the remainder conditions. Official grading is retained with that implicit restriction stated.