2017 AMC 10B Problem 14

Question

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?

\dfrac{1}{5}

\dfrac{2}{5}

\dfrac{3}{5}

\dfrac{4}{5}

1

Modulo

5

, only whether

N

is divisible by

5

matters

Use Fermat’s little theorem or check residue classes modulo

5

By Fermat’s Little Theorem,

N^4\equiv1\pmod5

whenever

N

is not divisible by

5.

Therefore,

N^{16}\equiv(N^4)^4\equiv1\pmod5.

There are

\frac{2020}{5}=404

multiples of

5,

so there are

2020-404=1616

allowable values of

N.

A multiple of

5

has

N^{16}\equiv0\pmod5,

so no other values work. Thus the probability is

\dfrac{1616}{2020}=\dfrac45.

Thus, the correct answer is D .

Problem 14 in other years