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

\begin{document}
\title{CEMC Euclid 2023/10C}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 124}
\maketitle

\section*{Problem}
Define
\[ f(n) =
  \left\lfloor \frac{n}{1^2+1} \right\rfloor
  + \left\lfloor \frac{2n}{2^2+1}\right\rfloor
  + \left\lfloor \frac{3n}{3^2+1} \right\rfloor
  + \dotsb \]
for each positive integer $n$.
Suppose $m$ is odd and $f(m+1) - f(m) = 2$. Show that $m$ is prime.

\section*{Video}
\href{https://www.youtube.com/watch?v=soMY1qyNiNI&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/soMY1qyNiNI}}

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

\newpage

\section*{Solution}
Notice that for any positive integers $n$ and $k$, we have
\[
  \left\lfloor \frac{kn+k}{k^2+1} \right\rfloor
  - \left\lfloor \frac{kn}{k^2+1} \right\rfloor
  = \begin{cases}
  1 & n \equiv k, 2k, \dots, k^2 \pmod{k^2+1} \\
  0 & \text{otherwise.}
  \end{cases}
\]
Fix $m$ and let $a_k$ be the term above for brevity.
This means that
\[ f(m+1)-f(m) = a_1 + a_2 + \dots. \]

\begin{claim*}
  If $m > 1$ is odd and composite, then $a_1+a_2+\dots$ is at least $3$.
\end{claim*}
\begin{proof}
  Notice that $a_1 = 1$, $a_m = 1$,
  and if $d$ is any proper divisor of $m$ which is
  greater than or equal to $\sqrt m$ (so that $d^2+1 > m$),
  we have $a_d = 1$ as well.
\end{proof}

Finally, $f(2)-f(1)=1$.
So if $m$ is odd and $f(m+1)-f(m)=2$, it follows $m$ is prime.

\end{document}
