Integer with largest number of divisors

Question

Prove that the number $83160= 2 ^{3} \cdot 3 ^{3}\cdot 5 \cdot 7 \cdot 11 $ has the largest number of divisors among all integers $≤10^5$.

My Attempt. The number $83160$ is so-called highly composite numbers and there are algorithms, for example here, for calculating such a numbers. So, I can make a computer program to calculate it. It is possible to prove it without any computer calculation?

Answer 1

Given a natural number $N$ let $N=p_1^{\alpha_1}\cdots p_n^{\alpha_n}$ be its decomposition into the product of powers of distinct prime numbers. Then the number of distinct divisors of $N$ is $$D(N)=(\alpha_1+1)\cdots (\alpha_n+1).$$

Thus, given the upper bound $\overline{N}$ for $N$, looking for the maximum of $D(N)$ it suffices to consider $p_i$ is the $i$-th prime number and $\alpha_1\ge \alpha_2\ge\dots\ge\alpha_n$.

Next, if $p_j^\alpha<p_i^\beta$ for some natural $\beta\le\alpha_i$ but $(\alpha_j+\alpha+1)(\alpha_i-\beta+1)\ge (\alpha_j+1)(\alpha_i+1)$ then we can replace $N$ by a smaller number $N\cdot p_j^\alpha p_i^{-\beta}$ without decreasing $D(N)$. In particular, putting $\beta=\alpha_i$ we can assume that for the required $N$ and for each distinct $i$ and $j$ holds $$p_i^{\alpha_i}<p_j^{(\alpha_j+1)(\alpha_i+1)-(\alpha_j+1)}= p_j^{(\alpha_j+1)\alpha_i},$$ that is $p_i<p_j^{\alpha_j+1}$. On the other hand, since we may additionally consider $\alpha_{n+1}=0$, we have $2(\alpha_i-\beta+1)<\alpha_i+1$ (that is $\alpha_i+1<2\beta$) for each $i\le n$ and natural $\beta$ such that $p_{n+1}<p_i^{\beta}$.

Let $\overline{N}=10^5$. If $p_n\ge 13$ then $p_1^{\alpha_1}\ge 8$ and $p_2^{\alpha_2}\ge 9$. Then $$N\ge 8\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13=360 360>\overline{N}.$$ Thus $p_n\le 11$. If $p_n=11$ then similarly to the above we can show that $\alpha_i=1$ for $i\ge 3$, so it remains to check a few remaining possibilities for $\alpha_1$ and $\alpha_2$.

If $p_n\le 7$ then $p_{n+1}\le 11$, so we have $\alpha_i+1<2\beta$ for each $i\le n$ and natural $\beta$ such that $11<p_i^{\beta}$. In particular, $\alpha_1\le 6$, $\alpha_2\le 4$, $\alpha_3\le 2$, and $\alpha_4\le 2$. Recall that the number $83160= 2^{3} \cdot 3^{3}\cdot 5 \cdot 7 \cdot 11$ has $(3+1)(3+1)(1+1) (1+1) (1+1)=128$ divisors. In order to $(\alpha_1+1) (\alpha_2+1) (\alpha_3+1) (\alpha_4+1)>128$ we have $\alpha_4\ge 1$, so $p_n=7$, and again it remains to check a few remaining possibilities for $\alpha_i$’s.