HMMT 十一月 2014 · GEN 赛 · 第 10 题

英文解析

10. Suppose that m and n are integers with 1 ≤ m ≤ 49 and n ≥ 0 such that m divides n + 1. Whatis the number of possible values of m ?
    n +1
    Answer: 29 If n is even, n + 1 | n + 1, so we can cover all odd m .
    n +1
    If m is even and m | n + 1, then n must be odd, so n + 1 is even, and m cannot be divisible by 4 orany prime congruent to 3 (mod 4). Conversely, if m/ 2 has all factors 1 (mod 4), then by CRT there
    2 N +1
    exists N ≡ 1 (mod 4) such that m | N + 1 | N + 1 (note ( N + 1) / 2 is odd).
    So the only bad numbers take the form 2 k , where 1 ≤ k ≤ 24 is divisible by at least one of
    2 , 3 , 7 , 11 , 19 , 23 , 31 , . . . . We count k = 2 , 4 , . . . , 24 (there are 12 numbers here), k = 3 , 9 , 15 , 21 (anotherfour), k = 7 , 11 , 19 , 23 (another four), giving a final answer of 49 − 12 − 4 − 4 = 29.
    General Test