Find all odd natural numbers $n$ such that $d(n)$ is the largest divisor of the number $n$ different from $n$. ($d(n)$ is the number of divisors of the number n including $1$ and $n$ ).
Problem
Source: Balkan BMO Shortlist 2016 N2
Tags: divisor, maximum, number theory, odd, IMO Shortlist
31.07.2019 14:16
The fact that $n$ is an odd positive integer means there are $k$ odd primes $p_1 < p_2 < \cdots < p_k$ and $k$ positive integers $r_1,r_2, \ldots , r_k$ s.t. $(1) \;\; n = \prod_{i=1}^k p_i^{r_i}$. The largest divisor of $n$ different from $n$ is ${\textstyle \frac{n}{p_1}}$. Consequently we obtain the equation $\prod_{i=1}^k (r_i + 1) = \frac{n}{p_1}$, which according to (1) is equivalent to $(2) \;\; \prod_{i=1}^k \frac{p_i^{r_i}}{r_i + 1} = p_1$. If $r$ is a constant positive integer, then the function ${\textstyle \frac{x^r}{r+1}}$ is strictly increasing when $x \geq 2$. Consequently by (2) $(3) \;\; p_1 \geq \prod_{i=1}^k \frac{p_i}{2}$. If $k \geq 2$, then $2 \geq \prod_{i=2}^k \frac{p_i}{2} \geq \frac{5}{2}$, a contradiction implying $k=1$. Hence $n = p_1^{r_1}$, which according to (2) give us $(4) \;\; r_1 + 1 = p_1^{r_1-1}$. Clearly $r_1 \neq 1$ by (4). Therefore $r_1 \geq 2$, which according to (4) give us $1 = \frac{p_1^{r_1 - 1}}{r_1+1} \geq \frac{5^{2-1}}{2+1} = \frac{p_1}{3}$, yielding $p_1 \leq 3$ and equality iff $p_1=3$ and $r_1=2$. Conclusion: The only positive integer satisfying the given conditions is $n = 3^2 = 9$.
02.10.2019 17:55
16.09.2023 10:40
Let's solve the problem for any $n\geq 2$, rather than just odd, it is not really harder. Answer: $8$, $9$, $12$ Let $n=\prod_{i=1}^k p_i^{e_i}$ for primes $p_1 < p_2 < \ldots < p_k$ and $e_i \geq 1$. The number of divisors of $n$ is $(e_1 + 1)(e_2+1)\cdots (e_k+1)$, while the largest divisor of $n$ less than $n$ is $\frac{n}{p_1} = p_1^{e_1-1}p_2^{e_2}\ldots p_k^{e_k}$. We must have $$ (e_1 + 1)(e_2+1)\cdots (e_k+1) = p_1^{e_1-1}p_2^{e_2}\ldots p_k^{e_k}.$$ Suppose firstly that $e_1 \geq 2$ and $p_1 \geq 3$. The inequalities $3^{x-1} \geq x + 1$ and $5^y > y + 1$ hold for all $x\geq 2$ andd $y\geq 1$ (with equality in the former only for $x=2$; prove all these by induction), so for $k\geq 2$ we have no solution (the right-hand side exceeds the left-hand one), while for $k=1$ we get only $p_1=3$, $e_1=2$, i.e. $n=9$. Now suppose $e_1 \geq 3$ and $p_1 = 2$. Since $2^{x-1} \geq x+1$ for $x\geq 3$ (with equality only for $x=3$) and $3^y > y+1$ for $y\geq 1$, then for $k\geq 2$ we have no solution, while for $k=1$ the only possibility is $p_1 = 2$ and $e_1 = 3$, i.e. $n=8$. Now let $p_1 = e_1 = 2$, i.e. $\frac{3}{2}(e_2+1)\cdots (e_k+1) = p_2^{e_2}\ldots p_k^{e_k}$. Since $3^x \geq \frac{3}{2}(x+1)$ for $x\geq 1$ (with equality only for $x=1$, prove this by induction), then for $k\geq 2$ we have no solution, while for $k=1$ we get $p_2 = 3$ with $e_2 = 1$, i.e. $n=12$. Finally, treat $e_1 = 1$, i.e. working with $2(e_2+1)\cdots (e_k+1) = p_2^{e_2}\ldots p_k^{e_k}$. But here the right-hand side is odd (since $p_i \geq 3$ for $i\geq 2$), while the left-hand side is even, contradiction.
19.11.2024 16:34
A significantly quicker argument when $n$ is even: $\frac{n}{2} = \tau(n) \leq 2\sqrt{n}$, so $n\leq 16$.
21.12.2024 08:16