Revision as of 15:07, 7 June 2020

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 (If you don't remember formula for sum of cubes)

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

@@ Line 2: / Line 2: @@
 Find the sum of all positive integers <math>n</math> such that when <math>1^3+2^3+3^3+\cdots +n^3</math> is divided by <math>n+5</math>, the remainder is <math>17</math>.
-== Solution 1 ==
+== Solution 1 (If you don't remember formula for sum of cubes) ==
 We first note that since the remainder is <math>17</math> and we are dividing by <math>n+5</math>, <math>n+5</math> must be greater than <math>17</math>, meaning that <math>n</math> has to be at least <math>13</math>.

Page

Toolbox

Search

Difference between revisions of "2020 AIME II Problems/Problem 10"

Revision as of 15:07, 7 June 2020

Problem

Solution 1 (If you don't remember formula for sum of cubes)