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

\begin{document}
\title{Shortlist 2007 N5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 13}
\maketitle

\section*{Problem}
Find all functions $f \colon \NN \to \NN$ such that $f(1)=1$ and
for all positive integers $m$ and $n$ and primes $p$,
the number $f(m+n)$ is divisible by $p$
if and only if $f(m) + f(n)$ is divisible by $ p$.

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

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

\newpage

\section*{Solution}
The answer is that $f$ must be the identity (which works).
We let $\opname{rad} n$ denote the product of distinct prime factors of $n$.
We also let $P(m,n)$ denote the given statement.

\begin{remark*}
  The original problem gave the hypothesis $f$ was surjective
  in place of $f(1)=1$.
  Our version is better:
  to see that $f$ surjective implies $f(1)=1$ anyways,
  consider $P(1,N-1)$ if $f(N)=1$ held for any $N \ge 2$.
\end{remark*}

\begin{claim*}
  We have $\opname{rad} f(2^e) =2$ for every positive integer $e$;
  that is, $f(2)$, $f(4)$, \dots are all powers of $2$.
\end{claim*}
\begin{proof}
  Follows by taking $P(2^{e-1}, 2^{e-1})$ and induction.
\end{proof}

\begin{claim*}
  We have $f(2) = 2$, $f(3) = 3$, $f(4) = 4$.
\end{claim*}
\begin{proof}
  First, $P(3,1)$ gives that $f(3) = 2^y-1$ for some $y$.
  Now if $f(2) = 2^x$ then $P(2,1)$ gives
  \[ \opname{rad}(2^x+1) = \opname{rad}(2^y-1). \]
  We now consider two cases.
  \begin{itemize}
    \ii If $x = 3$ then this forces $y = 2$.
    So $f(2) = 8$ and $f(3) = 3$.
    But $\opname{rad} (1+f(4)) = \opname{rad} (f(2)+f(3)) = 11$,
    so there is no possible value of $f(4)$, contradiction.

    \ii Otherwise, let $p$ be a primitive prime divisor of $2^{2x}-1$
    which exists by Zsigmondy.
    It also divides the right-hand side, so $2x \mid y$,
    and $2^{2x}-1 \mid 2^y-1$.
    This could only happen if $2^x-1=1$, so $x=1$.
    This gives $y=2$ (again by Zsigmondy) and we're done.
  \end{itemize}
  Hence $f(2) = 2$ and $f(3) = 3$.
  Now $\opname{rad} (1+f(4)) = \opname{rad} (f(2)+f(3)) = 5$,
  and since $f(4)$ is a power of $2$,
  Zsigmondy implies $f(4) = 4$.
\end{proof}

Moving forward, we apply the following simple consequence of Zsigmondy:
\begin{lemma*}
  If $\opname{rad}(2^x-1) = \opname{rad}(2^y-1)$ then $x=y$.
  Similarly if $\opname{rad}(2^x+1) = \opname{rad}(2^y+1)$ then $x=y$.
\end{lemma*}

We now prove by induction on $e \ge 1$ the statement that
\[ f(n) = n \qquad \text{ for } 2^e \le n \le 2^{e+1}. \]
The base case is already set for us.
For the inductive step, suppose $f$ is the identity for $n \le 2^e$.
We proceed in three steps:
\begin{itemize}
\ii First, we have
\begin{align*}
  \opname{rad} \left( 1 + f\left( 2^{e+1}-1 \right) \right) &= 2 \\
  \opname{rad} \left( f\left( 2^{e+1}-1 \right) \right) &=
  \opname{rad} \left( f(2^e-1) + f(2^e) \right) = \opname{rad} (2^{e+1}-1).
\end{align*}
The first equation just says $f(2^{e+1}-1) = 2^t-1$ for some $t$.
So the latter equation, together with the lemma,
gives $f(2^{e+1}-1) = 2^{e+1}-1$.

\ii Next, we have
\begin{align*}
  \opname{rad} \left( f(2^{e+1}) + 1 \right)
  &= \opname{rad} f(2^{e+1}+1)
  = \opname{rad} \left( (2^{e+1}-1) + 2 \right) \\
  &= \opname{rad} \left( f(2^{e+1}-1) + f(2) \right)
  = \opname{rad} \left( 2^{e+1} + 1 \right)
\end{align*}
which gives $f(2^{e+1}) = 2^{e+1}$.

\ii Now assume $2^e + 1 \le n \le 2^{e+1}-2$.
Let $1 \le k \le 2^e - 2$ be such than $n+k = 2^{e+1}-1$.
Then
\begin{align*}
  \opname{rad} \left( f(n)+k \right)
  &= \opname{rad} \left( f(n)+f(k) \right)
  = \opname{rad} \left( f(n+k) \right) = \opname{rad} \left( 2^{e+1}-1 \right) \\
  \opname{rad} \left( f(n)+k+1 \right)
  &= \opname{rad} \left( f(n)+f(k+1) \right)
  = \opname{rad} \left( f(n+k+1) \right) = 2.
\end{align*}
So we have an integer $x$ (depending on $k$) such that
\[ f(n) + k + 1 = 2^x \implies
  \opname{rad}(2^x - 1)
  = \opname{rad} \left( f(n)+k \right)
  = \opname{rad}(2^{e+1}-1).  \]
Hence $x = e+1$.
And so $f(n) = n$.
\end{itemize}
This completes the induction and hence the problem is solved.

\end{document}
