GATE 2018 CS – Question 4
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?
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.
More Quantitative Aptitude: Data Interpretation, Arithmetic and Number Computation questions
- GATE 2018 CS Q5
- GATE 2018 CS Q6
- GATE 2018 CS Q8
- GATE 2015 CS (CS1) Q8
- GATE 2015 CS (CS1) Q10
- GATE 2016 CS (CS1) Q6
All Quantitative Aptitude: Data Interpretation, Arithmetic and Number Computation questions →