Maths Olympiad Prep

Library / Putnam /45 of 60

Putnam

Number theory Difficulty 8.1 Shortlist Find the answer

Let AA be the set of all integers nn such that 1≤n≤20211 \leq n \leq 2021 and gcd⁡(n,2021)=1\gcd(n, 2021) = 1. For every nonnegative integer jj, let
S(j)=∑n∈Anj.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. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

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

We first check that for pp prime,
∑n=1p−1nj≡0(modp)⇔j≢0(modp−1). \sum_{n=1}^{p-1} n^j \equiv 0 \pmod{p} \Leftrightarrow j \not\equiv 0 \pmod{p-1}.
If j≡0(modp−1)j \equiv 0 \pmod{p-1}, then nj≡1(modp)n^j \equiv 1 \pmod{p} for each nn, so ∑n=1p−1nj≡p−1(modp)\sum_{n=1}^{p-1} n^j \equiv p-1 \pmod{p}. If j≢0(modp−1)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=1p−1nj≡∑n=1p−1(mn)j=mj∑n=1p−1nj(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=1p−1nj≡0(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
S(j)≡46∑n=142nj(mod43)S(j)≡42∑n=146nj(mod47).\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
S(j)≡0(mod43)⇔j≢0(mod42)S(j)≡0(mod47)⇔j≢0(mod46).\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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.