Difference between revisions of "2011 AIME I Problems/Problem 11"

(Solution)
(the incorrect problem was up, I changed it to the actual one)
(39 intermediate revisions by 24 users not shown)
Line 1: Line 1:
== Problem ==
+
Let <math>R</math> be the set of all possible remainders when a number of the form <math>2^n</math>, <math>n</math> a nonnegative integer, is divided by 1000. Let <math>S</math> be the sum of the elements in <math>R</math>. Find the remainder when <math>S</math> is divided by 1000.
Let <math>R</math> be the set of all possible remainders when a number of the form <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 ==
+
== Solution 1==
Note that the cycle of remainders of <math>2^n</math> will start after <math>2^2</math> because remainders of <math>1, 2, 4</math> will not be possible after (the numbers following will always be congruent to 0 modulo 8). Now we have to find the order. Note that <math>2^{100}\equiv 1\mod 125</math>. The order is <math>100</math> starting with remainder <math>8</math>. All that is left is find <math>S</math> in mod <math>1000</math> after some computation.
+
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^{99}\equiv 2^{100}-1\equiv 8-1\equiv \boxed{007}\mod 1000</cmath>
+
<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 2 ==
 +
Notice that our sum of remainders looks like <cmath>S = 1 + 2 + 4 + 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>
 +
 
 +
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, 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:
 +
 
 +
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>
 +
 
 +
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>
  
 
== 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}}
 +
 +
[[Category: Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Revision as of 20:33, 2 September 2020

Let $R$ be the set of all possible remainders when a number of the form $2^n$, $n$ a nonnegative integer, is divided by 1000. Let $S$ be the sum of the elements in $R$. Find the remainder when $S$ is divided by 1000.

Solution 1

Note that $x \equiv y \pmod{1000} \Leftrightarrow x \equiv y \pmod{125}$ and $x \equiv y \pmod{8}$. So we must find the first two integers $i$ and $j$ such that $2^i \equiv 2^j \pmod{125}$ and $2^i \equiv 2^j \pmod{8}$ and $i \neq j$. Note that $i$ and $j$ will be greater than 2 since remainders of $1, 2, 4$ will not be possible after 2 (the numbers following will always be congruent to 0 modulo 8). Note that $2^{100}\equiv 1\pmod{125}$ (see Euler's theorem) and $2^0,2^1,2^2,\ldots,2^{99}$ are all distinct modulo 125 (proof below). Thus, $i = 103$ and $j =3$ are the first two integers such that $2^i \equiv 2^j \pmod{1000}$. All that is left is to find $S$ in mod $1000$. After some computation: \[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}.\] To show that $2^0, 2^1,\ldots, 2^{99}$ are distinct modulo 125, suppose for the sake of contradiction that they are not. Then, we must have at least one of $2^{20}\equiv 1\pmod{125}$ or $2^{50}\equiv 1\pmod{125}$. However, writing $2^{10}\equiv 25 - 1\pmod{125}$, we can easily verify that $2^{20}\equiv -49\pmod{125}$ and $2^{50}\equiv -1\pmod{125}$, giving us the needed contradiction.

Solution 2

Notice that our sum of remainders looks like \[S = 1 + 2 + 4 + 2^3 + 2^4 + \cdots.\] We want to find the remainder of $S$ upon division by $1000.$ Since $1000$ decomposes into primes as $1000 = 2^3 \cdot 5^3$, we can check the remainders of $S$ modulo $2^3$ and modulo $5^3$ separately.

Checking $S$ modulo $2^3$ is easy, so lets start by computing the remainder of $S$ upon division by $5^3.$ To do this, let's figure out when our sequence finally repeats. Notice that since the remainder when dividing any term of $S$ (after the third term) by $1000$ will be a multiple of $2^3$, when this summation finally repeats, the first term to repeat will be not be $1$ since $2^3 \nmid 1.$ Instead, the first term to repeat will be $2^3$, and then the sequence will continue once again $2^4, 2^5, \cdots.$

Now, to compute $S$ modulo $125$, we want to find the least positive integer $d$ such that $2^d \equiv 1 \pmod {125}$ since then $d$ will just be the number of terms of $S$ (after the third term!) before the sequence repeats. In other words, our sequence will be of the form $S = 1 + 2 + 4 + \left(2^3 + 2^4 + \cdots + 2^{2 + d}\right)$ and then we will have $2^{d + 3} \equiv 2^3 \pmod {125}$, and the sequence will repeat from there. Here, $d$ simply represents the order of $2$ modulo $125$, denoted by $d = \text{ord}_{125}(2).$ To begin with, we'll use a well-known property of the order to get a bound on $d.$

Since $\gcd(2, 125) = 1$ and $\phi(125) = 100$, we know by Euler's Theorem that $2^{100} \equiv 1 \pmod {125}.$ However, we do not know that $100$ is the least $d$ satisfying $2^d \equiv 1 \pmod {125}.$ Nonetheless, it is a well known property of the order that $\text{ord}_{125}(2) = d | \phi(125) = 100.$ Therefore, we can conclude that $d$ must be a positive divisor of $100.$

Now, this still leaves a lot of possibilities, so let's consider a smaller modulus for the moment, say $\mod 5.$ Clearly, we must have that $2^d \equiv 1 \pmod 5.$ Since $2^4 \equiv 1 \pmod 5$ and powers of two will then cycle every four terms, we know that $2^d \equiv 1 \pmod 5 \iff 4 | d.$ Combining this relation with $d | 100$, it follows that $d \in \{4, 20, 100\}.$

Now, it is trivial to verify that $d \ne 4.$ In addition, we know that \[2^{20} = \left(2^{10}\right)^2 = \left(1024\right)^2 \equiv 24^2 = 576 \not\equiv 1 \pmod {125}.\] Therefore, we conclude that $d \ne 20.$ Hence, we must have $d = 100.$ (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 $d = 100$, we know that \[S = 1 + 2 + 4 + 2^3 + 2^4 + \cdots + 2^{102}.\] There are two good ways to finish from here:

The first way is to use a trick involving powers of $2.$ Notice that \[S = 1 + 2 + 4 + ... + 2^{102} = 2^{103} - 1.\] Certainly \[S = 2^{103} - 1 \equiv -1 \equiv 7 \pmod {8}.\] In addition, since we already computed $\text{ord}_{125}(2) = d = 100$, we know that \[S = 2^{103} - 1 = 2^{100} \cdot 2^3 - 1 \equiv 2^3 - 1 \equiv 7 \pmod {125}.\] Therefore, since $S \equiv 7 \pmod{8}$ and $S \equiv 7 \pmod{125}$, we conclude that $S \equiv \boxed{007} \pmod {1000}.$

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 $S$ into groups: \[R = 1 + 2 + 4; \quad T = 2^3 + 2^4 + \cdots + 2^{102}.\] It is easy to see that $R$ is congruent to $7$ modulo $1000.$

Now, for $T$, notice that there are $100$ terms in the summation, each with a different remainder upon division by $125.$ Since each of these remainders is certainly relatively prime to $125$, these $100$ remainders correspond to the $100$ positive integers less than $125$ that are relatively prime to $125.$ Therefore, \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*} Then, since $T$ is divisible by $125$ and $8$, it follows that $T$ is divisible by $1000.$ Therefore, \[S = R + T \equiv R \equiv \boxed{007} \pmod{1000}.\]

See also

2011 AIME I (ProblemsAnswer KeyResources)
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. AMC logo.png

Invalid username
Login to AoPS