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

\begin{document}
\title{TSTST 2020/8}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 50}
\maketitle

\section*{Problem}
For every positive integer $N$,
let $\sigma(N)$ denote the sum of the positive integer divisors of $N$.
Find all integers $m \ge n \ge 2$ satisfying
\[ \frac{\sigma(m)-1}{m-1}
  = \frac{\sigma(n)-1}{n-1} = \frac{\sigma(mn)-1}{mn-1}.  \]

\section*{Video}
\href{https://www.youtube.com/watch?v=NOjZ_DKUgxc}{\texttt{https://youtu.be/NOjZ\_DKUgxc}}

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

\newpage

\section*{Solution}
The answer is that $m$ and $n$ should be powers
of the same prime number.
These all work because for a prime power we have
\[
  \frac{\sigma(p^e) - 1}{p^e - 1}
  = \frac{(1 + p + \dots + p^e) - 1}{p^e - 1}
  = \frac{p(1 + \dots + p^{e-1})}{p^e - 1}
  = \frac{p}{p-1}.
\]
So we now prove these are the only ones.
Let $\lambda$ be the common value of the three fractions.

\begin{claim*}
  Any solution $(m,n)$ should satisfy
  $d(mn) = d(m) + d(n) - 1$.
\end{claim*}
\begin{proof}
  The divisors of $mn$ include the divisors of $m$,
  plus $m$ times the divisors of $n$ (counting $m$ only once).
  Let $\lambda$ be the common value; then this gives
  \begin{align*}
    \sigma(mn) & \ge \sigma(m) + m\sigma(n) - m\\
    & = (\lambda m - \lambda + 1) + m(\lambda n - \lambda + 1) - m\\
    & = \lambda mn - \lambda + 1
  \end{align*}
  and so equality holds.
  Thus these are all the divisors of $mn$,
  for a count of $d(m) + d(n) - 1$.
\end{proof}

\begin{claim*}
  If $d(mn) = d(m) + d(n) - 1$ and $\min(m, n) \ge 2$,
  then $m$ and $n$ are powers of the same prime.
\end{claim*}
\begin{proof}
  Let $A$ denote the set of divisors of $m$ and $B$ denote the set of divisors of $n$.
  Then $|A \cdot B| = |A| + |B| - 1$ and $\min(|A|, |B|) > 1$,
  so $|A|$ and $|B|$ are geometric progressions with the same ratio.
  It follows that $m$ and $n$ are powers of the same prime.
\end{proof}

\begin{remark*}[Nikolai Beluhov]
  Here is a completion not relying on $|A \cdot B| = |A| + |B| - 1$.
  By the above arguments, we see that every divisor of $mn$ is
  either a divisor of $n$, or $n$ times a divisor of $m$.

  Now suppose that some prime $p \mid m$ but $p \nmid n$.
  Then $p \mid mn$ but $p$ does not appear in the above classification,
  a contradiction.
  By symmetry, it follows that $m$ and $n$ have the same prime divisors.

  Now suppose we have different primes $p \mid m$ and $q \mid n$.
  Write $\nu_p(m) = \alpha$ and $\nu_p(n) = \beta$.
  Then $p^{\alpha+\beta} \mid mn$, but it does not appear in the above characterization,
  a contradiction.
  Thus, $m$ and $n$ are powers of the same prime.
\end{remark*}

\begin{remark*}
  [Comments on the function in the problem]
  Let $f(n) = \frac{\sigma(n)-1}{n-1}$.
  Then $f$ is not really injective even outside the above solution;
  for example, we have $f(6 \cdot 11^k) = \frac{11}{5}$ for all $k$,
  plus sporadic equivalences like $f(14) = f(404)$,
  as pointed out by one reviewer during test-solving.
  This means that both relations should be used at once, not independently.
\end{remark*}

\begin{remark*}
  [Authorship remarks]
  Ankan gave the following story for how he came up with the problem
  while thinking about so-called \emph{almost perfect} numbers.
  \begin{quote}
  I was in some boring talk when I recalled a conjecture
  that if $\sigma(n) = 2n-1$, then $n$ is a power of $2$.
  For some reason (divine intervention, maybe) I had the double idea of
  (1) seeing whether $m$, $n$, $mn$ all almost perfect
  implies $m$, $n$ powers of $2$,
  and (2) trying the naive divisor bound to resolve this.
  Through sheer dumb luck this happened to work out perfectly.
  I thought this was kinda cool but I felt that I hadn't really
  unlocked a lot of the potential this idea had:
  then I basically tried to find the ``general situation''
  which allows for this manipulation,
  and was amazed that it led to such a striking statement.
  \end{quote}
\end{remark*}

\end{document}
