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

\begin{document}
\title{Canada 2021/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 65}
\maketitle

\section*{Problem}
A function $f \colon \NN \to \NN$ is called \emph{Canadian} if it satisfies
\[ \gcd\left(f(f(x)), f(x+y)\right)=\gcd(x, y) \]
for all pairs of positive integers $x$ and $y$.
Find all positive integers $m$ such that $f(m)=m$ for all Canadian functions $f$.

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

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

\newpage

\section*{Solution}
\emph{This problem and solution were suggested by Eric Shen (CAN).}

The answer is any integer which is not $1$ or a prime power.
The following functions show this,
for any nonnegative integer $e$ (including $e=0$) and prime $p$:
\[ f(x) = \begin{cases}
    p^{e+1} & x = p^e \\
    p^{e} & x = p^{e+1} \\
    x & \text{otherwise}.
  \end{cases}
\]
Here are two approaches.

\paragraph{Solution from Twitch Solves ISL.}
By letting $x=a$ and $x+y=b$, we get an addition-free statement:
\[ \gcd(f(f(a)), f(b)) = \gcd(a,b) \qquad \forall a < b. \]
In particular, if we fix a value of $b$,
we see that $f(b)$ is divisible by every proper divisor of $b$.
\begin{claim*}
  We have $x \mid f(x)$ for any non prime power $x$.
\end{claim*}
\begin{proof}
  Fix $b = x$ and vary $a$ across prime powers dividing $x$.
\end{proof}

\begin{claim*}
  We have $f(x) = x$ for all $x$ which is not a prime power.
\end{claim*}
\begin{proof}
  Since $x$ is not a prime power, we have $x \mid f(x)$,
  and in particular, $f(x)$ is not a prime power, so $x \mid f(x) \mid f(f(x))$.
  Now assume that $x < f(x)$; then
  \[ f(f(x)) = \gcd(f(f(x)), f(f(x))) = \gcd(x, f(x)) \mid x \]
  so $x = f(x) = f(f(x))$, contradiction.
\end{proof}

\begin{remark*}
  [Finding the construction]
  One can also deduce,
  though we don't need to, that $f(f(x)) = x$ from here.
  Indeed fix $x$, and let $y = (x+f(f(x))+3)!$ to conclude.
  Together with the fact that $p^{e-1} \mid f(p^e)$ for any prime $p$
  (from $(a,b) = (p^{e-1}, p^e)$),
  this motivates the construction given at the start of the proof.
\end{remark*}

\paragraph{Approach by Kevin Min.}
We prove the following claim:
\begin{claim*}
  $f(f(x)) = x$ for all $x$
\end{claim*}
\begin{proof}
  Let $P(x, y)$ denote the given equation.
  For any prime $p$ and number $x$, let $v_p(x)=k$.
  Then note that if $p^{k+1}\mid f(f(x))$,
  then we cannot have $p^{k+1}\mid f(n)$ for any $n>f(x)$
  or else $P(x, n-x)$ leads to a contradiction.
  But taking $P(p^z, p^z)$ for arbitrarily large $z$
  we get $p^{k+1}\mid f(n)$ for arbitrarily large $n$, contradiction.
  Similarly, if $p^k\nmid f(f(x))$ then $P(x, p^k)$ gives a contradiction.
  Thus $v_p(f(f(x)))=v_p(x)$ for all primes p, so $f(f(x))=x$.
\end{proof}

Then the given statement reduces to $\gcd(x, f(x+y))=\gcd(x, x+y)$. Let $z=x+y$ and let $Q(x, z)$ denote the given statement, where $z>x$.
Then suppose $z$ is not a prime power, so for some prime $p$
let $v_p(z)=m, z=p^m\cdot c$.
Then from $Q(p^m, z)$ we get $p^m\mid f(z)$, so $z\mid f(z)$.
But then $f(z)$ isn't a prime power either,
so $f(z)\mid f(f(z))$, and as $z=f(f(z))$ we must have $z=f(z)$.

\end{document}
