Difference between revisions of "2014 AMC 10B Problems/Problem 17"
m (→Solution 1) |
m (→Solution 7) |
||
(39 intermediate revisions by 13 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
What is the greatest power of <math>2</math> that is a factor of <math>10^{1002} - 4^{501}</math>? | What is the greatest power of <math>2</math> that is a factor of <math>10^{1002} - 4^{501}</math>? | ||
Line 8: | Line 8: | ||
We begin by factoring the <math>2^{1002}</math> out. This leaves us with <math>5^{1002} - 1</math>. | We begin by factoring the <math>2^{1002}</math> out. This leaves us with <math>5^{1002} - 1</math>. | ||
− | We factor the difference of squares, leaving us with <math>(5^{501} - 1)(5^{501} + 1)</math>. We note that all even powers of <math>5</math> more than two end in ...<math>625</math>. Also, all odd powers of five more than | + | We factor the difference of squares, leaving us with <math>(5^{501} - 1)(5^{501} + 1)</math>. We note that all even powers of <math>5</math> more than two end in ...<math>625</math>. Also, all odd powers of five more than <math>2</math> end in ...<math>125</math>. Thus, <math>(5^{501} + 1)</math> would end in ...<math>126</math> and thus would contribute one power of two to the answer, but not more. |
− | We can continue to factor < | + | We can continue to factor <math>(5^{501} - 1)</math> as a difference of cubes, leaving us with <math>(5^{167} - 1)</math> times an odd number (Notice that the other number is <math>5^{334} + 5^{167} + 1</math>. The powers of <math>5</math> end in <math>5</math>, so the two powers of <math>5</math> will end with <math>0</math>. Adding <math>1</math> will make it end in <math>1</math>. Thus, this is an odd number). <math>(5^{167} - 1)</math> ends in ...<math>124</math>, contributing two powers of two to the final result. |
− | Or we can see that < | + | Or we can see that <math>(5^{501} - 1)</math> ends in <math>124</math>, and is divisible by <math>2</math> only. Still that's <math>2</math> powers of <math>2</math>. |
− | Adding these extra < | + | Adding these extra <math>3</math> powers of two to the original <math>1002</math> factored out, we obtain the final answer of <math>\textbf{(D) } 2^{1005}</math>. |
==Solution 2== | ==Solution 2== | ||
Line 27: | Line 27: | ||
This means that <math>N</math> is divisible by <math>8= 2^3</math> but not <math>16 = 2^4</math>, so <math>k = 3</math> and our answer is <math>2^{1002 + 3} =\boxed{\textbf{(D)}\: 2^{1005}}</math>. | This means that <math>N</math> is divisible by <math>8= 2^3</math> but not <math>16 = 2^4</math>, so <math>k = 3</math> and our answer is <math>2^{1002 + 3} =\boxed{\textbf{(D)}\: 2^{1005}}</math>. | ||
+ | ==Solution 3== | ||
+ | Convert <math>4^{501}=2^{1002}</math>. We can factor out <math>2^{1002}</math> to get that <math>\nu_2(10^{1002}-2^{1002})=1002+\nu_2(5^{1002}-1)</math>. Using the adjusted Lifting The Exponent lemma (<math>\nu_2(a^n-b^n)=\nu_2(n)+\nu_2(a^2-b^2)-1</math> for all even <math>n</math> and odd <math>a,b</math>), we get that the answer is <math>2^{1002+\nu_2(1002)+\nu_2(24)-1}=2^{1002+1+3-1}=\boxed{\textbf{(D)}2^{1005}}</math> | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | Factor out <math>2^{1002}</math> to get <math>2^{1002}(5^{1002} - 1)</math>. Since <math>5^{1002}-1\equiv 3^{1002}-1\equiv (9)^{501}-1\equiv 1^{501}-1\equiv 0\pmod{8}</math>, but <math>5^{1002}-1\equiv 11^{1002}-1\equiv 121\cdot (11^4)^{250} - 1\equiv 121 - 1\equiv 8 \pmod{16}</math>, <math>5^{1002}-1</math> has 3 factors of 2. Hence <math>2^{1002 + 3} =\boxed{2^{1005}}</math> is the largest power of two which divides the given number | ||
+ | |||
+ | ==Solution 5== | ||
+ | |||
+ | Like Solution 1, factor out <math>2^{1002}</math> to get <math>(2^{1002})(5^{501}-1)(5^{501}+1)</math>. Using engineer's induction, we observe that for any positive integer <math>5^n</math> (where <math>n</math> is an odd positive integer), it appears that the least even numbers directly above and below <math>n</math> in value must contain a maximum multiple of <math>4</math> and a maximum multiple of <math>2</math>. Hence, the answer is <math>2^{1002+2+1}</math> which is <math>\boxed{\textbf{(D)} 2^{1005}}</math> . | ||
+ | |||
+ | Proof; | ||
+ | |||
+ | For all integers <math>x</math> where <math>x=5^{n}</math> where n is an odd integer, <math>x</math> must end in <math>125.</math> | ||
+ | Thus, we find that <math>x-1</math> and <math>x+1</math> respectively end in <math>124</math> and <math>126.</math> | ||
+ | |||
+ | Case <math>1</math> : <math>x-1</math> | ||
+ | |||
+ | We know that this number takes the form <math>abcde... 124</math> where <math>abcde...</math> is an integer that ends in <math>124</math>. Because <math>abcde...</math> is a multiple of <math>4</math> times an even number <math>e</math> while <math>124</math> is <math>4(31)</math>, we find that <math>X-1</math> must be <math>4e + 4 \cdot 31 = 4(e+31) = 4o</math> where <math>o</math> is an odd number | ||
+ | |||
+ | Case <math>2</math> : <math>x+1</math> | ||
+ | |||
+ | We know that this number <math>fghijk...126</math> ends. Because it is <math>2</math> more than the number <math>x-1</math>, which is a multiple of <math>4</math>, we find <math>x+1 = 4o + 2</math> which is an even number that is not divisible by <math>4</math>. Thus, it must have a maximum of <math>1</math> multiple of <math>2</math>. | ||
+ | |||
+ | This means that for any number <math>x</math> being in the form <math>5^{n}</math> where <math>n</math> is an odd integer, <math>x-1</math> must have a maximum of <math>2</math> factors of <math>2</math> while <math>x+1</math> must have a maximum of <math>1</math> factor of <math>2</math>. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ~ShangJ2 | ||
+ | |||
+ | ==Solution 6== | ||
+ | |||
+ | Using difference of squares, we get <math>\left(10^{501}-2^{501}\right) \left(10^{501}+2^{501}\right)</math>. Factoring a <math>2^{501}</math> out, we get <math>\left(2^{501}\right) \left(5^{501}-1\right) \left(2^{501}\right) \left(5^{501}+1\right)</math>, and grouping like terms give <math>\left(2^{1002}\right) \left(5^{501}-1\right) \left(5^{501}+1\right)</math>. | ||
+ | |||
+ | |||
+ | Then, you would go ahead and innocently choose <math>\textbf{(A) } 2^{1002}</math>, right? No! Note that <math>5^n</math>, where <math>n</math> is any odd integer greater than or equal to <math>3</math>, it always ends in <math>125</math>. So, <math>5^{501}+1</math> ends in <math>126</math> and <math>5^{501}-1</math> ends in <math>124</math>, so they add up to an extra three <math>2</math>'s. Therefore, the answer is actually <math>2^{1002+3}=\boxed{\textbf{(D) } 2^{1005}}</math>. | ||
+ | |||
+ | ~MrThinker | ||
+ | |||
+ | ==Solution 7== | ||
+ | Note that we are trying to find the number of powers of <math>2</math> in <math>(5^{1002}-1) \cdot 2^{1002}.</math> Let's see how many <math>5^{1002}-1</math> has. | ||
+ | |||
+ | Try the first 4 powers of 5, namely <math>5^1</math>, <math>5^2</math>, <math>5^3</math>, and <math>5^4</math>. Note that when taking <math>mod 4</math>, all result in <math>1 mod 4</math>. When taking <math>mod 8</math>, even powers result in <math>1 mod 8</math>. When taking <math>mod 16</math>, every <math>4</math>th power (i.e. <math>4,8,..</math>) will result in <math>1 mod 16</math>. | ||
+ | |||
+ | Because <math>1002</math> is even but <math>2 mod 4, 5^1002</math> will be equivalent to <math>1 mod 8</math> but not <math>1 mod 16</math>. Hence <math>5^1002 - 1</math> ≡ <math>0 mod 8</math>, and so we have an extra power of <math>2^3</math>, hence the result is <math>1002+3=1005 (D)</math>. | ||
+ | |||
+ | ~mathboy282 | ||
+ | ~Minor Edits by L314159265358979323846264 | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/aCtvD8nitgg | ||
+ | |||
+ | ~savannahsolver | ||
Latest revision as of 02:42, 30 October 2024
Contents
Problem
What is the greatest power of that is a factor of ?
Solution 1
We begin by factoring the out. This leaves us with .
We factor the difference of squares, leaving us with . We note that all even powers of more than two end in .... Also, all odd powers of five more than end in .... Thus, would end in ... and thus would contribute one power of two to the answer, but not more.
We can continue to factor as a difference of cubes, leaving us with times an odd number (Notice that the other number is . The powers of end in , so the two powers of will end with . Adding will make it end in . Thus, this is an odd number). ends in ..., contributing two powers of two to the final result.
Or we can see that ends in , and is divisible by only. Still that's powers of .
Adding these extra powers of two to the original factored out, we obtain the final answer of .
Solution 2
First, we can write the expression in a more primitive form which will allow us to start factoring. Now, we can factor out . This leaves us with . Call this number . Thus, our final answer will be , where is the largest power of that divides . Now we can consider , since by the answer choices.
Note that The powers of cycle in with a period of . Thus, This means that is divisible by but not , so and our answer is .
Solution 3
Convert . We can factor out to get that . Using the adjusted Lifting The Exponent lemma ( for all even and odd ), we get that the answer is
Solution 4
Factor out to get . Since , but , has 3 factors of 2. Hence is the largest power of two which divides the given number
Solution 5
Like Solution 1, factor out to get . Using engineer's induction, we observe that for any positive integer (where is an odd positive integer), it appears that the least even numbers directly above and below in value must contain a maximum multiple of and a maximum multiple of . Hence, the answer is which is .
Proof;
For all integers where where n is an odd integer, must end in Thus, we find that and respectively end in and
Case :
We know that this number takes the form where is an integer that ends in . Because is a multiple of times an even number while is , we find that must be where is an odd number
Case :
We know that this number ends. Because it is more than the number , which is a multiple of , we find which is an even number that is not divisible by . Thus, it must have a maximum of multiple of .
This means that for any number being in the form where is an odd integer, must have a maximum of factors of while must have a maximum of factor of .
~ShangJ2
Solution 6
Using difference of squares, we get . Factoring a out, we get , and grouping like terms give .
Then, you would go ahead and innocently choose , right? No! Note that , where is any odd integer greater than or equal to , it always ends in . So, ends in and ends in , so they add up to an extra three 's. Therefore, the answer is actually .
~MrThinker
Solution 7
Note that we are trying to find the number of powers of in Let's see how many has.
Try the first 4 powers of 5, namely , , , and . Note that when taking , all result in . When taking , even powers result in . When taking , every th power (i.e. ) will result in .
Because is even but will be equivalent to but not . Hence ≡ , and so we have an extra power of , hence the result is .
~mathboy282 ~Minor Edits by L314159265358979323846264
Video Solution
~savannahsolver
See Also
2014 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 16 |
Followed by Problem 18 | |
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.