2019 Mock AMC 10B Problems/Problem 19

Revision as of 21:46, 2 November 2019 by Baker77 (talk | contribs)

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 e^{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 smallest powers of $2$ that divide each of these numbers are $2, 2, 2, 2, 2, and 4$, respectively. The smallest power of $2$ that divides $3^{2016} - 1$ is thus $2^5 \cdot 4 = \boxed{\text{E} 256}$.