Difference between revisions of "2019 Mock AMC 10B Problems/Problem 19"
Jayevvms123 (talk | contribs) m (→Solution) |
|||
(8 intermediate revisions by 2 users not shown) | |||
Line 8: | Line 8: | ||
<math>3^{2016} - 1 = (3^{1008} - 1)(3^{1008} + 1) = (3^{504} - 1)(3^{504} + 1)(3^{1008} + 1) = (3^{252} - 1)(3^{252} + 1)(3^{504} + 1)(3^{1008} + 1)</math> | <math>3^{2016} - 1 = (3^{1008} - 1)(3^{1008} + 1) = (3^{504} - 1)(3^{504} + 1)(3^{1008} + 1) = (3^{252} - 1)(3^{252} + 1)(3^{504} + 1)(3^{1008} + 1)</math> | ||
− | <math>= (3^{126} - 1)(3^{126} + 1)(3^{252} + 1)(3^{504} + 1)(3^{1008} + 1) = (3^{63} - 1)(3^{63} + 1)(3^{126} + 1)(3^{252} + 1)(3^{504} + 1)(3^{1008} + 1)</math>. By simple mod checking, we find that <math>3^{1008} + 1 \equiv 3^{504} + 1 \equiv 3^{252} + 1 \equiv 3^{126} + 1 \equiv 3^{63} - 1 \equiv 2</math> <math>\text{mod}</math> <math>4</math>, and <math>3^{63} + 1 \equiv 4</math> <math>\text{mod}</math> <math>8</math>. Therefore, the | + | <math>= (3^{126} - 1)(3^{126} + 1)(3^{252} + 1)(3^{504} + 1)(3^{1008} + 1) = (3^{63} - 1)(3^{63} + 1)(3^{126} + 1)(3^{252} + 1)(3^{504} + 1)(3^{1008} + 1)</math>. |
+ | |||
+ | By simple mod checking, we find that | ||
+ | |||
+ | <math>3^{1008} + 1 \equiv 3^{504} + 1 \equiv 3^{252} + 1 \equiv 3^{126} + 1 \equiv 3^{63} - 1 \equiv 2</math> <math>\text{mod}</math> <math>4</math>, and <math>3^{63} + 1 \equiv 4</math> <math>\text{mod}</math> <math>8</math>. | ||
+ | |||
+ | Therefore, the largest powers of <math>2</math> that divide each of these numbers are <math>2, 2, 2, 2, 2</math>, and <math>4</math>. The largest power of <math>2</math> that divides <math>3^{2016} - 1</math> is thus <math>2^5 \cdot 4 = \boxed{\text{(D)} 128}</math>. | ||
+ | |||
+ | <baker77> | ||
+ | |||
+ | |||
+ | Solution 2 | ||
+ | |||
+ | By LTE Lemma, we know that <math>v_2(x^n - y^n) = v_2(x-y) + v_2(n) + v_2(x+y)-1</math> | ||
+ | |||
+ | So plugging in <math>x=3, y=1</math>, and <math>n=2016</math>, we get <math>1+5+2-1 = 7</math> so the answer is <math>2^7 = \boxed{128}</math> | ||
+ | |||
+ | <jayevvms123> |
Latest revision as of 23:04, 3 October 2023
Problem
What is the largest power of that divides
?
Solution
.
By simple mod checking, we find that
, and
.
Therefore, the largest powers of that divide each of these numbers are
, and
. The largest power of
that divides
is thus
.
<baker77>
Solution 2
By LTE Lemma, we know that
So plugging in , and
, we get
so the answer is
<jayevvms123>