2019 Mock AMC 10B Problems/Problem 19
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 $3^{1008} + 1 \equiv 3^{504} + 1 \equiv e^{252} + 1 \equiv 3^{126 + 1 \equiv 3^{63} - 1 \equiv 2$ (Error compiling LaTeX. Unknown error_msg)
, and
. Therefore, the smallest powers of
that divide each of these numbers are
, respectively. The smallest power of
that divides
is thus
.