2017 AMC 10B Problem 14

$N^{16}$ is far too big to compute, but we only need its remainder when divided by $5$. The remainder of a product depends only on the remainders of the factors, so only $N$'s own remainder matters. For example, $7$ and $2$ both leave remainder $2$, and $7^2 = 49$ and $2^2 = 4$ both leave remainder $4$.

1. Try the small remainders $1, 2, 3, 4$ and raise each to the fourth power:

1. So whenever $N$ is not a multiple of $5$, $N^4$ leaves remainder $1$. In symbols, $N^4 \equiv 1 \pmod 5$, which just means "$N^4$ leaves remainder $1$ when divided by $5$."
2. Now $N^{16} = N^4 \cdot N^4 \cdot N^4 \cdot N^4$. Four factors that each leave remainder $1$ multiply to something that leaves remainder $1 \cdot 1 \cdot 1 \cdot 1 = 1$.
3. If $N$ is a multiple of $5$, then $N^{16}$ is too, and the remainder is $0$.
4. So the remainder is $1$ exactly when $N$ is not a multiple of $5$.
5. From $1$ to $2020$ there are $2020 \div 5 = 404$ multiples of $5$. That leaves $2020 - 404 = 1616$ numbers that work.
6. The probability is $\frac{1616}{2020} = \frac{4}{5}$.

The answer is $\boxed{\textbf{(D)}\ \frac{4}{5}}$.

For remainder questions about huge powers, work with remainders from the start and look for a power that brings you back to $1$. Here the fourth power does it for every number not divisible by $5$ (a fact known as Fermat's little theorem), and $16$ is a multiple of $4$. Because $2020$ is a multiple of $5$, each remainder appears equally often, giving exactly $\frac45$.

Only the remainder of $N$ mod $5$ matters. Compute fourth powers of each nonzero residue:
$$1^4 = 1,\quad 2^4 = 16 \equiv 1,\quad 3^4 = 81 \equiv 1,\quad 4^4 = 256 \equiv 1 \pmod 5.$$
So whenever $5 \nmid N$, $N^{16} = (N^4)^4 \equiv 1^4 = 1 \pmod 5$. If $5 \mid N$, then $N^{16} \equiv 0$.

Thus $N^{16}$ leaves remainder $1$ exactly when $N$ is not a multiple of $5$. Since $2020 = 5 \cdot 404$, the range $1$ to $2020$ contains $404$ multiples of $5$ and $2020 - 404 = 1616$ non-multiples. The probability is
$$\frac{1616}{2020} = \frac{4}{5}.$$

The answer is $\boxed{\textbf{(D)}\ \frac{4}{5}}$.