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

\begin{document}
\title{EGMO 2024/5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 146}
\maketitle

\section*{Problem}
Find all functions $f \colon \NN \to \NN$ such that for all $x,y \in \NN$:
\begin{enumerate}
  \ii[(i)] $x$ and $f(x)$ have the same number of positive divisors.
  \ii[(ii)] if $x \nmid y$ and $y \nmid x$, then:
  \[ \gcd(f(x), f(y)) > f(\gcd(x, y)). \]
\end{enumerate}

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

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

\newpage

\section*{Solution}
The answer is
\[ f(x) = \ell^{d(x)-1} \]
where $\ell$ is a fixed prime, and $d(\bullet)$ is the divisor counting function.
This works, because when $x \nmid y$ and $y \nmid x$
we obviously have $d(\gcd(x,y)) < \min(d(x), d(y))$.
So now we prove this is the only solution.

Obviously $f(1) = 1$; we ignore this case further.

Note that $f(p)$ is always a prime for each prime $p$.
But if $p$ and $q$ are two different primes, then apparently
\[ \gcd\left( f(p), f(q) \right) > f(\gcd(p,q)) = f(1) \ge 1\]
and yet the left-hand side is the GCD of two primes.
So this could only happen if they are the \emph{same} prime;
hence we conclude $f(p)$ is constant, say $\ell$.

\begin{claim*}
  Every output of $f$ besides $f(1)$ must be a multiple of $\ell$
\end{claim*}
\begin{proof}
  To show $\ell \mid f(x)$ for $x > 1$,
  take $y$ to be any prime not dividing $x$.
  Then $\gcd(f(x), \ell) > 1$, as needed.
\end{proof}

This allows us to extend our earlier claim as follows:
\begin{claim*}
  If $p_1$, \dots, $p_k$ are distinct primes and
  $q_1$, \dots, $q_k$ are primes then
  \[ f\left( p_1^{q_1-1} \dots p_k^{q_k-1} \right) = \ell^{q_1 \dots q_k - 1}. \]
\end{claim*}
\begin{proof}
  By induction on $k$.
  For the base case $k = 1$,
  we know $f(p^{q-1})$ needs to be a multiple of $\ell$,
  and the only multiple of $\ell$ with $q$ prime divisors is $\ell^{q-1}$.

  Suppose $k \ge 2$ and WLOG $q_1 \ge q_2 \ge \dots \ge q_k$.
  We let $p$ be any other prime. Then
  \[
    \gcd\left( f(p_1^{q_1-1} \dots p_k^{q_k-1}),
      f(p_1^{q_1-1} \dots p_{k-1}^{q_{k-1}-1}p) \right)
      > f\left( p_1^{q_1-1} \dots p_{k-1}^{q_{k-1}-1}  \right)
      = q_1 q_2 \dots q_{k-1}.
  \]
  Hence $f(p_1^{q_1-1} \dots p_k^{q_k-1})$ is divisible by
  $\ell^{q_1 \dots q_{k-1}}$.
  There are no proper divisors of $q_1 \dots q_k$
  exceeding $q_1 \dots q_{k-1}$,
  so this forces $f(p_1^{q_1-1} \dots p_k^{q_k-1}) = \ell^{q_1 \dots q_k - 1}$ exactly.
\end{proof}

We will now attack the main problem in the following presentation:
\begin{claim*}
  Suppose $p_1$, \dots, $p_k$, $r_1$, \dots, $r_m$ are pairwise distinct primes,
  and $q_1$, \dots, $q_k$ are also prime numbers, and $e_1, \dots, e_m \ge 2$.
  Let
  \[ x = p_1^{q_1-1} \dots p_k^{q_k-1} r_1^{e_1-1} \dots r_m^{e_m-1} \]
  and set
  \[ n = d(x) = q_1 \dots q_k e_1 \dots e_m. \]
  Then $f(x) = \ell^{n-1}$.
\end{claim*}
\begin{proof}
  The proof is by induction on $m$, with the base case $m=0$ already done.
  For the inductive step, look at $e_m$.
  If $e_m$ is prime there is nothing to do.
  Otherwise, $e_m \ge 3$, and we can take a prime $q$ satisfying
  \[ \frac{e_m}{2} < q < e_m. \]
  and let $z$ be a random other prime not appearing already;
  then choosing
  \begin{align*}
    y &= p_1^{q_1-1} \dots p_k^{q_k-1} r_1^{e_1-1} \dots r_{m-1}^{q-1} z \\
    \gcd(x,y) &= p_1^{q_1-1} \dots p_k^{q_k-1} r_1^{e_1-1} \dots r_{m-1}^{q-1}.
  \end{align*}
  Then
  \begin{align*}
    f(y) &= \ell^{2q_1 \dots q_k \cdot e_1 \dots e_{m-1} \cdot q  - 1} > \ell^{n-1} \\
    f(\gcd(x,y)) &= \ell^{q_1 \dots q_k \cdot e_1 \dots e_{m-1} \cdot q - 1}
    = \ell^{n \cdot \frac{q}{e_m} - 1} > \ell^{\frac n2 - 1}.
  \end{align*}
  It follows that $\nu_{\ell}(f(x)) + 1 > \frac n2$.
  We know $n = d(f(x)) = \prod_{p} \left( \nu_p(f(x)) + 1 \right)$.
  If a number greater than $n/2$ appears on the product of the RHS,
  then in fact the product consists only of $n$.
  This completes the induction.
\end{proof}

\end{document}
