Difference between revisions of "2011 AIME I Problems/Problem 11"
m (→Solution 3 (Fake-ish)) |
|||
Line 41: | Line 41: | ||
After listing out a few remainders of numbers of the form <math>2^i</math>, namely <math>1, 2, 4, 8, 16, 64, 128, 512, 024, 048...</math>, we can guess that, except for the first <math>3</math>, the remainder will hit every multiple of <math>8</math> between <math>8</math> and <math>992</math>, inclusive. This means that our sum is of the form <math>1 + 2 + 4 + 8(1+2+...+124)</math>. This can be written as | After listing out a few remainders of numbers of the form <math>2^i</math>, namely <math>1, 2, 4, 8, 16, 64, 128, 512, 024, 048...</math>, we can guess that, except for the first <math>3</math>, the remainder will hit every multiple of <math>8</math> between <math>8</math> and <math>992</math>, inclusive. This means that our sum is of the form <math>1 + 2 + 4 + 8(1+2+...+124)</math>. This can be written as | ||
<math>1 + 2 + 4 + 8(\frac{124\cdot125}{2}) = 7+4(124\cdot125)</math>. Since the, last term, <math>4(124\cdot125)</math>, is divisible by <math>1000</math> it's remainder is <math>0</math>. Thus the total remainder is just <math>1+2+4 = \boxed{007}.</math> | <math>1 + 2 + 4 + 8(\frac{124\cdot125}{2}) = 7+4(124\cdot125)</math>. Since the, last term, <math>4(124\cdot125)</math>, is divisible by <math>1000</math> it's remainder is <math>0</math>. Thus the total remainder is just <math>1+2+4 = \boxed{007}.</math> | ||
+ | |||
+ | == Solution 4 == | ||
+ | We know <math>1, 2,</math> and <math>4</math> are in <math>R</math>. Any other element in <math>R</math> must be a multiple of <math>8</math>. All multiples of <math>8</math> under <math>1000</math> sum up to a multiple of <math>1000</math>. So we can ignore them. We need to remove all multiples of <math>5</math>, or <math>40</math> in what we counted because all elements of <math>R</math> can only be divisible by <math>2</math>. But, their sum is also a multiple of <math>1000</math>. Likewise, the sum of all multiples of <math>8k</math> for some <math>k</math> will be a multiple of <math>1000</math>. Thus, our answer is <math>1+2+4=\boxed{007}</math>. | ||
+ | |||
+ | Solution by TheUltimate123 | ||
== See also == | == See also == | ||
{{AIME box|year=2011|n=I|num-b=10|num-a=12}} | {{AIME box|year=2011|n=I|num-b=10|num-a=12}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 22:26, 2 March 2017
Problem
Let be the set of all possible remainders when a number of the form
,
a nonnegative integer, is divided by
. Let
be the sum of the elements in
. Find the remainder when
is divided by
.
Solution 1
Note that and
. So we must find the first two integers
and
such that
and
and
. Note that
and
will be greater than 2 since remainders of
will not be possible after 2 (the numbers following will always be congruent to 0 modulo 8). Note that
(see Euler's theorem) and
are all distinct modulo 125 (proof below). Thus,
and
are the first two integers such that
. All that is left is to find
in mod
. After some computation:
To show that
are distinct modulo 125, suppose for the sake of contradiction that they are not. Then, we must have at least one of
or
. However, writing
, we can easily verify that
and
, giving us the needed contradiction.
Solution 2
Notice that our sum of remainders looks like We want to find the remainder of
upon division by
Since
decomposes into primes as
, we can check the remainders of
modulo
and modulo
separately.
Checking modulo
is easy, so lets start by computing the remainder of
upon division by
To do this, let's figure out when our sequence finally repeats.
Notice that since the remainder when dividing any term of
(after the third term) by
will be a multiple of
, when this summation finally repeats, the first term to repeat will be not be
since
Instead, the first term to repeat will be
, and then the sequence will continue once again
Now, to compute modulo
, we want to find the least positive integer
such that
since then
will just be the number of terms of
(after the third term!) before the sequence repeats. In other words, our sequence will be of the form
and then we will have
, and the sequence will repeat from there. Here,
simply represents the order of
modulo
, denoted by
To begin with, we'll use a well-known property of the order to get a bound on
Since and
, we know by Euler's Theorem that
However, we do not know that
is the least
satisfying
Nonetheless, it is a well known property of the order that
Therefore, we can conclude that
must be a positive divisor of
Now, this still leaves a lot of possibilities, so let's consider a smaller modulus for the moment, say Clearly, we must have that
Since
and powers of two will then cycle every four terms, we know that
Combining this relation with
, it follows that
Now, it is trivial to verify that In addition, we know that
Therefore, we conclude that
Hence, we must have
(Notice that we could have guessed this by Euler's, but we couldn't have been certain without investigating the order more thoroughly).
Now, since we have found , we know that
There are two good ways to finish from here:
The first way is to use a trick involving powers of Notice that
Certainly
In addition, since we already computed
, we know that
Therefore, since
and
, we conclude that
The second way is not as slick, but works better in a general setting when there aren't any convenient tricks as in Method 1. Let us split the terms of into groups:
It is easy to see that
is congruent to
modulo
Now, for , notice that there are
terms in the summation, each with a different remainder upon division by
Since each of these remainders is certainly relatively prime to
, these
remainders correspond to the
positive integers less than
that are relatively prime to
Therefore,
Then, since
is divisible by
and
, it follows that
is divisible by
Therefore,
Solution 3 (Fake-ish)
After listing out a few remainders of numbers of the form , namely
, we can guess that, except for the first
, the remainder will hit every multiple of
between
and
, inclusive. This means that our sum is of the form
. This can be written as
. Since the, last term,
, is divisible by
it's remainder is
. Thus the total remainder is just
Solution 4
We know and
are in
. Any other element in
must be a multiple of
. All multiples of
under
sum up to a multiple of
. So we can ignore them. We need to remove all multiples of
, or
in what we counted because all elements of
can only be divisible by
. But, their sum is also a multiple of
. Likewise, the sum of all multiples of
for some
will be a multiple of
. Thus, our answer is
.
Solution by TheUltimate123
See also
2011 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 10 |
Followed by Problem 12 | |
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.