Remainder 1 with every divisor, but divisible by 13
Remainder 1 with every divisor, but divisible by 13: Find the least number which, when divided by 6, 7, 8, 9 and… Answer and worked solution on CodeKairo.
- Topic: Number System
- Section: Quantitative Aptitude
- Difficulty: Hard
- Time target: 150 seconds
Question
Find the least number which, when divided by 6, 7, 8, 9 and 10, leaves a remainder of 1 in each case, but is exactly divisible by 13.
Options
- 3361
- 10081
- 17641
- 25201
Show the answer and the worked solution
Correct answer: C. 17641
Worked solution
- LCM(6, 7, 8, 9, 10) = 2520, so the number is of the form 2520k + 1.
- 2520 = 13 × 193 + 11, so 2520k + 1 ≡ 11k + 1 (mod 13).
- Need 11k + 1 ≡ 0, i.e. 11k ≡ 12 (mod 13). Testing k = 1, 2, 3 … gives k = 7 (11 × 7 = 77 = 65 + 12 ✓).
- The number is 2520 × 7 + 1 = 17641, and 17641 ÷ 13 = 1357. ✓
Answer: 17641.
The idea
Two conditions, two steps: the 'same remainder' condition fixes the form LCM·k + r, and the divisibility condition fixes k. Testing k = 1, 2, 3 … against the second condition is quicker than any formal congruence work at this size.
Shortcut. Each answer must be 2520k + 1. 3361 fails at once (3360 has digit sum 12, so 9 does not divide it). Divide the rest by 13 from the smallest: 10081 leaves 6, and 17641 = 13 × 1357.
Common trap. 3361 — 3360 is divisible by 6, 7, 8 and 10, so it survives a check that skips 9; it also leaves 7 on division by 13.