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$

Solution:

By Fermat's Little Theorem, we know that $a^{p-1} \equiv 1 \mod p$ if $a$ and $p$ are relatively prime.

Therefore, $a^4 \equiv 1 \mod 5,$ which makes: $a^{16} \equiv (a^4)^4 \equiv 1 \mod 5$ if $a$ and $5$ are relatively prime.

Since $5$ is a prime, they are relatively prime if $a$ isn't a multiple of $5.$ There are $\frac{2020} 5 =404$ multiples of $5,$ so there are $1616$ non-multiples of $5.$

All multiples of $5,$ when taken to the $16^{th}$ power, have a remainder of $0$ when divided by $5$ so they aren't included. Thus, there are exactly $1616$ of $2020$ numbers that work. This makes the probability $\frac{1616}{2020} = \frac 45.$

Thus, the correct answer is D .

2017 AMC 10B Problem 14

Solution:

Problem 14 in Other Years