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 "2022 AMC 10B Problems/Problem 17"

(Created page with "==Problem== One of the following numbers is not divisible by any prime number less than 10. Which is it? ==Solution== For A, modulo 3, <cmath> \begin{align*} 2^{606} - 1 &...")
 
(→‎Solution 2 (Factoring))
 
(40 intermediate revisions by 13 users not shown)
Line 1: Line 1:
 +
{{duplicate|[[2022 AMC 10B Problems/Problem 17|2022 AMC 10B #17]] and [[2022 AMC 12B Problems/Problem 15|2022 AMC 12B #15]]}}
 +
 
==Problem==
 
==Problem==
  
−
One of the following numbers is not divisible by any prime number less than 10. Which is it?
+
One of the following numbers is not divisible by any prime number less than <math>10.</math> Which is it?
 +
 
 +
<math>\textbf{(A) } 2^{606}-1 \qquad\textbf{(B) } 2^{606}+1 \qquad\textbf{(C) } 2^{607}-1 \qquad\textbf{(D) } 2^{607}+1\qquad\textbf{(E) } 2^{607}+3^{607}</math>
  
−
==Solution==
+
==Solution 1 (Modular Arithmetic)==
  
−
For A, modulo 3,
+
For <math>\textbf{(A)}</math> modulo <math>3,</math>
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 13: Line 17:
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
 +
Thus, <math>2^{606} - 1</math> is divisible by <math>3.</math>
  
−
Thus, <math>2^{606} - 1</math> is divisible by 3.
+
For <math>\textbf{(B)}</math> modulo <math>5,</math>
−
 
 
−
For B, modulo 5,
 
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 25: Line 28:
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
 +
Thus, <math>2^{606} + 1</math> is divisible by <math>5.</math>
  
−
Thus, <math>2^{606} + 1</math> is divisible by 5.
+
For <math>\textbf{(D)}</math> modulo <math>3,</math>
−
 
 
−
For D, modulo 3,
 
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 36: Line 38:
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
 +
Thus, <math>2^{607} + 1</math> is divisible by <math>3.</math>
  
−
Thus, <math>2^{607} + 1</math> is divisible by 3.
+
For <math>\textbf{(E)}</math> modulo <math>5,</math>
−
 
 
−
For E, module 5,
 
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 48: Line 49:
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
 +
Thus, <math>2^{607} + 3^{607}</math> is divisible by <math>5.</math>
 +
 +
Therefore, the answer is <math>\boxed{\textbf{(C) }2^{607} - 1}.</math>
 +
 +
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
 +
~MrThinker (LaTeX Error)
 +
 +
==Solution 2 (Factoring)==
 +
We have
 +
<cmath>\begin{alignat*}{8}
 +
2^{606}-1 &= 4^{303}-1 &&= (4-1)(4^{302}+4^{301}+4^{300}+\cdots+4^0), \\
 +
2^{606}+1 &= 4^{303}+1 &&= (4+1)(4^{302}-4^{301}+4^{300}-\cdots+4^0), \\
 +
2^{607}+1 & &&= (2+1)(2^{606}-2^{605}+2^{604}-\cdots+2^0), \\
 +
2^{607}+3^{607} & &&= (2+3)(2^{606}\cdot3^0-2^{605}\cdot3^1+2^{604}\cdot3^2-\cdots+2^0\cdot3^{606}).
 +
\end{alignat*}</cmath>
 +
We conclude that <math>\textbf{(A)}</math> is divisible by <math>3</math>, <math>\textbf{(B)}</math> is divisible by <math>5</math>,<math>\textbf{(D)}</math> is divisible by <math>3</math>, and <math>\textbf{(E)}</math> is divisible by <math>5</math>.
 +
 +
Since all of the other choices have been eliminated, we are left with <math>\boxed{\textbf{(C) } 2^{607}-1}</math>.
 +
 +
~not_slay
 +
 +
==Solution 3 (Elimination)==
 +
Mersenne Primes are primes of the form <math>2^n-1</math>, where <math>n</math> is prime. Using the process of elimination, we can eliminate every option except for <math>\textbf{(A)}</math> and <math>\textbf{(C)}</math>. Clearly, <math>606</math> isn't prime, so the answer must be <math>\boxed{\textbf{(C) }2^{607}-1}</math>.
 +
 +
Note: A organization of computer scientist and mathematicians named Great Internet Mersenne Prime Search (GIMPS) search for the worlds biggest prime numbers. More information can be found on https://www.mersenne.org/primes/
 +
 +
==Solution 3a (Elimination)==
 +
 +
We examine option E first. <math>2^{607}</math> has a units digit of <math>8</math> (Taking the units digit of the first few powers of two gives a pattern of <math>2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6,\cdots</math>) and <math>3^{607}</math> has a units digit of <math>7</math> (Taking the units digit of the first few powers of three gives a pattern of <math>3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7, 1,\cdots</math>). Adding <math>7</math> and <math>8</math> together, we get <math>15</math>, which is a multiple of <math>5</math>, meaning that <math>2^{607}+3^{607}</math> is divisible by 5.
 +
 +
Next, we examine option D. We take the first few powers of <math>2</math> added with <math>1</math>:
 +
<cmath>2^1+1=3</cmath>
 +
<cmath>2^2+1=5</cmath>
 +
<cmath>2^3+1=9</cmath>
 +
<cmath>2^4+1=17</cmath>
 +
<cmath>2^5+1=33</cmath>
 +
<cmath>2^6+1=65</cmath>
 +
<cmath>2^7+1=129</cmath>
 +
 +
We see that the odd powers of <math>2</math> added with 1 are multiples of three. If we continue this pattern, <math>2^{607}+1</math> will be divisible by <math>3</math>. (The reason why this pattern works: When you multiply <math>2 \equiv2\pmod{3}</math> by <math>2</math>, you obtain <math>4 \equiv1 \pmod{3}</math>. Multiplying by <math>2</math> again, we get <math>1\cdot2\equiv2 \pmod{3}</math>. We see that in every cycle of two powers of <math>2</math>, it goes from <math>2 \pmod{3}</math> to <math>1 \pmod{3}</math> and back to <math>2 \pmod{3}</math>.)
 +
 +
Next, we examine option B. We see that <math>2^{606}</math> has a units of digits of <math>4</math> (Taking the units digit of the first few powers of two gives a pattern of <math>2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6,\cdots</math>). Adding <math>1</math> to <math>4</math>, we get <math>5</math>. Since <math>2^{606}+1</math> has a units digit of <math>5</math>, it is divisible by <math>5</math>.
 +
 +
Lastly, we examine option A. Using the difference of cubes factorization <math>a^3-b^3=(a-b)(a^2+ab+b^2)</math>, we have <math>2^{606}-1^3=(2^{202}-1)(2^{404}+2^{202}+1)</math>. Since <math>2^{404}+2^{202}+1\equiv0\pmod{3}</math> (Every term in the sequence is equivalent to <math>1\pmod{3}</math>), <math>2^{606}-1</math> is divisible by <math>3</math>.
 +
 +
Since we have eliminated every option except C, <math>\boxed{\text{(C)} \hspace{0.1 in}2^{607}-1}</math> is not divisible by any prime less than <math>10</math>.
 +
 +
~arjken (+ minor LaTeX edits ~TaeKim)
 +
 +
==Solution 3b (Elimination + Number Theory)==
 +
 +
We know that the prime numbers less than 10 are <math>2,3,5</math> and <math>7</math>. We can start by testing if any of the answer choices are divisible by <math>2</math>. We see that they are all sums of one even number and one odd number, which is simply odd. So, we cannot exclude any answer choices so far. Now, let's check divisibility by <math>3</math>. We can use the fact that <math>2 \equiv -1 \pmod{3}</math> to our advantage:
 +
 +
 +
 +
<math>(\text{A})\hspace{0.1in} 2^{606}-1</math>
 +
<math> \equiv (-1)^{606} -1 </math>
 +
<math>\equiv 1-1</math>
 +
<math>\equiv 0 \pmod{3}</math>
 +
 +
 +
<math>(\text{B}) \hspace{0.1in} 2^{606}+1</math>
 +
<math> \equiv (-1)^{606} +1</math>
 +
<math>\equiv 1+1</math>
 +
<math>\equiv 2 \pmod{3}</math>
 +
 +
 +
<math>(\text{C})\hspace{0.1in} 2^{607}-1</math>
 +
<math>\equiv (-1)^{607} -1</math>
 +
<math>\equiv -1 - 1</math>
 +
<math>\equiv -2 \pmod{3}</math>
 +
 +
 +
<math>(\text{D})\hspace{0.1in} 2^{607} +1 \equiv (-1)^{607} +1 \equiv -1+1 \equiv 0 \pmod{3}</math>
 +
 +
 +
<math>(\text{E}) \hspace{0.1in}  2^{607} + 3^{607} \equiv 2^{607} \equiv (-1)^{607} \equiv -1 \pmod{3}</math>
 +
  
−
Thus, <math>2^{607} + 3^{607}</math> is divisible by 5.
+
So, we eliminate choices A and D from divisibility by 3. Now, we move onto divisibility by 5. We can use cycling of powers to find useful remainders. Let's start with choice <math>B</math>.  
  
−
Therefore, the answer is
 
−
\boxed{\textbf{(C) <math>2^{607} - 1</math>}}.
 
  
−
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
+
 
 +
<math>(\text{B}) \hspace{0.1in} 2^{606}+1</math>
 +
 
 +
 
 +
 
 +
We see that the remainders of powers of <math>2</math> when divided by <math>5</math> cycle in a pattern: <math>2,4,3,1,2,4,3,1 \dots</math>. Since the pattern cycles every 4 terms, we use modulo 4 to simplify 606, getting that <math>606 \equiv 2\pmod{4}</math>. So, we get that <math>2^{606}</math> is congruent modulo 5 to the second term of our pattern, so <math>2^{606} \equiv{4} \pmod{5}</math>. Thus, <math> 2^{606}+1 \equiv 4+1 \equiv 5\equiv 0\pmod{5}</math>. We now eliminate choice B and compare choices C and E. 
 +
 
 +
 
 +
<math>(\text{E}) \hspace{0.1in} 2^{607} + 3^{607}</math>
 +
 
 +
 
 +
 
 +
 
 +
Looking at choice E, we see that we have to do similar cycling for powers of <math>3</math>. We get a pattern of <math>3,4,2,1,3,4,2,1 \dots</math>. Since this pattern also cycles every 4 terms, we use modulo 4 to simplify 607, getting that <math>607 \equiv 3\pmod{4}</math>. Both the power of 3 and the power of 2 have an exponent of 607, so we use the third term (since we just found that <math>607 \equiv 3\pmod{4}</math>) in each corresponding 4 term pattern to get that <math>2^{607} + 3^{607} \equiv 3+2 \equiv 5 \equiv 0\pmod{5}</math>. We eliminate choice E, and we are left with the correct answer: choice <math>\boxed{(\text{C}) \hspace{0.1in} 2^{607}-1}</math>
 +
 
 +
 
 +
~TaeKim
 +
 
 +
==Video Solution by mop 2024==
 +
https://youtu.be/ezGvZgBLe8k&t=577s
 +
 
 +
~r00tsOfUnity
  
 
==Video Solution==
 
==Video Solution==
Line 61: Line 160:
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
 +
== Video Solution by OmegaLearn Using Digit Cycles ==
 +
https://youtu.be/k4eLhi9wXO8
 +
 +
~ pi_is_3.14
 +
 +
==Video Solution(1-16)==
 +
https://youtu.be/SCwQ9jUfr0g
 +
 +
~~Hayabusa1
 +
==Video Solution by Interstigation==
 +
https://youtu.be/NSGUJJYD8KA
 +
 +
~Interstigation
 +
 +
==Video Solution by TheBeautyofMath==
 +
https://youtu.be/UQWqjI4G1hc
 +
 +
~IceMatrix
 +
== See Also ==
 +
{{AMC10 box|year=2022|ab=B|num-b=16|num-a=18}}
 +
{{AMC12 box|year=2022|ab=B|num-b=14|num-a=16}}
 +
{{MAA Notice}}

Latest revision as of 23:14, 2 November 2024

The following problem is from both the 2022 AMC 10B #17 and 2022 AMC 12B #15, so both problems redirect to this page.

Problem

One of the following numbers is not divisible by any prime number less than $10.$ Which is it?

$\textbf{(A) } 2^{606}-1 \qquad\textbf{(B) } 2^{606}+1 \qquad\textbf{(C) } 2^{607}-1 \qquad\textbf{(D) } 2^{607}+1\qquad\textbf{(E) } 2^{607}+3^{607}$

Solution 1 (Modular Arithmetic)

For $\textbf{(A)}$ modulo $3,$ \begin{align*} 2^{606} - 1 & \equiv (-1)^{606} - 1 \\ & \equiv 1 - 1 \\ & \equiv 0 . \end{align*} Thus, $2^{606} - 1$ is divisible by $3.$

For $\textbf{(B)}$ modulo $5,$ \begin{align*} 2^{606} + 1 & \equiv 2^{{\rm Rem} ( 606, \phi(5) )} + 1 \\ & \equiv 2^{{\rm Rem} ( 606, 4 )} + 1 \\ & \equiv 2^2 + 1 \\ & \equiv 0 . \end{align*} Thus, $2^{606} + 1$ is divisible by $5.$

For $\textbf{(D)}$ modulo $3,$ \begin{align*} 2^{607} + 1 & \equiv (-1)^{607} + 1 \\ & \equiv - 1 + 1 \\ & \equiv 0 . \end{align*} Thus, $2^{607} + 1$ is divisible by $3.$

For $\textbf{(E)}$ modulo $5,$ \begin{align*} 2^{607} + 3^{607} & \equiv 2^{607} + (-2)^{607} \\ & \equiv 2^{607} - 2^{607} \\ & \equiv 0 . \end{align*} Thus, $2^{607} + 3^{607}$ is divisible by $5.$

Therefore, the answer is $\boxed{\textbf{(C) }2^{607} - 1}.$

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

~MrThinker (LaTeX Error)

Solution 2 (Factoring)

We have \begin{alignat*}{8} 2^{606}-1 &= 4^{303}-1 &&= (4-1)(4^{302}+4^{301}+4^{300}+\cdots+4^0), \\ 2^{606}+1 &= 4^{303}+1 &&= (4+1)(4^{302}-4^{301}+4^{300}-\cdots+4^0), \\ 2^{607}+1 & &&= (2+1)(2^{606}-2^{605}+2^{604}-\cdots+2^0), \\ 2^{607}+3^{607} & &&= (2+3)(2^{606}\cdot3^0-2^{605}\cdot3^1+2^{604}\cdot3^2-\cdots+2^0\cdot3^{606}). \end{alignat*} We conclude that $\textbf{(A)}$ is divisible by $3$, $\textbf{(B)}$ is divisible by $5$,$\textbf{(D)}$ is divisible by $3$, and $\textbf{(E)}$ is divisible by $5$.

Since all of the other choices have been eliminated, we are left with $\boxed{\textbf{(C) } 2^{607}-1}$.

~not_slay

Solution 3 (Elimination)

Mersenne Primes are primes of the form $2^n-1$, where $n$ is prime. Using the process of elimination, we can eliminate every option except for $\textbf{(A)}$ and $\textbf{(C)}$. Clearly, $606$ isn't prime, so the answer must be $\boxed{\textbf{(C) }2^{607}-1}$.

Note: A organization of computer scientist and mathematicians named Great Internet Mersenne Prime Search (GIMPS) search for the worlds biggest prime numbers. More information can be found on https://www.mersenne.org/primes/

Solution 3a (Elimination)

We examine option E first. $2^{607}$ has a units digit of $8$ (Taking the units digit of the first few powers of two gives a pattern of $2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6,\cdots$) and $3^{607}$ has a units digit of $7$ (Taking the units digit of the first few powers of three gives a pattern of $3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7, 1,\cdots$). Adding $7$ and $8$ together, we get $15$, which is a multiple of $5$, meaning that $2^{607}+3^{607}$ is divisible by 5.

Next, we examine option D. We take the first few powers of $2$ added with $1$: \[2^1+1=3\] \[2^2+1=5\] \[2^3+1=9\] \[2^4+1=17\] \[2^5+1=33\] \[2^6+1=65\] \[2^7+1=129\]

We see that the odd powers of $2$ added with 1 are multiples of three. If we continue this pattern, $2^{607}+1$ will be divisible by $3$. (The reason why this pattern works: When you multiply $2 \equiv2\pmod{3}$ by $2$, you obtain $4 \equiv1 \pmod{3}$. Multiplying by $2$ again, we get $1\cdot2\equiv2 \pmod{3}$. We see that in every cycle of two powers of $2$, it goes from $2 \pmod{3}$ to $1 \pmod{3}$ and back to $2 \pmod{3}$.)

Next, we examine option B. We see that $2^{606}$ has a units of digits of $4$ (Taking the units digit of the first few powers of two gives a pattern of $2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6,\cdots$). Adding $1$ to $4$, we get $5$. Since $2^{606}+1$ has a units digit of $5$, it is divisible by $5$.

Lastly, we examine option A. Using the difference of cubes factorization $a^3-b^3=(a-b)(a^2+ab+b^2)$, we have $2^{606}-1^3=(2^{202}-1)(2^{404}+2^{202}+1)$. Since $2^{404}+2^{202}+1\equiv0\pmod{3}$ (Every term in the sequence is equivalent to $1\pmod{3}$), $2^{606}-1$ is divisible by $3$.

Since we have eliminated every option except C, $\boxed{\text{(C)} \hspace{0.1 in}2^{607}-1}$ is not divisible by any prime less than $10$.

~arjken (+ minor LaTeX edits ~TaeKim)

Solution 3b (Elimination + Number Theory)

We know that the prime numbers less than 10 are $2,3,5$ and $7$. We can start by testing if any of the answer choices are divisible by $2$. We see that they are all sums of one even number and one odd number, which is simply odd. So, we cannot exclude any answer choices so far. Now, let's check divisibility by $3$. We can use the fact that $2 \equiv -1 \pmod{3}$ to our advantage:


$(\text{A})\hspace{0.1in} 2^{606}-1$ $\equiv (-1)^{606} -1$ $\equiv 1-1$ $\equiv 0 \pmod{3}$


$(\text{B}) \hspace{0.1in} 2^{606}+1$ $\equiv (-1)^{606} +1$ $\equiv 1+1$ $\equiv 2 \pmod{3}$


$(\text{C})\hspace{0.1in} 2^{607}-1$ $\equiv (-1)^{607} -1$ $\equiv -1 - 1$ $\equiv -2 \pmod{3}$


$(\text{D})\hspace{0.1in} 2^{607} +1 \equiv (-1)^{607} +1 \equiv -1+1 \equiv 0 \pmod{3}$


$(\text{E}) \hspace{0.1in} 2^{607} + 3^{607} \equiv 2^{607} \equiv (-1)^{607} \equiv -1 \pmod{3}$


So, we eliminate choices A and D from divisibility by 3. Now, we move onto divisibility by 5. We can use cycling of powers to find useful remainders. Let's start with choice $B$.


$(\text{B}) \hspace{0.1in} 2^{606}+1$


We see that the remainders of powers of $2$ when divided by $5$ cycle in a pattern: $2,4,3,1,2,4,3,1 \dots$. Since the pattern cycles every 4 terms, we use modulo 4 to simplify 606, getting that $606 \equiv 2\pmod{4}$. So, we get that $2^{606}$ is congruent modulo 5 to the second term of our pattern, so $2^{606} \equiv{4} \pmod{5}$. Thus, $2^{606}+1 \equiv 4+1 \equiv 5\equiv 0\pmod{5}$. We now eliminate choice B and compare choices C and E.


$(\text{E}) \hspace{0.1in} 2^{607} + 3^{607}$



Looking at choice E, we see that we have to do similar cycling for powers of $3$. We get a pattern of $3,4,2,1,3,4,2,1 \dots$. Since this pattern also cycles every 4 terms, we use modulo 4 to simplify 607, getting that $607 \equiv 3\pmod{4}$. Both the power of 3 and the power of 2 have an exponent of 607, so we use the third term (since we just found that $607 \equiv 3\pmod{4}$) in each corresponding 4 term pattern to get that $2^{607} + 3^{607} \equiv 3+2 \equiv 5 \equiv 0\pmod{5}$. We eliminate choice E, and we are left with the correct answer: choice $\boxed{(\text{C}) \hspace{0.1in} 2^{607}-1}$


~TaeKim

Video Solution by mop 2024

https://youtu.be/ezGvZgBLe8k&t=577s

~r00tsOfUnity

Video Solution

https://youtu.be/YF3HPVcVGZk

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution by OmegaLearn Using Digit Cycles

https://youtu.be/k4eLhi9wXO8

~ pi_is_3.14

Video Solution(1-16)

https://youtu.be/SCwQ9jUfr0g

~~Hayabusa1

Video Solution by Interstigation

https://youtu.be/NSGUJJYD8KA

~Interstigation

Video Solution by TheBeautyofMath

https://youtu.be/UQWqjI4G1hc

~IceMatrix

See Also

2022 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 16 		Followed by
Problem 18
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2022 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Problem 16
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_17&oldid=231298"