\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}}
\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 any 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}