Maths Olympiad Prep

Library / /48 of 64

Number theory Difficulty 8.1 Shortlist Find the answer

Let AA be the set of all integers nn such that 1n20211 \leq n \leq 2021 and gcd(n,2021)=1\gcd(n, 2021) = 1. For every nonnegative integer jj, let
S(j)=nAnj.S(j) = \sum_{n \in A} n^j.
Determine all values of jj such that S(j)S(j) is a multiple of 2021.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The values of jj in question are those not divisible by either 4242 or 4646.

We first check that for pp prime,
n=1p1nj0(modp)j≢0(modp1). \sum_{n=1}^{p-1} n^j \equiv 0 \pmod{p} \Leftrightarrow j \not\equiv 0 \pmod{p-1}.
If j0(modp1)j \equiv 0 \pmod{p-1}, then nj1(modp)n^j \equiv 1 \pmod{p} for each nn, so n=1p1njp1(modp)\sum_{n=1}^{p-1} n^j \equiv p-1 \pmod{p}. If j≢0(modp1)j \not\equiv 0 \pmod{p-1}, we can pick a primitive root mm modulo pp,
observe that mj≢1(modp)m^j \not\equiv 1 \pmod{p}, and then note that
n=1p1njn=1p1(mn)j=mjn=1p1nj(modp), \sum_{n=1}^{p-1} n^j \equiv \sum_{n=1}^{p-1} (mn)^j = m^j \sum_{n=1}^{p-1} n^j \pmod{p},
which is only possible if n=1p1nj0(modp)\sum_{n=1}^{p-1} n^j \equiv 0 \pmod{p}.

We now note that the prime factorization of 2021 is 43×4743 \times 47,
so it suffices to determine when S(j)S(j) 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.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.