\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{SMO 2020/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 27}
\maketitle
\section*{Problem}
Let $p > 2$ be a fixed prime number.
Find all functions $f \colon \FF_p \to \FF_p$,
such that $f(f(n)) = f(n+1) - 1$ for all $n$.
\section*{Video}
\href{https://www.youtube.com/watch?v=8IjDBRNMGI0&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/8IjDBRNMGI0}}
\newpage
\section*{Solution}
Only the identity function works.
\begin{claim*}
$f$ is bijective.
\end{claim*}
\begin{proof}
The function $f$ is surjective since $f(f(n)) = f(n+1)-1$
means that if $y$ is in the range of $f$,
then so is $y-1$.
Since the domain and codomain are finite with equal cardinality,
this implies it is actually a bijection.
\end{proof}
\begin{claim*}
For every integer $e \ge 1$ we have the statement
\[ P_e(n): \qquad f^{2^e}(n) + e = f(n+e). \]
\end{claim*}
\begin{proof}
The statement $P_1$ is given.
By applying $f$ to both sides of $P_1(n)$ we have
\[ f^2(f^2(n)) + 1
\overset{P_1(f^2(n))}{=}
f(f^2(n)+1) = f^2(n+1) \overset{P_1(n+1)}{=} f(n+2) - 1
\]
and thus we arrive at the statement
\[ P_2(n): \qquad f^4(n) + 2 = f(n+2) \]
which is the statement $P_2$.
Take $f$ of both sides again and
\[ f^8(n) + 2 \overset{P_2(f^4(n))}{=}
f(f^4(n)+2) = f(f(n+2)) \overset{P_1(n)}{=} f(n+3) - 1 \]
which gives the statement $P_3$ and repeating this argument
yields the general claim.
\end{proof}
Now we have in particular that $f^{2^p}(n) = f(n)$,
and hence all elements of $\FF_p$ have order dividing $2^p-1$.
However, all divisors of $2^p-1$ are $1 \pmod p$, and
in particular no divisor other than $1$ is greater than $p$.
So $f$ has order $1$ on all elements, ergo it must be the identity.
\end{document}