HMMT 十一月 2017 · GEN 赛 · 第 3 题

HMMT November 2017 — GEN Round — Problem 3

Find the number of integers n with 1 ≤ n ≤ 2017 so that ( n − 2)( n − 0)( n − 1)( n − 7) is an integer multiple of 1001.

解析

Find the number of integers n with 1 ≤ n ≤ 2017 so that ( n − 2)( n − 0)( n − 1)( n − 7) is an integer multiple of 1001. Proposed by: Dhruv Rohatgi Answer: 99 Note that 1001 = 7 · 11 · 13, so the stated product must be a multiple of 7, as well as a multiple of 11, as well as a multiple of 13. There are 4 possible residues of n modulo 11 for which the product is a multiple of 11; similarly, there are 4 possible residues of n modulo 13 for which the product is a multiple of 13. However, there are only 3 possible residues of n modulo 7 for which the product is a multiple of 7. Consider each of these 4 · 4 · 3 = 48 possible triples of remainders. By the Chinese Remainder Theorem there is exactly one value of n with 1 ≤ n ≤ 1001 achieving those remainders, and exactly one value of n with 16 ≤ n ≤ 1016 achieving those remainders. Similarly, there is exactly one value of n with 1017 ≤ n ≤ 2017 with those same remainders. Hence there are 96 values of n with 16 ≤ n ≤ 2017 such that ( n − 2)( n − 0)( n − 1)( n − 7) is a multiple of 1001. It remains to check n ∈ { 1 , 2 , 3 , . . . , 15 } . Since the product must be a multiple of 7, we can narrow the set to { 1 , 2 , 7 , 8 , 9 , 14 } . The first 3 values work trivially, since the product is 0. It can be easily checked that none of the remaining values of n yield a product which is a multiple of 11. Hence, the final answer is 96 + 3 = 99.