The number $A$ is a product of $n$ distinct natural numbers. Prove that $A$ has at least $\frac{n(n-1)}{2}+1$ distinct divisors (including 1 and $A$).
Problem
Source: IV International Festival of Young Mathematicians Sozopol 2013, Theme for 10-12 grade
Tags: number theory, Divisors
kaede
24.01.2020 15:08
It is sufficient to show that the following proposition $P( n)$ is always true by induction on $n$ :
$P( n)$: Any product of distinct $n$ natural numbers greater than $1$ has more than $n( n+1) /2$ distinct positive divisors.
It is not difficult to verify that $P( n)$ is true for $n=1,2,3,4,5.$
Suppose that $P(n)$ is true for some $n\geq 5 $
Let $A=a_{1} a_{2} \dotsc a_{n+1}$ where $a_{1} ,a_{2} \dotsc a_{n+1}$ are distinct and greater than $1$.
First, suppose that $A$ is a power of prime number $p$.
It is clear that $p^{( n+1)( n+2) /2} \mid A$, so we have $\tau ( A) >( n+1)( n+2) /2$.
Next, suppose that $A$ has at least two distinct prime divisors.
Let $e=\min\{\nu _{p}( A) ;\ p\mid A\}$
Let $q$ be a prime divisor of $A$ such that $\nu _{q}( A) =e$.
We consider the following two cases $( 1) ,( 2)$.
$( 1)$ the number of distinct prime divisors of $A$ is at least $3$.
Let $h$ be a positive integer such that $q\mid a_{h}$.
Since $P( n)$ is true, we have $\tau ( A/a_{h}) >n( n+1) /2$.
So $\tau ( A) \geq n( n+1) /2+( n( n+1) /2)^{2/3} >( n+1)( n+2) /2$.
Thus $P( n+1)$ is true.
(2) the number of distinct prime divisors of $A$ is exactly $2$.
Let $m=\max\{\nu _{q}( a_{i}) |\ 1\leq i\leq n+1\}$.
Suppose that $m\geq 2$.
Let $h$ be a positive integer such that $q^{2} \mid a_{h}$.
Since $P( n)$ is true, we have $\tau ( A/a_{h}) >n( n+1) /2$.
So $\tau ( A) \geq n( n+1) /2+2( n( n+1) /2)^{1/2} >( n+1)( n+2) /2$.
Finally, suppose that $m=1$.
Let $p$ be the largest prime divisor of $A$.
Let $t=\#\{j\in \mathbb{N} |\ q\mid a_{j}\}$.
Then we have $\nu _{q}( A) \geq t$ and $\nu _{p}( A) \geq t^{2} -( n+2) t+\left( n^{2} +3n+2\right) /2$.
So $\tau ( A) \geq ( t+1)\left( t^{2} -( n+2) t+\left( n^{2} +3n+4\right) /2\right)$.
Let $f( x)$ be the real-valued function defined by the following :
$f( x) =( x+1)\left( x^{2} -( n+2) x+\left( n^{2} +3n+4\right) /2\right)$.
We can verify that $f'( x) >0$.
So $\tau ( A) \geq f( 1) =n^{2} +n+2 >( n+1)( n+2) /2$.
Thus $P( n+1)$ is true in the case $( 2)$.
Therefore, $P( n)$ is true for all positive integers $n$.
$\blacksquare $
62861
25.01.2020 11:25
Let $A = a_1 \cdots a_n$ with $a_{k+1} - a_k \ge 1$ for all $k$. Then \[1, a_2, \dots, a_n, a_2a_n, \dots, a_{n-1}a_n, a_2a_{n-1}a_n, \dots, a_{n-2}a_{n-1}a_n, \dots, a_2 \cdots a_n\]are $\tfrac{n(n-1)}{2} + 1$ different divisors of $A$.