\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{USEMO 2019/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 11}
\maketitle

\section*{Problem}
Prove that for any prime $p$,
there exists a positive integer $n$ such that
\[ 1^n + 2^{n-1} + 3^{n-2} + \dotsb + n^1 \equiv 2020 \pmod{p}. \]

\section*{Video}
\href{https://www.youtube.com/watch?v=0rdn01T_q4Y&list=PLi6h8GM1FA6yfhMMNqJi1mht4KmZnXpj6}{\texttt{https://youtu.be/0rdn01T\_q4Y}}

\section*{External Link}
\url{https://aops.com/community/p15425708}

\newpage

\section*{Solution}
The idea is to pick $n = c \cdot p \cdot (p-1)$
for suitable integer $c$.
In what follows, everything is written modulo $p$.

\begin{claim*}
  When $n = c \cdot p \cdot (p-1)$, the left-hand side is equal to
  \begin{align*}
    c \cdot \sum_{a=0}^{p-2} \sum_{b=1}^{p-1} b^a
    = c \cdot \big[ & 1^0 + 2^0 + \dots + (p-1)^0 \\[-2.5ex]
    &+ 1^1 + 2^1 + \dots + (p-1)^1 \\
    &+ 1^2 + 2^2 + \dots + (p-1)^2 \\
    &+ \dots \\
    &+ 1^{p-2} + 2^{p-2} + \dots + (p-1)^{p-2} \big].
  \end{align*}
\end{claim*}
\begin{proof}
  In the original sum, we discard all the terms divisible by $p$,
  reduce all the bases modulo $p$,
  and reduce all the exponents modulo $p-1$ (by Fermat's little theorem).
  Then each block of $p(p-1)$ terms equals
  \begin{align*}
    & \phantom{+} 1^{0} + 2^{p-2} + 3^{p-3} + \dots + (p-1)^1 \\
    & + 1^{p-2} + 2^{p-3} + 3^{p-4} + \dots + (p-1)^0 \\
    & + 1^{p-3} + 2^{p-4} + 3^{p-5} + \dots + (p-1)^{p-2} \\
    & + \dots \\
    & + 1^1 + 2^0 + 3^{p-2} + \dots + (p-1)^2
  \end{align*}
  which rearranges to the desired sum.
\end{proof}

\begin{claim*}
  We have
  \[ \sum_{a=0}^{p-2} \sum_{b=1}^{p-1} b^a \equiv -1 \pmod p. \]
\end{claim*}

\begin{proof}
  [First proof]
  By the geometric series formula
  \[ \sum_{a=0}^{p-2} b^a = \frac{b^{p-1}-1}{b-1} = 0
    \qquad \forall\;  b = 2, 3, \dots p-1.  \]
  The terms with $b=1$ contribute $1^0+1^1+\dots+1^{p-2} = p-1$
  and done.
\end{proof}
\begin{proof}
  [Second proof]
  In fact, it's a classical lemma
  (proved in the same way, using primitive roots) that
  \[ \sum_{b=1}^{p-1} b^a \equiv
    \begin{cases}
      -1 & p-1 \mid a \\
      0 & p-1 \nmid a
    \end{cases}
    \pmod p
  \]
  so this is immediate.
\end{proof}

Thus we simply need to select $c \equiv -2020 \pmod p$ and win
(and $c > 0$).

\end{document}
