Find the smallest positive number N such that: • N leaves remainder 4 when divided by each of 16, 18, and 20; and • N is exactly divisible by 7.

Difficulty: Medium

Correct Answer: 2884

Explanation:


Introduction / Context:
This is a linear congruence with a divisibility constraint. A number that leaves the same remainder r with several moduli is congruent to r modulo the LCM of those moduli. Then, impose the divisibility requirement to select the least positive solution.


Given Data / Assumptions:

  • N ≡ 4 (mod 16), N ≡ 4 (mod 18), N ≡ 4 (mod 20).
  • N is divisible by 7.


Concept / Approach:
First, compute L = LCM(16, 18, 20). All solutions to the congruences are N = L*k + 4 for integer k ≥ 0. Then choose the smallest k for which N is a multiple of 7. Use modular arithmetic to solve (L*k + 4) ≡ 0 (mod 7).


Step-by-Step Solution:

Prime factors: 16 = 2^4; 18 = 2*3^2; 20 = 2^2*5.LCM L = 2^4 * 3^2 * 5 = 16 * 9 * 5 = 720.General solution: N = 720k + 4.Impose N ≡ 0 (mod 7): 720k + 4 ≡ 0 (mod 7). Since 720 ≡ 6 (mod 7), we need 6k + 4 ≡ 0 ⇒ 6k ≡ 3 (mod 7).Multiply both sides by 6 (inverse of 6 mod 7): k ≡ 18 ≡ 4 (mod 7).Least nonnegative k = 4 ⇒ N = 720*4 + 4 = 2884.


Verification / Alternative check:

Check: 2884 ÷ 16 leaves 4, ÷ 18 leaves 4, ÷ 20 leaves 4; and 2884 ÷ 7 = 412 exactly.


Why Other Options Are Wrong:

  • 2256, 865, 3332 fail either the remainder condition or the divisibility-by-7 condition (or both).


Common Pitfalls:

  • Losing track of the LCM or using some but not all moduli in forming L.


Final Answer:

2884

More Questions from Problems on H.C.F and L.C.M

Discussion & Comments

No comments yet. Be the first to comment!
Join Discussion