Difference between revisions of "2011 AIME I Problems/Problem 11"
(Tag: Undo) |
|||
Line 1: | Line 1: | ||
− | =Problem= | + | == Problem == |
− | Let <math>R</math> be the set of all possible remainders when a number | + | Let <math>R</math> be the set of all possible remainders when a number <math>2^n</math>, <math>n</math> a nonnegative integer, is divided by <math>1000</math>. Let <math>S</math> be the sum of the elements in <math>R</math>. Find the remainder when <math>S</math> is divided by <math>1000</math>. |
− | =Solution 1= | + | == Solution 1 == |
− | |||
− | + | Note that the invariance of <math>R \subseteq \mathbb Z_{1000}</math> upon multiplication by <math>2</math> implies the invariance of <math>R \setminus \{1, 2, 4\}</math> as <math>2^n \equiv 0 \mod{8}</math> for <math>n \ge 3.</math> Thus, letting the sum of the residues less <math>1, 2, 4</math> be <math>S',</math> we have <math>2S' \equiv S' \mod{1000} \Rightarrow S' \equiv 0 \mod{1000},</math> from which <math>S = S' + 1 + 2 + 4 \equiv \boxed{007} \mod{1000}</math> follows. | |
− | |||
− | Checking <math>S</math> modulo <math>2^3</math> is easy, so lets start by computing the remainder of <math>S</math> upon division by <math>5^3.</math> To do this, let's figure out when our sequence finally repeats. Notice that since the remainder when dividing any term of <math>S</math> (after the third term) by <math>1000</math> will be a multiple of <math>2^3</math>, when this summation finally repeats, the first term to repeat will be not be <math>1</math> since <math>2^3 \nmid 1.</math> Instead, the first term to repeat will be <math>2^3</math>, and then the sequence will continue once again <math>2^4, 2^5, \cdots.</math> | + | == Solution 2== |
+ | Note that <math>x \equiv y \pmod{1000} \Leftrightarrow x \equiv y \pmod{125}</math> and <math>x \equiv y \pmod{8}</math>. So we must find the first two integers <math>i</math> and <math>j</math> such that <math>2^i \equiv 2^j \pmod{125}</math> and <math>2^i \equiv 2^j \pmod{8}</math> and <math>i \neq j</math>. Note that <math>i</math> and <math>j</math> will be greater than 2 since remainders of <math>1, 2, 4</math> will not be possible after 2 (the numbers following will always be congruent to 0 modulo 8). Note that <math>2^{100}\equiv 1\pmod{125}</math> (see [[Euler's Totient Theorem|Euler's theorem]]) and <math>2^0,2^1,2^2,\ldots,2^{99}</math> are all distinct modulo 125 (proof below). Thus, <math>i = 103</math> and <math>j =3</math> are the first two integers such that <math>2^i \equiv 2^j \pmod{1000}</math>. All that is left is to find <math>S</math> in mod <math>1000</math>. After some computation: | ||
+ | <cmath> | ||
+ | S = 2^0+2^1+2^2+2^3+2^4+...+2^{101}+ 2^{102} = 2^{103}-1 \equiv 8 - 1 \mod 1000 = \boxed{007}. | ||
+ | </cmath> | ||
+ | To show that <math>2^0, 2^1,\ldots, 2^{99}</math> are distinct modulo 125, suppose for the sake of contradiction that they are not. Then, we must have at least one of <math>2^{20}\equiv 1\pmod{125}</math> or <math>2^{50}\equiv 1\pmod{125}</math>. However, writing <math>2^{10}\equiv 25 - 1\pmod{125}</math>, we can easily verify that <math>2^{20}\equiv -49\pmod{125}</math> and <math>2^{50}\equiv -1\pmod{125}</math>, giving us the needed contradiction. | ||
+ | |||
+ | == Solution 3 (Euler's theorem) == | ||
+ | Notice that our sum of remainders looks like <cmath>S = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + \cdots.</cmath> We want to find the remainder of <math>S</math> upon division by <math>1000.</math> Since <math>1000</math> decomposes into primes as <math>1000 = 2^3 \cdot 5^3</math>, we can check the remainders of <math>S</math> modulo <math>2^3</math> and modulo <math>5^3</math> separately. | ||
+ | |||
+ | Checking <math>S</math> modulo <math>2^3</math> is easy, so lets start by computing the remainder of <math>S</math> upon division by <math>5^3.</math> To do this, let's figure out when our sequence finally repeats. | ||
+ | Notice that since the remainder when dividing any term of <math>S</math> (after the third term) by <math>1000</math> will be a multiple of <math>2^3</math>, when this summation finally repeats, the first term to repeat will be ''not'' be <math>1</math> since <math>2^3 \nmid 1.</math> Instead, the first term to repeat will be <math>2^3</math>, and then the sequence will continue once again <math>2^4, 2^5, \cdots.</math> | ||
Now, to compute <math>S</math> modulo <math>125</math>, we want to find the least positive integer <math>d</math> such that <math>2^d \equiv 1 \pmod {125}</math> since then <math>d</math> will just be the number of terms of <math>S</math> (after the third term!) before the sequence repeats. In other words, our sequence will be of the form <math>S = 1 + 2 + 4 + \left(2^3 + 2^4 + \cdots + 2^{2 + d}\right)</math> and then we will have <math>2^{d + 3} \equiv 2^3 \pmod {125}</math>, and the sequence will repeat from there. Here, <math>d</math> simply represents the order of <math>2</math> modulo <math>125</math>, denoted by <math>d = \text{ord}_{125}(2).</math> To begin with, we'll use a well-known property of the order to get a bound on <math>d.</math> | Now, to compute <math>S</math> modulo <math>125</math>, we want to find the least positive integer <math>d</math> such that <math>2^d \equiv 1 \pmod {125}</math> since then <math>d</math> will just be the number of terms of <math>S</math> (after the third term!) before the sequence repeats. In other words, our sequence will be of the form <math>S = 1 + 2 + 4 + \left(2^3 + 2^4 + \cdots + 2^{2 + d}\right)</math> and then we will have <math>2^{d + 3} \equiv 2^3 \pmod {125}</math>, and the sequence will repeat from there. Here, <math>d</math> simply represents the order of <math>2</math> modulo <math>125</math>, denoted by <math>d = \text{ord}_{125}(2).</math> To begin with, we'll use a well-known property of the order to get a bound on <math>d.</math> | ||
− | Since <math>\gcd(2, 125) = 1</math> and <math>\phi(125) = 100</math>, we know by Euler's Theorem that <math>2^{100} \equiv 1 \pmod {125}.</math> However, we do not know that <math>100</math> is the least <math>d</math> satisfying <math>2^d \equiv 1 \pmod {125}.</math> Nonetheless, it is a well known property of the order that <math>\text{ord}_{125}(2) = d | \phi(125) = 100.</math> Therefore, we can conclude that <math>d</math> must be a positive divisor of <math>100.</math> | + | Since <math>\gcd(2, 125) = 1</math> and <math>\phi(125) = 100</math>, we know by Euler's Theorem that <math>2^{100} \equiv 1 \pmod {125}.</math> However, we do not know that <math>100</math> is the ''least'' <math>d</math> satisfying <math>2^d \equiv 1 \pmod {125}.</math> Nonetheless, it is a well known property of the order that <math>\text{ord}_{125}(2) = d | \phi(125) = 100.</math> Therefore, we can conclude that <math>d</math> must be a positive divisor of <math>100.</math> |
− | Now, this still leaves a lot of possibilities, so let's consider a smaller modulus for the moment, say <math>\mod 5.</math> Clearly, we must have that <math>2^d \equiv 1 \pmod 5.</math> Since <math>2^4 \equiv 1 \pmod 5</math> and powers of two will then cycle every four terms, we know that <math>2^d \equiv 1 \pmod 5 \iff 4 | d.</math> Combining this relation with <math>d | 100</math>, it follows that <math>d \in \{4, 20, 100\}.</math> | + | Now, this still leaves a lot of possibilities, so let's consider a smaller modulus for the moment, say <math>\mod 5.</math> Clearly, we must have that <math>2^d \equiv 1 \pmod 5.</math> Since <math>2^4 \equiv 1 \pmod 5</math> and powers of two will then cycle every four terms, we know that <math>2^d \equiv 1 \pmod 5 \iff 4 | d.</math> Combining this relation with <math>d | 100</math>, it follows that <math>d \in \{4, 20, 100\}.</math> |
Now, it is trivial to verify that <math>d \ne 4.</math> In addition, we know that <cmath>2^{20} = \left(2^{10}\right)^2 = \left(1024\right)^2 \equiv 24^2 = 576 \not\equiv 1 \pmod {125}.</cmath> Therefore, we conclude that <math>d \ne 20.</math> Hence, we must have <math>d = 100.</math> (Notice that we could have guessed this by Euler's, but we couldn't have been certain without investigating the order more thoroughly). | Now, it is trivial to verify that <math>d \ne 4.</math> In addition, we know that <cmath>2^{20} = \left(2^{10}\right)^2 = \left(1024\right)^2 \equiv 24^2 = 576 \not\equiv 1 \pmod {125}.</cmath> Therefore, we conclude that <math>d \ne 20.</math> Hence, we must have <math>d = 100.</math> (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 <math>d = 100</math>, we know that <cmath>S = 1 + 2 + 4 + 2^3 + 2^4 + \cdots + 2^{102}.</cmath> There are two good ways to finish from here: | + | Now, since we have found <math>d = 100</math>, we know that <cmath>S = 1 + 2 + 4 + 2^3 + 2^4 + \cdots + 2^{102}.</cmath> There are two good ways to finish from here: |
The first way is to use a trick involving powers of <math>2.</math> Notice that <cmath>S = 1 + 2 + 4 + ... + 2^{102} = 2^{103} - 1.</cmath> Certainly <cmath>S = 2^{103} - 1 \equiv -1 \equiv 7 \pmod {8}.</cmath> In addition, since we already computed <math>\text{ord}_{125}(2) = d = 100</math>, we know that <cmath>S = 2^{103} - 1 = 2^{100} \cdot 2^3 - 1 \equiv 2^3 - 1 \equiv 7 \pmod {125}.</cmath> Therefore, since <math>S \equiv 7 \pmod{8}</math> and <math>S \equiv 7 \pmod{125}</math>, we conclude that <math>S \equiv \boxed{007} \pmod {1000}.</math> | The first way is to use a trick involving powers of <math>2.</math> Notice that <cmath>S = 1 + 2 + 4 + ... + 2^{102} = 2^{103} - 1.</cmath> Certainly <cmath>S = 2^{103} - 1 \equiv -1 \equiv 7 \pmod {8}.</cmath> In addition, since we already computed <math>\text{ord}_{125}(2) = d = 100</math>, we know that <cmath>S = 2^{103} - 1 = 2^{100} \cdot 2^3 - 1 \equiv 2^3 - 1 \equiv 7 \pmod {125}.</cmath> Therefore, since <math>S \equiv 7 \pmod{8}</math> and <math>S \equiv 7 \pmod{125}</math>, we conclude that <math>S \equiv \boxed{007} \pmod {1000}.</math> | ||
− | 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 <math>S</math> into groups: <cmath>R = 1 + 2 + 4; \quad T = 2^3 + 2^4 + \cdots + 2^{102}.</cmath> It is easy to see that <math>R</math> is congruent to <math>7</math> modulo <math>1000.</math> | + | 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 <math>S</math> into groups: <cmath>R = 1 + 2 + 4; \quad T = 2^3 + 2^4 + \cdots + 2^{102}.</cmath> It is easy to see that <math>R</math> is congruent to <math>7</math> modulo <math>1000.</math> |
+ | |||
+ | Now, for <math>T</math>, notice that there are <math>100</math> terms in the summation, each with a different remainder upon division by <math>125.</math> Since each of these remainders is certainly relatively prime to <math>125</math>, these <math>100</math> remainders correspond to the <math>100</math> positive integers less than <math>125</math> that are relatively prime to <math>125.</math> Therefore, | ||
+ | <cmath>\begin{align*}T &\equiv 1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 + 11 + \cdots + 124 \pmod{125} \\ | ||
+ | &= \left(1 + 2 + 3 + \cdots + 125\right) - \left(5 + 10 + 15 + \cdots 125\right) \\ | ||
+ | &= \frac{125 \cdot 126}{2} - 5\left(1 + 2 + 3 + \cdots 25\right) \\ | ||
+ | &= 125 \cdot 63 - 5\left(\frac{25 \cdot 26}{2}\right) \\ | ||
+ | &= 125\left(63 - 13\right) \\ | ||
+ | &\equiv 0 \pmod{125}.\end{align*}</cmath> | ||
+ | Then, since <math>T</math> is divisible by <math>125</math> and <math>8</math>, it follows that <math>T</math> is divisible by <math>1000.</math> Therefore, <cmath>S = R + T \equiv R \equiv \boxed{007} \pmod{1000}.</cmath> | ||
+ | |||
+ | == 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 | ||
+ | |||
+ | == Solution 5 == | ||
+ | |||
+ | Recognize that as you cycle through progressively higher powers of two, you will have to begin repeating in a pattern at some point, since there are only a finite number of possible 3-digit endings and clearly there is no way for a small sub-pattern to form. The previous statement is true by induction since if a pattern began occurring, then it would need to occur for all values before that as well which is clearly untrue unless it encompasses all possible powers of two. Thus we can start thinking about a final value for it to start repeating. It can't be <math>001</math> or <math>501</math>, and it can't be <math>002</math> or <math>502</math> either because the last two digits of any power of 2 greater than <math>2^1</math> are divisible by 4. However, it can be <math>004</math> or <math>504</math>. From the fact that <math>1+2+4+8 \dots 2^n=2^{n+1}-1</math>, we can safely assume that the sum of all possible endings mod 1000 will be <math>2 \times4 -1=\boxed{007}</math>. | ||
+ | |||
+ | == Solution 6 (assumptions) == | ||
+ | We know that units digits repeat every <math>4</math>, and tens digits every <math>20</math>. Therefore, continuing the pattern, hundreds digits should repeat every <math>100</math>. But taking modulo <math>8</math>, we know that <math>1, 2, 4</math> will not be the same modulo <math>1000</math>. Hence, we start at <math>2^3</math> and move up <math>100</math>. That lands us at the first repeat, <math>2^{103}</math>. Just sum up to <math>2^{102}</math> to get a modulus of <math>\boxed{007}</math>. | ||
− | + | == See also == | |
+ | {{AIME box|year=2011|n=I|num-b=10|num-a=12}} | ||
− | + | [[Category: Intermediate Number Theory Problems]] | |
− | + | {{MAA Notice}} | |
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Revision as of 12:59, 8 May 2020
Contents
Problem
Let be the set of all possible remainders when a number , 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 the invariance of upon multiplication by implies the invariance of as for Thus, letting the sum of the residues less be we have from which follows.
Solution 2
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 3 (Euler's theorem)
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 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
Solution 5
Recognize that as you cycle through progressively higher powers of two, you will have to begin repeating in a pattern at some point, since there are only a finite number of possible 3-digit endings and clearly there is no way for a small sub-pattern to form. The previous statement is true by induction since if a pattern began occurring, then it would need to occur for all values before that as well which is clearly untrue unless it encompasses all possible powers of two. Thus we can start thinking about a final value for it to start repeating. It can't be or , and it can't be or either because the last two digits of any power of 2 greater than are divisible by 4. However, it can be or . From the fact that , we can safely assume that the sum of all possible endings mod 1000 will be .
Solution 6 (assumptions)
We know that units digits repeat every , and tens digits every . Therefore, continuing the pattern, hundreds digits should repeat every . But taking modulo , we know that will not be the same modulo . Hence, we start at and move up . That lands us at the first repeat, . Just sum up to to get a modulus of .
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.