GATE CS Mastery
Cheat sheets

GATE CS 2018 · General Aptitude

Question 4

MCQPrinted as GA Q.41 markWrong answer: −1/3Easy (estimate)

Question

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?

Choose one option
Official answer and solution
Official answer
C
From
Official GATE 2018 answer key

Solution

Find the least common multiple (LCM) of 20, 42, and 76, then add the constant remainder 7.

A number NN leaving remainder 7 when divided by 20, 42, and 76 satisfies:

N≡7(mod20),N≡7(mod42),N≡7(mod76)N \equiv 7 \pmod{20}, \quad N \equiv 7 \pmod{42}, \quad N \equiv 7 \pmod{76}

Thus, N−7N - 7 must be a common multiple of 20, 42, and 76.

Find the prime factorizations:

  • 20=22×520 = 2^2 \times 5
  • 42=2×3×742 = 2 \times 3 \times 7
  • 76=22×1976 = 2^2 \times 19

The least common multiple is:

LCM(20,42,76)=22×3×5×7×19=4×15×133=60×133=7980\text{LCM}(20, 42, 76) = 2^2 \times 3 \times 5 \times 7 \times 19 = 4 \times 15 \times 133 = 60 \times 133 = 7980

The smallest natural number in the given choices is 7980+7=79877980 + 7 = 7987.

Final answer

C

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2018 Computer Science and Information Technology (CS)
Question
4 of 65, printed as GA Q.4
Section
General Aptitude

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.