Let be the set of all integers such that and . For every nonnegative integer , let
Determine all values of such that is a multiple of 2021.
Solution
The values of in question are those not divisible by either or .
We first check that for prime,
If , then for each , so . If , we can pick a primitive root modulo ,
observe that , and then note that
which is only possible if .
We now note that the prime factorization of 2021 is ,
so it suffices to determine when is divisible by each of 43 and 47.
We have
\begin{align*}
S(j) &\equiv 46 \sum_{n=1}^{42} n^j \pmod{43} \\
S(j) &\equiv 42 \sum_{n=1}^{46} n^j \pmod{47}.
\end{align*}
Since 46 and 42 are coprime to 43 and 47, respectively,
we have
\begin{gather*}
S(j) \equiv 0 \pmod{43} \Leftrightarrow j \not\equiv 0 \pmod{42} \\
S(j) \equiv 0 \pmod{47} \Leftrightarrow j \not\equiv 0 \pmod{46}.
\end{gather*}
This yields the claimed result.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.