13. Let $p(x)=x^{20}+a_{19} x^{19}+a_{18} x^{18}+\ldots+a_{1} x+a_{0}$ be a polynomial, with the $a_{i}$ being integers. We know that, for all integers $k$ between 1 and 20, $p(k)=2k$. What are the last 3 digits of $p(21)$?
13. The answer is 042. Let $q(x) = p(x) - 2x$. Since $p(k) = 2k$ for $k = 1, \ldots, 20$, then $q(k) = 0$ for $k = 1, \ldots, 20$. According to the Ruffini's theorem, this means that the polynomial $q(x)$ is divisible by $x-1, x-2, \ldots, x-20$. Therefore, we have

$$
q(x) = (x-1)(x-2) \cdots (x-20) r(x)
$$

for some polynomial $r(x)$. If $r(x)$ had a degree of 1 or higher, $q(x)$ and thus $p(x) = q(x) + 2x$ would have a degree greater than 20, which contradicts the hypothesis. Therefore, $r(x)$ must be a constant, say $r(x) = \alpha$. Expanding the product in equation (2), we see that the leading term (degree 20) of $q(x)$, and thus of $p(x)$, has a coefficient of $\alpha$; hence, $r(x) = \alpha = 1$. We have thus shown that

$$
q(x) = (x-1)(x-2) \cdots (x-20).
$$

From this equality, it follows that

$$
p(x) = (x-1)(x-2) \cdots (x-20) + 2x
$$

and therefore, evaluating the polynomial at $x = 21$, we get

$$
p(21) = 20 \cdot 19 \cdots 1 + 2 \cdot 21 = 20! + 42
$$

The term 20! is a multiple of 1000 (it can be easily verified that it contains enough factors of 2 and 5); more precisely, 20! ends exactly with 4 zeros (there are only 4 factors equal to 5). Therefore, the last three digits of $p(21)$ are 042.