2017 AIME II Problem 8

Attempt Problem 8 of the 2017 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2017 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

8.

Find the number of positive integers nn less than 20172017 such that 1+n+n22!+n33!+n44!+n55!+n66! \begin{aligned} &1 + n + \frac{n^2}{2!} + \frac{n^3}{3!} + \frac{n^4}{4!} \\ &{}+ \frac{n^5}{5!} + \frac{n^6}{6!} \end{aligned} is an integer.

Answer: 134
Concepts:divisibilitymodular arithmeticfactorialcasework
Difficulty rating: 2840
Solution:

Multiplying by 6!=720,6! = 720, the sum is an integer exactly when 720n6+6n5+30n4+120n3+360n2. \begin{aligned} &720 \mid n^6 + 6n^5 + 30n^4 \\ &{}+ 120n^3 + 360n^2. \end{aligned} If nn were odd, every term except n6n^6 would be even, making the total odd. If 3n,3 \nmid n, then modulo 33 every term except n6n^6 vanishes while n61(mod3).n^6 \equiv 1 \pmod 3. So nn must be a multiple of 6.6.

Write n=6k.n = 6k. Then 30n4=72054k4,30n^4 = 720 \cdot 54k^4, 120n3=72036k3,120n^3 = 720 \cdot 36k^3, and 360n2=72018k2360n^2 = 720 \cdot 18k^2 are all divisible by 720,720, while n6+6n5=66k5(k+1).n^6 + 6n^5 = 6^6 k^5(k + 1). Since 66=26366^6 = 2^6 3^6 supplies the factors 242^4 and 323^2 of 720=24325,720 = 2^4 \cdot 3^2 \cdot 5, the condition reduces to 5k(k+1),5 \mid k(k + 1), that is, k0k \equiv 0 or 4(mod5).4 \pmod 5.

For n=6k<2017n = 6k \lt 2017 we need 1k336.1 \le k \le 336. That range contains 6767 multiples of 55 and 6767 values with k4(mod5),k \equiv 4 \pmod 5, so there are 67+67=13467 + 67 = 134 such n.n.

← Problem 7#7
Full Exam

Problem 8 in Other Years