Difference between revisions of "2009 AMC 10B Problems/Problem 21"
m (Reverted edits by Whitelisted (talk) to last revision by Savannahsolver) (Tag: Rollback) |
(→Solution 2) |
||
| Line 20: | Line 20: | ||
We have <math>3^2 = 9 \equiv 1 \pmod 8</math>. Hence for any <math>k</math> we have <math>3^{2k}\equiv 1^k = 1 \pmod 8</math>, and then <math>3^{2k+1} = 3\cdot 3^{2k} \equiv 3\cdot 1 = 3 \pmod 8</math>. | We have <math>3^2 = 9 \equiv 1 \pmod 8</math>. Hence for any <math>k</math> we have <math>3^{2k}\equiv 1^k = 1 \pmod 8</math>, and then <math>3^{2k+1} = 3\cdot 3^{2k} \equiv 3\cdot 1 = 3 \pmod 8</math>. | ||
| − | Therefore our sum gives the same remainder modulo <math>8</math> as <math>1 + 3 + 1 + 3 + 1 + \cdots + 1 + 3</math>. There are <math>2010</math> terms in the sum, hence there are <math>2010/2 = 1005</math> pairs <math>1+3</math>, and thus the sum is <math>1005 \cdot 4 = 4020 \equiv 20 \equiv \boxed{4} \pmod 8</math>. | + | Therefore our sum gives the same remainder modulo <math>8</math> as <math>1 + 3 + 1 + 3 + 1 + \cdots + 1 + 3</math>. There are <math>2010</math> terms in the sum, hence there are <math>2010/2 = 1005</math> pairs of <math>1+3</math>, and thus the sum is <math>1005 \cdot 4 = 4020 \equiv 20 \equiv \boxed{4} \pmod 8</math>. |
=== Solution 3 === | === Solution 3 === | ||
Revision as of 10:38, 2 July 2021
Contents
Problem
What is the remainder when 
is divided by 8?
Solution
Solution 1
The sum of any four consecutive powers of 3 is divisible by 
and hence is divisible by 8. Therefore
is divisible by 8. So the required remainder is 
. The answer is 
.
Solution 2
We have 
. Hence for any 
we have 
, and then 
.
Therefore our sum gives the same remainder modulo 
as 
. There are 
terms in the sum, hence there are 
pairs of 
, and thus the sum is 
.
Solution 3
We have the formula 
for the sum of a finite geometric sequence which we want to find the residue modulo 8.
![\[\frac{1 \cdot (3^{2010}-1)}{2}\]](http://latex.artofproblemsolving.com/6/d/b/6db10a23c131768960b3f0f57e141d4e9d2edcec.png)
![\[\frac{3^{2010}-1}{2} = \frac{9^{1005}-1}{2}\]](http://latex.artofproblemsolving.com/d/0/5/d05bd1b955c4f2eb083e52b012d3d33c86a94702.png)
![\[\frac{9^{1005}-1}{2} \equiv \frac{1^{1005}-1}{2} \equiv \frac{0}{2} \pmod 8\]](http://latex.artofproblemsolving.com/6/8/a/68a6dafa6a361a53ef0f2421e265eed91901085a.png)
Therefore, the numerator of the fraction is divisible by . However, when we divide the numerator by 
, we get a remainder of 
modulo , giving us .
Note: you need to prove that ![\[\frac{9^{1005}-1}{2}\]](http://latex.artofproblemsolving.com/b/9/e/b9e6e42c3fae1e6d2f6a9b861c9e974a79a5cbd4.png)
is not congruent to 0 mod 16 because if so, then the whole thing would be congruent to 0 mod 8, even after dividing by 2 ~ ilikepi12
Video Solution
~savannahsolver
See also
| 2009 AMC 10B (Problems • Answer Key • Resources) | ||
| Preceded by Problem 20 |
Followed by Problem 22 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
| All AMC 10 Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
