2020 AIME II Problems/Problem 10

Revision as of 15:15, 7 June 2020 by CoolCarsOnTheRun (talk | contribs) (Problem)

Problem

Find the sum of all positive integers $n$ such that when $1^3+2^3+3^3+\cdots +n^3$ is divided by $n+5$, the remainder is $17$.

Solution 1

We first note that since the remainder is $17$ and we are dividing by $n+5$, $n+5$ must be greater than $17$, meaning that $n$ has to be at least $13$.

We then notice that we can pair the $5^3$ term with the $n^3$ term to factor it into $(n+5)(n^2-5n+25)$ using the sum of cubes formula, which is divisible by $n+5$. We can do the same for the $6^3$ term with the $(n-1)^3$ term, the $7^3$ term with the $(n-2)^3$, and so on, which are all divisible by $n+5$. However, when $n$ is odd, we will have a middle term that is not paired with any other terms, which is not necessarily divisible by $n+5$. Thus, we have two cases:

$\textbf{CASE 1: } n$ is even
If $n$ is even, all terms that are greater than $4^3$ pair, as there are an even number of terms that are greater than $4^3$. Therefore, all we need in order for the entire sequence to have a remainder of $17$ when divided by $n+5$ is $1^3+2^3+3^3+4^3$ to have a remainder of $17$ when divided by $n+5$.

Evaluating $1^3+2^3+3^3+4^3$ as $100$, all we need to be true is \[100\equiv 17\pmod {n+5},\] or that \[83\equiv 0\pmod {n+5}.\] Thus, $83$ will be divisible by $n+5$ where $n\geq 13$. As $83$ is prime, $n+5$ must be equal to either $1$ or $83$. If $n+5=1$, we have that $n=-4$, which is not greater than or equal to $13$, so that solution is extraneous.

If $n+5=83$, we have that $n=78$, which is $\geq 13$, so one of our solutions is $n=78$, and we are done with our first case.

$\textbf{CASE 2: } n$ is odd If $n$ is odd, the only term that does not pair is the arithmetic mean of the numbers under the cube of the largest and smallest terms that would pair, or $(\frac{n+5}{2})^3$. Therefore, as all other terms that are $\geq 5^3$ pair, the requirement that we have is \[1^3+2^3+3^3+4^3+\left(\frac{n+5}{2}\right)^3\equiv 17\pmod {n+5}.\] Calculating and simplifying, we have that \[83+\left(\frac{n+5}{2}\right)^3\equiv 0\pmod {n+5}.\] Now, we multiply both sides by $8$. However, since multiplication is not reversible in modular arithmetic, we need to check whether any solutions are extraneous after solving. The congruence that we now have is \[8\cdot 83+(n+5)^3\equiv 0\pmod {n+5}.\] As we know that $(n+5)^3$ is divisible by $n+5$, what we need now is \[8\cdot 83\equiv 0\pmod {n+5}.\] We now check each solution to see whether it works.

If $n+5=1, 2, 4, 8$, $n$ would be less than $13$, so none of these solutions work. If $n+5=83$, $n$ would be even, so that solution does not work for this case. Therefore, the only three solutions we need to check for this case are when $n+5=166$, $n+5=332$, or $n+5=664$. We plug these values into the congruence before we multiplied both sides by $8$ to check.

If $n+5=166$, we would need \[83+\left(\frac{166}{2}\right)^3\equiv 0\pmod {166}.\] Calculating and factoring out $83$, we have that \[83(1+83\cdot 83)\equiv 0\pmod {166}.\] As the right parenthesis is odd and $166=83\cdot 2$, we know that this solution works, so we have another solution: $n=166-5=161$.

If $n+5=332$, we would need \[83+\left(\frac{332}{2}\right)^3=83+166^3\equiv 0\pmod {322}.\] As the left hand side is odd, but all multiples of $322$ is even, this solution is therefore extraneous.

If $n+5=664$, we would need \[83+\left(\frac{664}{2}\right)^3=83+332^3\equiv 0\pmod {664}.\] Again, the left hand side is odd, and all multiples of $664$ are even, so this solution is extraneous.

Therefore, our final answer is $78+161=\boxed{239}$.

~ CoolCarsOnTheRun