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 "2017 AMC 10B Problems/Problem 14"
(Added another video solution)
 
(16 intermediate revisions by 8 users not shown)
Line 5: Line 5:
  
 
==Solution 1==
 
==Solution 1==
−
By Fermat's Little Theorem, <math>N^{16} = (N^4)^4 \equiv 1 \text{ (mod 5)}</math> when N is relatively prime to 5. However, this happens with probability <math>\boxed{\textbf{(D) } \frac 45}</math>.
+
Notice that we can rewrite <math>N^{16}</math> as <math>(N^{4})^4</math>. By [[Fermat's Little Theorem]], we know that <math>N^{(5-1)} \equiv 1 \pmod {5}</math>  if <math>N \not \equiv 0 \pmod {5}</math>. Therefore for all <math>N \not \equiv 0 \pmod {5}</math> we have <math>N^{16} \equiv (N^{4})^4 \equiv 1^4 \equiv 1 \pmod 5</math>. Since  <math>1\leq N \leq 2020</math>, and <math>2020</math> is divisible by <math>5</math>, <math>\frac{1}{5}</math> of the possible <math>N</math> are divisible by <math>5</math>. Therefore, <math>N^{16} \equiv 1 \pmod {5}</math> with probability <math>1-\frac{1}{5},</math> or <math>\boxed{\textbf{(D) } \frac 45}</math>.
  
 
==Solution 2==
 
==Solution 2==
Line 11: Line 11:
 
The pattern for <math>0</math> is <math>0</math>, no matter what power, so <math>0</math> doesn't work. Likewise, the pattern for <math>5</math> is always <math>5</math>. Doing the same for the rest of the digits, we find that the units digits of <math>1^{16}</math>, <math>2^{16}</math> ,<math>3^{16}</math>, <math>4^{16}</math> ,<math>6^{16}</math>, <math>7^{16}</math> ,<math>8^{16}</math> and <math>9^{16}</math> all have the remainder of <math>1</math> when divided by <math>5</math>, so <math>\boxed{\textbf{(D) } \frac 45}</math>.
 
The pattern for <math>0</math> is <math>0</math>, no matter what power, so <math>0</math> doesn't work. Likewise, the pattern for <math>5</math> is always <math>5</math>. Doing the same for the rest of the digits, we find that the units digits of <math>1^{16}</math>, <math>2^{16}</math> ,<math>3^{16}</math>, <math>4^{16}</math> ,<math>6^{16}</math>, <math>7^{16}</math> ,<math>8^{16}</math> and <math>9^{16}</math> all have the remainder of <math>1</math> when divided by <math>5</math>, so <math>\boxed{\textbf{(D) } \frac 45}</math>.
  
−
==Solution 3 (casework)==
 
−
We can use modular arithmetic for each case of <math>n(\text{mod }5)</math>
 
  
 +
Explanation:
 +
Since the remainder is 1, the units digit is either 1 or 6. Since we only care about the units digits, we don't need to think about anything beyond units digits.
 +
We count in modulus ten (fancy word of saying ignore everything except the units digit)
 +
For 1:
 +
1, 1, 1, 1... anything with a units digit one will always have powers that have a units digit one.
 +
For 2:
 +
2, 4, 8, 6, 2, 4, 8, 6... we see that it repeats with a cycle of 4. Since we are looking for the 16th power, the units digit will be 6, and this works.
 +
For 3:
 +
3, 9, 7, 1, 3, 9, 7, 1... similarly to 2, a cycle of 4 and the 16th power has a units digit of 1. This works.
 +
For 4:
 +
4, 6, 4, 6... a cycle of 4, 16th power has a units digit of 6. This works.
 +
For 5:
 +
5, 5, 5, 5... the units digit will always be 5, and this doesn't work.
 +
For 6:
 +
6, 6, 6, 6... the units digit will always be 6, and this works.
 +
For 7:
 +
7, 9, 3, 1, 7, 9, 3, 1... a cycle of 4, 16th power has a units digit of 1. This works.
 +
For 8:
 +
8, 4, 2, 6, 8, 4, 2, 6... a cycle of 4, 16th power has a units digit of 6. This works.
 +
For 9:
 +
9, 1, 9, 1... a cycle of 2, 16th power has a units digit of 1. This works.
 +
Last but not least, 0:
 +
0, 0, 0... the units digit will always be 0, and this does not work.
 +
To sum up: There are ten choices for the units digit. Of these ten choices, 1, 2, 3, 4, 6, 7, 8, 9 all work, and the probability is therefore <math>\frac{8}{10}=\frac{4}{5}</math> which is answer choice <math>\boxed{\textbf{(D)}\ \frac{4}{5}}</math>.
 +
~Explanation by JH. L
  
 +
==Solution 3 (Casework)==
 +
We can use modular arithmetic for each residue of <math>n \pmod 5</math>
  
−
If <math>n \equiv 0(\text{mod }5)</math>, then <math>n^{16} \equiv 0^{16} \equiv 0 (\text{mod }5)</math>
 
  
  
−
If <math>n \equiv 1(\text{mod }5)</math>, then <math>n^{16} \equiv 1^{16} \equiv 1 (\text{mod }5)</math>
+
If <math>n \equiv 0 \pmod 5</math>, then <math>n^{16} \equiv 0^{16} \equiv 0 \pmod 5</math>
  
  
−
If <math>n \equiv 2(\text{mod }5)</math>, then <math>n^{16} \equiv (n^2)^8 \equiv 4^8 \equiv (-1)^8 \equiv 1 (\text{mod }5)</math>
+
If <math>n \equiv 1 \pmod 5</math>, then <math>n^{16} \equiv 1^{16} \equiv 1 \pmod 5</math>
  
  
−
If <math>n \equiv 3(\text{mod }5)</math>, then <math>n^{16} \equiv (n^4)^4 \equiv 81^4 \equiv (1)^4 \equiv 1 (\text{mod }5)</math>
+
If <math>n \equiv 2 \pmod 5</math>, then <math>n^{16} \equiv (n^2)^8 \equiv (2^2)^8 \equiv 4^8 \equiv (-1)^8 \equiv 1 \pmod 5</math>
  
  
−
If <math>n \equiv 4(\text{mod }5)</math>, then <math>n^{16} \equiv (-1)^{16} \equiv 1 (\text{mod }5)</math>
+
If <math>n \equiv 3 \pmod 5</math>, then <math>n^{16} \equiv (n^2)^8 \equiv (3^2)^8 \equiv 9^8 \equiv (-1)^8 \equiv 1 \pmod 5</math>
  
  
 +
If <math>n \equiv 4 \pmod 5</math>, then <math>n^{16} \equiv 4^{16} \equiv (-1)^{16} \equiv 1 \pmod 5</math>
  
−
In <math>4</math> out of the <math>5</math> cases, the result was <math>1(\text{mod }5)</math>, and since each case occurs equally, the answer is <math>\boxed{\textbf{(D) }\frac{4}{5}}</math>
 
  
  
 +
In <math>4</math> out of the <math>5</math> cases, the result was <math>1 \pmod 5</math>, and since each case occurs equally as <math>2020 \equiv 0 \pmod 5</math>, the answer is <math>\boxed{\textbf{(D) }\frac{4}{5}}</math>
 +
 +
== Video Solution 1 by OmegaLearn ==
 +
https://youtu.be/zfChnbMGLVQ?t=2410
 +
 +
~ pi_is_3.14
 +
 +
==Video Solution 2==
 +
https://youtu.be/Oj3Z1JhvoiE
 +
 +
~savannahsolver
 +
 +
==Video Solution 3==
 +
https://www.youtube.com/watch?v=PY_WugVa4cg
 +
 +
~Math4All999
 +
 +
==See Also==
 
{{AMC10 box|year=2017|ab=B|num-b=13|num-a=15}}
 
{{AMC10 box|year=2017|ab=B|num-b=13|num-a=15}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 00:17, 4 December 2023

Problem

An integer $N$ is selected at random in the range $1\leq N \leq 2020$ . What is the probability that the remainder when $N^{16}$ is divided by $5$ is $1$?

$\textbf{(A)}\ \frac{1}{5}\qquad\textbf{(B)}\ \frac{2}{5}\qquad\textbf{(C)}\ \frac{3}{5}\qquad\textbf{(D)}\ \frac{4}{5}\qquad\textbf{(E)}\ 1$

Solution 1

Notice that we can rewrite $N^{16}$ as $(N^{4})^4$. By Fermat's Little Theorem, we know that $N^{(5-1)} \equiv 1 \pmod {5}$ if $N \not \equiv 0 \pmod {5}$. Therefore for all $N \not \equiv 0 \pmod {5}$ we have $N^{16} \equiv (N^{4})^4 \equiv 1^4 \equiv 1 \pmod 5$. Since $1\leq N \leq 2020$, and $2020$ is divisible by $5$, $\frac{1}{5}$ of the possible $N$ are divisible by $5$. Therefore, $N^{16} \equiv 1 \pmod {5}$ with probability $1-\frac{1}{5},$ or $\boxed{\textbf{(D) } \frac 45}$.

Solution 2

Note that the patterns for the units digits repeat, so in a sense we only need to find the patterns for the digits $0-9$ . The pattern for $0$ is $0$, no matter what power, so $0$ doesn't work. Likewise, the pattern for $5$ is always $5$. Doing the same for the rest of the digits, we find that the units digits of $1^{16}$, $2^{16}$ ,$3^{16}$, $4^{16}$ ,$6^{16}$, $7^{16}$ ,$8^{16}$ and $9^{16}$ all have the remainder of $1$ when divided by $5$, so $\boxed{\textbf{(D) } \frac 45}$.


Explanation: Since the remainder is 1, the units digit is either 1 or 6. Since we only care about the units digits, we don't need to think about anything beyond units digits. We count in modulus ten (fancy word of saying ignore everything except the units digit) For 1: 1, 1, 1, 1... anything with a units digit one will always have powers that have a units digit one. For 2: 2, 4, 8, 6, 2, 4, 8, 6... we see that it repeats with a cycle of 4. Since we are looking for the 16th power, the units digit will be 6, and this works. For 3: 3, 9, 7, 1, 3, 9, 7, 1... similarly to 2, a cycle of 4 and the 16th power has a units digit of 1. This works. For 4: 4, 6, 4, 6... a cycle of 4, 16th power has a units digit of 6. This works. For 5: 5, 5, 5, 5... the units digit will always be 5, and this doesn't work. For 6: 6, 6, 6, 6... the units digit will always be 6, and this works. For 7: 7, 9, 3, 1, 7, 9, 3, 1... a cycle of 4, 16th power has a units digit of 1. This works. For 8: 8, 4, 2, 6, 8, 4, 2, 6... a cycle of 4, 16th power has a units digit of 6. This works. For 9: 9, 1, 9, 1... a cycle of 2, 16th power has a units digit of 1. This works. Last but not least, 0: 0, 0, 0... the units digit will always be 0, and this does not work. To sum up: There are ten choices for the units digit. Of these ten choices, 1, 2, 3, 4, 6, 7, 8, 9 all work, and the probability is therefore $\frac{8}{10}=\frac{4}{5}$ which is answer choice $\boxed{\textbf{(D)}\ \frac{4}{5}}$. ~Explanation by JH. L

Solution 3 (Casework)

We can use modular arithmetic for each residue of $n \pmod 5$


If $n \equiv 0 \pmod 5$, then $n^{16} \equiv 0^{16} \equiv 0 \pmod 5$


If $n \equiv 1 \pmod 5$, then $n^{16} \equiv 1^{16} \equiv 1 \pmod 5$


If $n \equiv 2 \pmod 5$, then $n^{16} \equiv (n^2)^8 \equiv (2^2)^8 \equiv 4^8 \equiv (-1)^8 \equiv 1 \pmod 5$


If $n \equiv 3 \pmod 5$, then $n^{16} \equiv (n^2)^8 \equiv (3^2)^8 \equiv 9^8 \equiv (-1)^8 \equiv 1 \pmod 5$


If $n \equiv 4 \pmod 5$, then $n^{16} \equiv 4^{16} \equiv (-1)^{16} \equiv 1 \pmod 5$


In $4$ out of the $5$ cases, the result was $1 \pmod 5$, and since each case occurs equally as $2020 \equiv 0 \pmod 5$, the answer is $\boxed{\textbf{(D) }\frac{4}{5}}$

Video Solution 1 by OmegaLearn

https://youtu.be/zfChnbMGLVQ?t=2410

~ pi_is_3.14

Video Solution 2

https://youtu.be/Oj3Z1JhvoiE

~savannahsolver

Video Solution 3

https://www.youtube.com/watch?v=PY_WugVa4cg

~Math4All999

See Also

2017 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
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

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=2017_AMC_10B_Problems/Problem_14&oldid=206452"