|
|
| Line 1: |
Line 1: |
| − | ==Problem==
| + | #REDIRECT [[2022_AMC_10B_Problems/Problem_17]] |
| − | | |
| − | 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 \text{(E) } 2^{607}+3^{607}</math>
| |
| − | | |
| − | ==Solution 1 (Process of 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 1.1 (Process of 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>
| |
| − | | |
| − | | |
| − | 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>.
| |
| − | | |
| − | | |
| − | | |
| − | <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
| |
| − | | |
| − | ==Solution 2 (Factoring, Process of Elimination)==
| |
| − | | |
| − | We have <math>\textbf{(A)} = 2^{606} - 1 = 4^{303} - 1 = (4^{101} - 1)(4^{202} + 4^{101} + 1) \equiv 0 \pmod 3</math> because <math>4^x-1 \equiv 0 \pmod 3</math> for all positive integers <math>x</math>.
| |
| − | | |
| − | We have <math>\textbf{(B)} = 2^{606} + 1 = 4^{303} + 1 = (4^{101} + 1)(4^{202} - 4^{101} + 1) \equiv 0 \pmod 5</math> because <math>4^x+1 \equiv 0 \pmod 5</math> for all positive odd integers <math>x</math>.
| |
| − | | |
| − | We have <math>\textbf{(D)} = 2^{607} + 1 = (2 + 1)(1 - 2 + 4 - 8 + \cdots + 2^{606}) \equiv 0 \pmod 3</math>.
| |
| − | | |
| − | We have <math>\textbf{(E)} = 2^{607} + 3^{607} = (2+3)(3^{606} + 3^{605}2^1 + 3^{604}2^2 + \cdots + 2^{606}) \equiv 0 \pmod 5</math>.
| |
| − | | |
| − | Thus, our only answer left is <math>\boxed{(\text{C}) \hspace{0.1in} 2^{607}-1}</math>
| |
| − | | |
| − | ~mathboy100 (minor solution edits ~arjken)
| |
| − | | |
| − | == See Also ==
| |
| − | {{AMC12 box|year=2022|ab=B|num-b=14|num-a=16}}
| |
| − | {{MAA Notice}}
| |
