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

HMMT November 2014 — GEN Round — Problem 10

Suppose that m and n are integers with 1 ≤ m ≤ 49 and n ≥ 0 such that m divides n + 1. What is the number of possible values of m ?

解析

Suppose that m and n are integers with 1 ≤ m ≤ 49 and n ≥ 0 such that m divides n + 1. What is 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 or any 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 (another four), k = 7 , 11 , 19 , 23 (another four), giving a final answer of 49 − 12 − 4 − 4 = 29. General Test