A certain positive integer 'n' leaves a remainder of 2 when divided by 5 and a remainder of 3 when divided by 7. Which of the following could be the value of 'n'?
- A67
- B87
- C92
- D72
Show answer & explanationAnswer & explanation
Correct answer: B. 87
We are looking for an integer 'n' such that n ≡ 2 (mod 5) and n ≡ 3 (mod 7). This is a Chinese Remainder Theorem type problem. First, find the smallest such positive integer. From n ≡ 2 (mod 5), n can be 2, 7, 12, 17, 22, 27, 32, 37, 42, 47, 52, 57, 62, 67, 72, 77, 82, 87, 92, 97... From n ≡ 3 (mod 7), n can be 3, 10, 17, 24, 31, 38, 45, 52, 59, 66, 73, 80, 87, 94... The smallest common value is 17. The general form of 'n' will be 17 + k × LCM(5, 7). Since 5 and 7 are prime, LCM(5, 7) = 35. So, n = 17 + 35k. For k=0, n=17. For k=1, n=17+35 = 52. For k=2, n=17+70 = 87. For k=3, n=17+105 = 122. We are looking for 'n' between 50 and 100. The values are 52 and 87. Checking the options: A) 67: 67 mod 5 = 2 (correct), 67 mod 7 = 4 (incorrect, should be 3). B) 72: 72 mod 5 = 2 (correct), 72 mod 7 = 2 (incorrect, should be 3). C) 87: 87 mod 5 = 2 (correct), 87 mod 7 = 3 (correct). This matches. D) 92: 92 mod 5 = 2 (correct), 92 mod 7 = 1 (incorrect, should be 3). Thus, 87 is the correct answer.
Why the other options are wrong
- A. 67 leaves a remainder of 2 when divided by 5, but 4 when divided by 7.
- C. 92 leaves a remainder of 2 when divided by 5, but 1 when divided by 7.
- D. 72 leaves a remainder of 2 when divided by 5, but 2 when divided by 7.
Chinese Remainder Theorem (Basic Application)
A theorem that provides a unique solution (modulo the product of the moduli) to a system of simultaneous congruences with pairwise coprime moduli.
- Used to find an integer 'n' that satisfies multiple remainder conditions.
- If n ≡ a (mod m) and n ≡ b (mod k), where m and k are coprime, a unique solution exists modulo mk.
- One method involves listing numbers satisfying one condition and checking them against the other.
Memory trick: Find the pattern for one, then check for the other; the common step is key!