2011 AIME I Problems/Problem 11
Let be the set of all possible remainders when a number of the form , a nonnegative integer, is divided by 1000. Let be the sum of the elements in . Find the remainder when is divided by 1000.
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.
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,
Obviously, will have to repeat at some point, and our goal is just to find when it repeats. Suppose is the first time the powers of 2 repeat mod 1000, and that it is the same as where We have We can factor out a to get Now, let's apply CRT. Obviously, if it is 0 mod 1000, this means directly that it is 0 mod 8 and 0 mod 125. Since has to be odd, this necessarily means for This means that 125 has to divide We wish to find the minimum such that this is true, or similarly, we just wish to find Note that by Euler's Totient Theorem, that After checking, and seeing that , this directly means that or Since , the smallest pair is What this really means is that the sequence of remainders will start repeating at or namely that are all distinct residues mod 1000. Adding these yields
Solution 4 (Not rigorous)
If we write out the remainders when powers of are divided by , we must eventually write a number we have already written down. After this happens, we will fall into a cycle, and thus, nothing new will be written down.
The answer extraction of the problem is equivalent to asking for , where is the first number whose remainder when divided by is a repeat. This expression is equivalent to . So our answer will just be the first repeated remainder minus .
(Everything up to this point has been perfectly rigorous; now, we will destroy this.)
Note that , and cannot be the first repeated remainders, due to the , and divisibility rules, respectively (i.e. , and are the only powers of that leave a remainder of , and , respectively, when divided by .) There is no reason why could not be the first repeated remainder, so it probably is. Thus, our answer is . (In fact, one can quite easily show that if reappears at all in the sequence, it must be the first repeated remainder.)
Solution 5 (Very bad idea)
We can simply list out the last digits of all the powers of until we find a pattern.
Note: This solution is very tedious and should not be used unless there is enough remaining time and you can't think of any other way
We can see that after comes which can be written as . That means that all the terms after will repeat but negated modulo . Note that . As we are looking for the sum of all of the possible values mod , the answer is just
|2011 AIME I (Problems • Answer Key • Resources)
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
|All AIME Problems and Solutions