Revision as of 12:05, 18 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 the 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

Solution 2 (w/ formula)

Let $m=n+5$ . Then we have $1^3+2^3+3^3+\cdots+(m-5)^3\equiv 17 \mod m$ $\left(\frac{(m-5)(m-4)}{2}\right)^2\equiv 17 \mod m$ $\frac{400}{4}\equiv 17 \mod m$ $332 \equiv 0 \mod m$ So, $m\in\{83,166,332\}$ . Testing, the cases, only $332$ fails. This leaves $78+161=\boxed{239}$ .

Solution 3 (Official MAA 1)

The sum of the cubes from 1 to $n$ is $1^3+2^3+\cdots+n^3=\frac{n^2(n+1)^2}{4}.$ For this to be equal to $(n+5)q+17$ for some integer $q$ , it must be that $n^2(n+1)^2=4(n+5)q+4\cdot 17,$ so $n^2(n+1)^2 \equiv 4 \cdot 17= 68\hskip-.2cm \pmod{n+5}.$ But $n^2(n+1)^2 \equiv (-5)^2(-4)^2 = 400 \pmod{n+5}.$ Thus $n^2(n+1)^2$ is congruent to both $68$ and $400,$ which implies that $n+5$ divides $400-68 = 332=2^2 \cdot 83$ . Because $n+5 > 17$ , the only choices for $n+5$ are $83, 166,$ and $332.$ Checking all three cases verifies that $n=78$ and $n=161$ work, but $n=327$ does not. The requested sum is $78+161 = 239$ .

Solution 4 (Official MAA 2)

The sum of the cubes of the integers from $1$ through $n$ is $\frac{n^2(n+1)^2}{4},$ which, when divided by $n+5$ , has quotient $Q=\frac14n^3 -\frac34n^2+4n-20 = \frac{n^2(n-3)}4+4n-20$ with remainder $100.$ If $n$ is not congruent to $1\pmod4$ , then $Q$ is an integer, and $\frac{n^2(n+1)^2}{4} = (n+5)Q + 100 \equiv 17\pmod{n+5},$ so $n+5$ divides $100 - 17 =83$ , and $n = 78$ . If $n \equiv 1 \pmod4$ , then $Q$ is half of an integer, and letting $n = 4k+1$ for some integer $k$ gives $\frac{n^2(n+1)^2}{4} = 2(2k+3)Q + 100 \equiv 17\pmod{n+5}.$ Thus $2k+3$ divides $100-17 = 83$ . It follows that $k=40$ , and $n = 161$ . The requested sum is $161 + 78 = 239$ .

Solution 5

Using the formula for $\sum_{k=1}^n n^3$ , $1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^2(n+1)^2}{4}$ Since $1^3 + 2^3 + 3^3 + ... + n^3$ divided by $n + 5$ has a remainder of $17$ , $\frac{n^2(n+1)^2}{4} \equiv 17\pmod {n + 5}$ Using the rules of modular arithmetic, $n^2(n+1)^2 \equiv 68\pmod {n + 5}$ $n^2(n+1)^2 - 68\equiv 0\pmod {n + 5}$ Expanding the left hand side, $n^4 + 2 n^3 + n^2 - 68\equiv 0\pmod {n + 5}$ This means that $n^4 + 2 n^3 + n^2 - 68$ is divisible by ${n + 5}$ .

$(n + 5) | (n^4 + 2 n^3 + n^2 - 68)$ Dividing polynomials, $\frac{n^4 + 2 n^3 + n^2 - 68}{n + 5}$ $= n^3 - 3 n^2 + 16n - 80 + \frac{332}{(n + 5)}$ $(n + 5)$ $|$ $(n^4 + 2 n^3 + n^2 - 68)$ $\iff$ $\frac{332}{(n + 5)}$ $\in$ $\mathbb{Z}$

$\frac{332}{(n + 5)}$ $\in$ $\mathbb{Z}$ $\iff$ $(n + 5) = \pm 1, \pm 2, \pm 4, \pm 83, \pm 166, \pm 332$

Note that $n$ $\in$ $\mathbb{N}$ and $n + 5 > 17$ (because the remainder when dividing by $n + 5$ is $17$ , so $n + 5$ must be greater than $17$ ), so all options $\leq 17$ can be eliminated. $(n + 5) = 83, 166, 332$ $n = 78, 161, 327$ Checking all 3 cases, $n = 78$ and $n = 161$ work; $n = 327$ fails.

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

~ {TSun} ~

Video Solution

https://youtu.be/bz5N-jI2e0U?t=201

@@ Line 93: / Line 93: @@
 <br><br>
 ~ {TSun} ~
-==Solution 6 (Basic Mods+Formula)==
-The formula for sum of cubes is <math>\frac{n^2(n+1)^2}{4}</math>. So now what we are trying to find is all solutions for <math>\frac{n^2(n+1)^2}{4}\equiv 17\pmod{n+5}</math>. First we multiply both sides by <math>4</math> since we want to get rid of the <math>4</math> on the denominator. This means we are now left with <math>n^2(n+1)^2\equiv 68\pmod{n+5}</math>. Notice that <math>n\equiv -5\pmod{n+5}</math>. If we now plug in <math>-5</math> for <math>n</math> we get <math>-5^2(-4)^2\equiv 68\pmod{n+5}</math>. Simplifying this get's us <math>400\equiv 68\pmod{n+5}</math> subtracting both sides by 68 leaves us with, <math>332\equiv 0\pmod{n+5}</math>. This now means that <math>n+5</math> is a factor of <math>332</math>. Factoring <math>332</math> gets us <math>332=2^2\cdot83</math> This means the factors of <math>332</math> are <math>1,2,4,83,166,332</math>. <math>1,2,4</math> We can see immediately do not work as <math>17>1,17>2,17>4</math>. This now means <math>n+5=83,166,332</math>. Checking these <math>3</math>, we find out that <math>83</math> and <math>166</math> work, but <math>332</math> doesn't. This means <math>n=78,161</math>. Therefore, the answer is <math>78 + 161 = \boxed{239}</math>
-~Bole
 ==Video Solution==
 https://youtu.be/bz5N-jI2e0U?t=201

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

Page

Toolbox

Search

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