# 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 15:12, 7 June 2020

# Problem

Find the sum of all positive integers such that when is divided by , the remainder is .

## Solution 1

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

We then notice that we can pair the term with the term to factor it into using the sum of cubes formula, which is divisible by . We can do the same for the term with the term, the term with the , and so on, which are all divisible by . However, when is odd, we will have a middle term that is not paired with any other terms, which is not necessarily divisible by . Thus, we have two cases:

is even If is even, all terms that are greater than pair, as there are an even number of terms that are greater than . Therefore, all we need in order for the entire sequence to have a remainder of when divided by is to have a remainder of when divided by .

Evaluating as , all we need to be true is or that Thus, will be divisible by where . As is prime, must be equal to either or . If , we have that , which is not greater than or equal to , so that solution is extraneous.

If , we have that , which is , so one of our solutions is , and we are done with our first case.

is odd If 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 . Therefore, as all other terms that are pair, the requirement that we have is Calculating and simplifying, we have that Now, we multiply both sides by . 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 As we know that is divisible by , what we need now is We now check each solution to see whether it works.

If , would be less than , so none of these solutions work. If , 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 , , or . We plug these values into the congruence before we multiplied both sides by to check.

If , we would need Calculating and factoring out , we have that As the right parenthesis is odd and , we know that this solution works, so we have another solution: .

If , we would need As the left hand side is odd, but all multiples of is even, this solution is therefore extraneous.

If , we would need Again, the left hand side is odd, and all multiples of are even, so this solution is extraneous.

Therefore, our final answer is .

~ CoolCarsOnTheRun