\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USEMO 2021/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 89}
\maketitle
\section*{Problem}
Find all integers $n \ge 1$
such that $2^n - 1$ has exactly $n$ positive integer divisors.
\section*{Video}
\href{https://youtu.be/kjcY8qQAi5U}{\texttt{https://youtu.be/V-9UBJr7aDI}}
\newpage
\section*{Solution}
The valid $n$ are $1$, $2$, $4$, $6$, $8$, $16$, $32$.
They can be verified to work through inspection,
using the well known fact that the Fermat prime
$F_i = 2^{2^i}+1$ is indeed prime for $i = 0, 1, \dots, 4$
(but not prime when $i=5$).
We turn to the proof that these are the only valid values of $n$.
In both solutions that follow, $d(n)$ is the divisor counting function.
\paragraph{First approach (from author)}
Let $d$ be the divisor count function.
Now suppose $n$ works,
and write $n = 2^k m$ with $m$ odd.
Observe that
\[
2^n - 1
= (2^m - 1) (2^m + 1) (2^{2m} + 1) \cdots (2^{2^{k-1}m} + 1),
\]
and all $k+1$ factors on the RHS are pairwise coprime.
In particular,
\[
d(2^m - 1) d(2^m + 1) d(2^{2m} + 1) \cdots d(2^{2^{k-1}m} + 1)
= 2^k m.
\]
Recall the following fact, which follows from Mih\v{a}ilescu's theorem.
\begin{lemma*}
$2^r - 1$ is a square if and only if $r = 1$, and
$2^r + 1$ is a square if and only if $r = 3$.
\end{lemma*}
Now, if $m \ge 5$, then all $k+1$ factors on the LHS are even,
a contradiction.
Thus $m \le 3$.
We deal with both cases.
If $m = 1$, then the inequalities
\begin{align*}
d(2^{2^0} - 1) & = 1\\
d(2^{2^0} + 1) & \ge 2\\
d(2^{2^1} + 1) & \ge 2\\
& \vdots\\
d(2^{2^{k-1}} + 1) & \ge 2
\end{align*}
mean that it is necessary and sufficient for all of
$2^{2^0} + 1,\ 2^{2^1} + 1,\ \dots,\ 2^{2^{k-1}} + 1$
to be prime.
As mentioned at the start of the problem,
this happens if and only if $k \le 5$,
giving the answers $n \in \{1, 2, 4, 8, 16, 32\}$.
If $m = 3$, then the inequalities
\begin{align*}
d(2^{3 \cdot 2^0} - 1) & = 2\\
d(2^{3 \cdot 2^0} + 1) & = 3\\
d(2^{3 \cdot 2^1} + 1) & \ge 4\\
& \vdots\\
d(2^{3 \cdot 2^{k-1}} + 1) & \ge 4
\end{align*}
mean that $k \ge 2$ does not lead to a solution.
Thus $k \le 1$, and the only valid possibility turns out to be $n = 6$.
Consolidating both cases,
we obtain the claimed answer $n \in \{1, 2, 4, 6, 8, 16, 32\}$.
\paragraph{Second approach using Zsigmondy (suggested by reviewers)}
There are several variations of this Zsigmondy solution;
we present the approach found by Nikolai Beluhov.
Assume $n \ge 7$, and let $n = \prod_1^m p_i^{e_i}$ be the prime
factorization with $e_i > 0$ for each $i$.
Define the numbers
\begin{align*}
T_1 &= 2^{p_1^{e_1}} - 1 \\
T_2 &= 2^{p_2^{e_2}} - 1 \\
&\vdotswithin{=} \\
T_m &= 2^{p_m^{e_m}} - 1.
\end{align*}
We are going to use two facts about $T_i$.
\begin{claim*}
The $T_i$ are pairwise relatively prime and
\[ \prod_{i=1}^m T_i \mid 2^n-1. \]
\end{claim*}
\begin{proof}
Each $T_i$ divides $2^n-1$,
and the relatively prime part follows from the identity
$\gcd(2^x-1,2^y-1)=2^{\gcd(x,y)}-1$.
\end{proof}
\begin{claim*}
The number $T_i$ has at least $e_i$ distinct prime factors.
\end{claim*}
\begin{proof}
This follows from Zsigmondy's theorem: each successive quotient
$(2^{p^{k+1}}-1) / (2^{p^k}-1)$ has a new prime factor.
\end{proof}
\begin{claim*}
[Main claim]
Assume $n$ satisfies the problem conditions.
Then both the previous claims are sharp in the following sense:
each $T_i$ has \emph{exactly} $e_i$ distinct prime divisors, and
\[
\left\{ \text{primes dividing } \prod_{i=1}^m T_i \right\}
= \left\{ \text{primes dividing } 2^n-1 \right\}.
\]
\end{claim*}
\begin{proof}
Rather than try to give a size contradiction directly from here,
the idea is to define an ancillary function
\[ s(x) = \sum_{p \ \text{prime}} \nu_p(x) \]
which computes the sum of the exponents in the prime factorization.
For example
\[ s(n) = e_1 + e_2 + \dots + e_m. \]
On the other hand, using the earlier claim, we get
\[ s(d(2^n-1)) \ge s\left( d\left( \prod T_i \right) \right) \ge e_1 +
e_2 + \dots + e_m = s(n). \]
But we were told that $d(2^n-1) = n$;
hence equality holds in all our estimates, as needed.
\end{proof}
At this point, we may conclude directly that $m=1$ in any solution;
indeed if $m \ge 2$ and $n \ge 7$,
Zsigmondy's theorem promises a primitive prime divisor of $2^n-1$
not dividing any of the $T_i$.
Now suppose $n = p^e$, and $d(2^{p^e}-1) = n = p^e$.
Since $2^{p^e}-1$ has exactly $e$ distinct prime divisors,
this can only happen if in fact
\[ 2^{p^e}-1 = q_1^{p-1} q_2^{p-1} \dots q_e^{p-1} \]
for some distinct primes $q_1$, $q_2$, \dots, $q_e$.
This is impossible modulo $4$ unless $p=2$.
So we are left with just the case $n=2^e$, and need to prove $e\le5$.
The proof consists of simply remarking that $2^{2^5}+1$
is known to not be prime,
and hence for $e \ge 6$ the number $2^{2^{e}}-1$
always has at least $e+1$ distinct prime factors.
\end{document}