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

\begin{document}
\title{Shortlist 2004 N2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 7}
\maketitle

\section*{Problem}
Define $f \colon \NN \to \NN$ by
\[ f(n) = \sum_{k=1}^n \gcd(k,n). \]
For each positive integer $a$,
show that the equation $f(x)=ax$ has at least one solution
and determine whether or not that solution is unique.



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

\newpage

\section*{Solution}
Let $g(n) = f(n) / n$,
so we are interested in the outputs of $g$.
We start with:
\begin{claim*}
  The function $g$ is multiplicative
  and satisfies
  \[ g(p^e) = \frac{p-1}{p} \cdot e + 1 \]
  for any prime power $p^e$.
\end{claim*}
\begin{proof}
First, write
\[ f(n) = \sum_{d \mid n} d\varphi(n/d)
  = \id \ast \varphi \]
to get that $f$ is multiplicative
(as the Dirichlet convolution of two multiplicative functions).
Thus $g(n) = f(n)/n$ is multiplicative too.

Now note that for any prime power $p^e$, we have
\[ g(p^e) = \frac{f(p^e)}{p^e} =
  \frac{p^e \cdot 1 + p^{e-1}(p-1) + \dots + 1 \cdot
  (p^e-p^{e-1})}{p^e}
  = e + 1 - \frac ep \]
so the second part is true too.
\end{proof}

In particular, we have
\[ g(2^{2a-2}) = a \]
so we already know every $a$ has the solution $x = 2^{2a-2}$.

We now show that this is the only solution
if and only if $a$ is a power of $2$.

First, if $q > 1$ is any odd divisor of $a$,
then writing $a = q \cdot b$, one can note that
\begin{align*}
  g(2^{2b-2}) &= b \\
  g(3^{\frac32(q-1)}) &= q
\end{align*}
and in this way we generate a new solution to the given equation.
This shows the solution we found is not unique when $a$
is not a power of $2$.

Conversely, suppose $a = 2^\ell$ is a power of $2$ and
$x$ is an integer with
\[ g(x) = a = 2^\ell. \]
Note that if $y$ is an odd prime power, then
\begin{itemize}
  \ii $\nu_2(g(y)) = 0$, and
  \ii $g(y) > 1$.
\end{itemize}
So by measuring $\nu_2$,
we get $\nu_2(g(x)) = \ell \implies \nu_2(x) = 2a-2$
matching the solution we found before.
But then for size reasons, we must have $x = 2^{2a-2}$, as desired.

\end{document}
