Maths Olympiad Prep

Library / /236 of 348

Number theory Difficulty 5.0 AIME, harder Find the answer

Find the number of integers nn with 1n20171 \leq n \leq 2017 so that (n2)(n0)(n1)(n7)(n-2)(n-0)(n-1)(n-7) is an integer multiple of 1001.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Note that 1001=711131001=7 \cdot 11 \cdot 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 nn modulo 11 for which the product is a multiple of 11; similarly, there are 4 possible residues of nn modulo 13 for which the product is a multiple of 13. However, there are only 3 possible residues of nn modulo 7 for which the product is a multiple of 7. Consider each of these 443=484 \cdot 4 \cdot 3=48 possible triples of remainders. By the Chinese Remainder Theorem there is exactly one value of nn with 1n10011 \leq n \leq 1001 achieving those remainders, and exactly one value of nn with 16n101616 \leq n \leq 1016 achieving those remainders. Similarly, there is exactly one value of nn with 1017n20171017 \leq n \leq 2017 with those same remainders. Hence there are 96 values of nn with 16n201716 \leq n \leq 2017 such that (n2)(n0)(n1)(n7)(n-2)(n-0)(n-1)(n-7) is a multiple of 1001. It remains to check n{1,2,3,,15}n \in\{1,2,3, \ldots, 15\}. Since the product must be a multiple of 7, we can narrow the set to {1,2,7,8,9,14}\{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 nn yield a product which is a multiple of 11. Hence, the final answer is 96+3=9996+3=99.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.