Difference between revisions of "2019 Mock AMC 10B Problems/Problem 19"

Revision as of 22:02, 3 October 2023

Problem

What is the largest power of $2$ that divides $3^{2016}-1$ ?

$\textbf{(A)}\ 16 \qquad\textbf{(B)}\ 32 \qquad\textbf{(C)}\ 64 \qquad\textbf{(D)}\ 128 \qquad\textbf{(E)}\ 256$

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)$ .

By simple mod checking, we find that

$3^{1008} + 1 \equiv 3^{504} + 1 \equiv 3^{252} + 1 \equiv 3^{126} + 1 \equiv 3^{63} - 1 \equiv 2$ $\text{mod}$ $4$ , and $3^{63} + 1 \equiv 4$ $\text{mod}$ $8$ .

Therefore, the largest powers of $2$ that divide each of these numbers are $2, 2, 2, 2, 2$ , and $4$ . The largest power of $2$ that divides $3^{2016} - 1$ is thus $2^5 \cdot 4 = \boxed{\text{(D)} 128}$ .

Solution 2

By LTE Lemma, we know that $v_2(x^n - y^n) = v_2(x-y) + v_p(n) + v_p(x+y)-1$

So plugging in $x=3, y=1$ , and $n=2016$ , we get $1+5+2-1 = 7$ so the answer is $2^7 = \boxed{128}$

@@ Line 17: / Line 17: @@
 <baker77>
+Solution 2
+By LTE Lemma, we know that <math>v_2(x^n - y^n) = v_2(x-y) + v_p(n) + v_p(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>

Page

Toolbox

Search

Difference between revisions of "2019 Mock AMC 10B Problems/Problem 19"

Revision as of 22:02, 3 October 2023

Problem

Solution