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