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?
A. 3047 B. 6047 C. 7987 D. 63847
GATE 2018 · General Aptitude · Factors · medium
Answer: The smallest natural number is 7987. Answer: C.
Rewrite the condition: Since N mod 20 = N mod 42 = N mod 76 = 7, we have 20 | (N-7), 42 | (N-7), 76 | (N-7). So (N - 7) must be a common multiple of 20, 42, and 76. The smallest such value is their LCM.
Prime factorize each divisor: 20 = 4 x 5 = 2^2 x 5. 42 = 2 x 21 = 2 x 3 x 7. 76 = 4 x 19 = 2^2 x 19.
Compute LCM(20, 42, 76): Primes involved: 2 (max power 2^2), 3 (max power 3^1), 5 (max power 5^1), 7 (max power 7^1), 19 (max power 19^1). LCM = 4 x 3 x 5 x 7 x 19 = 4 x 3 = 12; 12 x 5 = 60; 60 x 7 = 420; 420 x 19 = 7980.
Find the smallest N: The smallest natural number satisfying all three remainder conditions is N = 7980 + 7 = 7987.