Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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\...")
 
m (→‎Solution)
 
(16 intermediate revisions by 2 users not shown)
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)</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 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 22:04, 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}$.

<baker77>


Solution 2

By LTE Lemma, we know that $v_2(x^n - y^n) = v_2(x-y) + v_2(n) + v_2(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}$

<jayevvms123>

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_Mock_AMC_10B_Problems/Problem_19&oldid=199100"