Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2020 AIME II Problems/Problem 10"
(→‎Problem)
Line 1: Line 1:
 
= Problem =
 
= Problem =
 
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>.
 
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 ==
 +
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>.
 +
 +
We then notice that we can pair the <math>5^3</math> term with the <math>n^3</math> term to factor it into <math>(n+5)(n^2-5n+25)</math> using the sum of cubes formula, which is divisible by <math>n+5</math>. We can do the same for the <math>6^3</math> term with the <math>(n-1)^3</math> term, the <math>7^3</math> term with the <math>(n-2)^3</math>, and so on, which are all divisible by <math>n+5</math>. However, when <math>n</math> is odd, we will have a middle term that is not paired with any other terms, which is not necessarily divisible by <math>n+5</math>. Thus, we have two cases:
 +
 +
<math>\textbf{CASE 1: } n</math> is even
 +
If <math>n</math> is even, all terms that are greater than <math>4^3</math> pair, as there are an even number of terms that are greater than <math>4^3</math>. Therefore, all we need in order for the entire sequence to have a remainder of <math>17</math> when divided by <math>n+5</math> is <math>1^3+2^3+3^3+4^3</math> to have a remainder of <math>17</math> when divided by <math>n+5</math>.
 +
 +
Evaluating <math>1^3+2^3+3^3+4^3</math> as <math>100</math>, all we need to be true is
 +
<cmath>100\equiv 17\pmod {n+5},</cmath>
 +
or that
 +
<cmath>83\equiv 0\pmod {n+5}.</cmath>
 +
Thus, <math>83</math> will be divisible by <math>n+5</math> where <math>n\geq 13</math>. As <math>83</math> is prime, <math>n+5</math> must be equal to either <math>1</math> or <math>83</math>. If <math>n+5=1</math>, we have that <math>n=-4</math>, which is not greater than or equal to <math>13</math>, so that solution is extraneous.
 +
 +
If <math>n+5=83</math>, we have that <math>n=78</math>, which is <math>\geq 13</math>, so one of our solutions is <math>n=78</math>, and we are done with our first case.
 +
 +
<math>\textbf{CASE 2: } n</math> is odd
 +
If <math>n</math> 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 <math>(\frac{n+5}{2})^3</math>. Therefore, as all other terms that are <math>\geq 5^3</math> pair, the requirement that we have is
 +
<cmath>1^3+2^3+3^3+4^3+\left(\frac{n+5}{2}\right)^3\equiv 17\pmod {n+5}.</cmath>
 +
Calculating and simplifying, we have that
 +
<cmath>83+\left(\frac{n+5}{2}\right)^3\equiv 0\pmod {n+5}.</cmath>
 +
Now, we multiply both sides by <math>8</math>. 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
 +
<cmath>8\cdot 83+(n+5)^3\equiv 0\pmod {n+5}.</cmath>
 +
As we know that <math>(n+5)^3</math> is divisible by <math>n+5</math>, what we need now is
 +
<cmath>8\cdot 83\equiv 0\pmod {n+5}.</cmath>
 +
We now check each solution to see whether it works.
 +
 +
If <math>n+5=1, 2, 4, 8</math>, <math>n</math> would be less than <math>13</math>, so none of these solutions work. If <math>n+5=83</math>, <math>n</math> 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 <math>n+5=166</math>, <math>n+5=332</math>, or <math>n+5=664</math>. We plug these values into the congruence before we multiplied both sides by <math>8</math> to check.
 +
 +
If <math>n+5=166</math>, we would need
 +
<cmath>83+\left(\frac{166}{2}\right)^3\equiv 0\pmod {166}.</cmath>
 +
Calculating and factoring out <math>83</math>, we have that
 +
<cmath>83(1+83\cdot 83)\equiv 0\pmod {166}.</cmath>
 +
As the right parenthesis is odd and <math>166=83\cdot 2</math>, we know that this solution works, so we have another solution: <math>n=166-5=161</math>.
 +
 +
If <math>n+5=332</math>, we would need
 +
<cmath>83+\left(\frac{332}{2}\right)^3=83+166^3\equiv 0\pmod {322}.</cmath>
 +
As the left hand side is odd, but all multiples of <math>322</math> is even, this solution is therefore extraneous.
 +
 +
If <math>n+5=664</math>, we would need
 +
<cmath>83+\left(\frac{664}{2}\right)^3=83+332^3\equiv 0\pmod {664}.</cmath>
 +
Again, the left hand side is odd, and all multiples of <math>664</math> are even, so this solution is extraneous.
 +
 +
Therefore, our final answer is <math>78+161=\boxed{239}</math>.
 +
 +
~ CoolCarsOnTheRun

Revision as of 14:12, 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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_10&oldid=124264"