Difference between revisions of "2019 Mock AMC 10B Problems/Problem 19"
(Created page with "== Problem == What is the largest power of <math>2</math> that divides <math>3^{2016}-1</math>? <math>\textbf{(A)}\ 16 \qquad\textbf{(B)}\ 32 \qquad\textbf{(C)}\ 64 \qquad\...") |
|||
Line 7: | Line 7: | ||
== Solution == | == Solution == | ||
− | <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) = (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 e^{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 smallest powers of <math>2</math> that divide each of these numbers are <math>2, 2, 2, 2, 2, and 4</math>, respectively. The smallest power of <math>2</math> that divides <math>3^{2016} - 1</math> is thus <math>2^5 \cdot 4 \equiv 256</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) = (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 e^{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 smallest powers of <math>2</math> that divide each of these numbers are <math>2, 2, 2, 2, 2, and 4</math>, respectively. The smallest power of <math>2</math> that divides <math>3^{2016} - 1</math> is thus <math>2^5 \cdot 4 \equiv 256</math>. |
Revision as of 21:44, 2 November 2019
Problem
What is the largest power of that divides
?
Solution
$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) = (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)$ (Error compiling LaTeX. Unknown error_msg). By simple mod checking, we find that
, and
. Therefore, the smallest powers of
that divide each of these numbers are
, respectively. The smallest power of
that divides
is thus
.