2020 AIME II Problems/Problem 10
Contents
Problem
Find the sum of all positive integers such that when
is divided by
, the remainder is
.
Solution 1 (If you don't remember the formula for sum of cubes)
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 two 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
Solution 2 (w/ formula)
Let . Then we have
So,
. Testing, the cases, only
fails. This leaves
.
Solution 3 (Official MAA 1)
The sum of the cubes from 1 to is
For this to be equal to
for some integer
, it must be that
so
But
Thus
is congruent to both
and
which implies that
divides
. Because
, the only choices for
are
and
Checking all three cases verifies that
and
work, but
does not. The requested sum is
.
Solution 4 (Official MAA 2)
The sum of the cubes of the integers from through
is
which, when divided by
, has quotient
with remainder
If
is not congruent to
, then
is an integer, and
so
divides
, and
. If
, then
is half of an integer, and letting
for some integer
gives
Thus
divides
. It follows that
, and
. The requested sum is
.
Solution 5
Using the formula for ,
Since
divided by
has a remainder of
,
Using the rules of modular arithmetic,
Expanding the left hand side,
This means that
is divisible by
.
Dividing polynomials,
Note that
and
(because the remainder when dividing by
is
, so
must be greater than
), so all options
can be eliminated.
Checking all 3 cases,
and
work;
fails.
Therefore, the answer is .
~ {TSun} ~
Solution 6 (similar ideas to Solution 1, but faster)
As before, we note that
Thus, we can pair up the terms from
to
and cancel them. We have to deal with two cases:
If is even, then
as there are an even number of terms and they pair and cancel. We thus get
or
which yields
If is odd, then
Letting
yields
However, this means that
is divisible by
so
Plugging this back into
yields
in the latter case.
Thus, the sum of all possible is just
- ccx09
Video solution
https://www.youtube.com/watch?v=87Mp0cdUtCU ~ North America Math Contest Go Go Go
Video Solution
https://youtu.be/bz5N-jI2e0U?t=201
See Also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.