2017 AMC 10 B

Complete problem set with solutions and individual problem pages

Problem 14 Medium

An integer N is selected at random in the range 1\leqslant N\leqslant2020. What is the probability that the remainder when N^{16} is divided by 5 is 1? (2017 AMC 10B Problem, Question#14)

  • A.

    \frac 15

  • B.

    \frac 25

  • C.

    \frac 35

  • D.

    \frac 45

  • E.

    1

Answer:D

By Fermat's Little Theorem, N^{16}=\left( N^{4}\right)^{4}\equiv1(mod 5), when N is relatively prime to 5. Hence, this happens with probability \frac 45.

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 \frac 45.

We can use modular arithmetic for each residue of n (mod 5).

If n\equiv0 (mod 5), then n^{16}\equiv0^{16}\equiv0(mod 5),

If n\equiv1 (mod 5), then n^{16}\equiv1^{16}\equiv0(mod 5),

If n\equiv2 (mod 5), then n^{16}\equiv\left( n^{2}\right)^{8}\equiv\left( 2^{2}\right)^{8}\equiv4^{8}\equiv\left( -1\right)^{8}\equiv1 (mod 5).

If n\equiv3 (mod 5), then n^{16}\equiv\left( n^{2}\right)^{8}\equiv\left( 3^{2}\right)^{8}\equiv9^{8}\equiv\left( -1\right)^{8}\equiv1 (mod 5).

If n\equiv4 (mod 5), then n^{16}\equiv4^{16}\equiv\left( -1\right)^{16}=1 (mod 5).

In 4 out of the 5 cases, the result was 1(mod 5), and since each case occurs equally as 2020\equiv0 (mod 5), the answer is \frac 45.

Related Problems
Problem 12 2017 AMC 10 B
Problem 13 2017 AMC 10 B
Problem 15 2017 AMC 10 B
Problem 16 2017 AMC 10 B
Think Academy Powered by ChatGPT