Problem

Find the number of positive integers $n$ less than $2017$ such that $1+n+\frac{n^2}{2!}+\frac{n^3}{3!}+\frac{n^4}{4!}+\frac{n^5}{5!}+\frac{n^6}{6!}$ is an integer.

Solution 1 (Not Rigorous)

Writing the last two terms with a common denominator, we have $\frac{6n^5+n^6}{720} \implies \frac{n^5(6+n)}{720}$ By inspection. this yields that $n \equiv 0, 24 \pmod{30}$ . Therefore, we get the final answer of $67 + 67 = \boxed{134}$ .

Solution 2

Taking out the $1+n$ part of the expression and writing the remaining terms under a common denominator, we get $\frac{1}{720}(n^6+6n^5+30n^4+120n^3+360n^2)$ . Therefore the expression $n^6+6n^5+30n^4+120n^3+360n^2$ must equal $720m$ for some positive integer $m$ . Taking both sides mod $2$ , the result is $n^6 \equiv 0 \pmod{2}$ . Therefore $n$ must be even. If $n$ is even, that means $n$ can be written in the form $2a$ where $a$ is a positive integer. Replacing $n$ with $2a$ in the expression, $64a^6+192a^5+480a^4+960a^3+1440a^2$ is divisible by $16$ because each coefficient is divisible by $16$ . Therefore, if $n$ is even, $n^6+6n^5+30n^4+120n^3+360n^2$ is divisible by $16$ .

Taking the equation $n^6+6n^5+30n^4+120n^3+360n^2=720m$ mod $3$ , the result is $n^6 \equiv 0 \pmod{3}$ . Therefore $n$ must be a multiple of $3$ . If $n$ is a multiple of three, that means $n$ can be written in the form $3b$ where $b$ is a positive integer. Replacing $n$ with $3b$ in the expression, $729b^6+1458b^5+2430b^4+3240b^3+3240b^2$ is divisible by $9$ because each coefficient is divisible by $9$ . Therefore, if $n$ is a multiple of $3$ , $n^6+6n^5+30n^4+120n^3+360n^2$ is divisibly by $9$ .

Taking the equation $n^6+6n^5+30n^4+120n^3+360n^2=720m$ mod $5$ , the result is $n^6+n^5 \equiv 0 \pmod{5}$ . The only values of $n (\text{mod }5)$ that satisfy the equation are $n\equiv0(\text{mod }5)$ and $n\equiv4(\text{mod }5)$ . Therefore if $n$ is $0$ or $4$ mod $5$ , $n^6+6n^5+30n^4+120n^3+360n^2$ will be a multiple of $5$ .

The only way to get the expression $n^6+6n^5+30n^4+120n^3+360n^2$ to be divisible by $720=16 \cdot 9 \cdot 5$ is to have $n \equiv 0 \pmod{2}$ , $n \equiv 0 \pmod{3}$ , and $n \equiv 0 \text{ or } 4 \pmod{5}$ . By the Chinese Remainder Theorem or simple guessing and checking, we see $n\equiv0,24 \pmod{30}$ . Because no numbers between $2011$ and $2017$ are equivalent to $0$ or $24$ mod $30$ , the answer is $\frac{2010}{30}\times2=\boxed{134}$ .

Solution 3

Note that $1+n+\frac{n^2}{2!}+\frac{n^3}{3!}+\frac{n^4}{4!}+\frac{n^5}{5!}$ will have a denominator that divides $5!$ . Therefore, for the expression to be an integer, $\frac{n^6}{6!}$ must have a denominator that divides $5!$ . Thus, $6\mid n^6$ , and $6\mid n$ . Let $n=6m$ . Substituting gives $1+6m+\frac{6^2m^2}{2!}+\frac{6^3m^3}{3!}+\frac{6^4m^4}{4!}+\frac{6^5m^5}{5!}+\frac{6^6m^6}{6!}$ . Note that the first $5$ terms are integers, so it suffices for $\frac{6^5m^5}{5!}+\frac{6^6m^6}{6!}$ to be an integer. This simplifies to $\frac{6^5}{5!}m^5(m+1)=\frac{324}{5}m^5(m+1)$ . It follows that $5\mid m^5(m+1)$ . Therefore, $m$ is either $0$ or $4$ modulo $5$ . However, we seek the number of $n$ , and $n=6m$ . By CRT, $n$ is either $0$ or $24$ modulo $30$ , and the answer is $67+67=\boxed{134}$ .

2017 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 7	Followed by Problem 9
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2017 AIME II Problems/Problem 8

Contents

Problem

Solution 1 (Not Rigorous)

Solution 2

Solution 3

See Also