Find the largest constant $c>0$ such that for every positive integer $n\ge 2$, there always exist a positive divisor $d$ of $n$ such that $$d\le \sqrt{n}\hspace{0.5cm} \text{and} \hspace{0.5cm} \tau(d)\ge c\sqrt{\tau(n)}$$where $\tau(n)$ is the number of divisors of $n$. Proposed by Mohd. Suhaimi Ramly
Problem
Source: Malaysian SST 2023 P4
Tags: number theory
vsamc
31.08.2023 15:48
The answer is $c = \boxed{\frac{1}{\sqrt{2}}}$.
Take $(d, n) = (1, 2)$ to see that we must have $c\leq \frac{1}{\sqrt{2}}$.
Now, we will show that $c = \frac{1}{\sqrt{2}}$ works.
First, we will show that such a $c$ works for a squarefree $n$. Let $n = p_1p_2\cdots p_r$ for primes $p_i$ and some $r\geq 1$. If $r$ is even, let $d$ be an element in $\{p_1p_2\cdots p_{r/2}, p_{r/2+1}p_{r/2+2}\cdots p_r\}$ which is at most $\sqrt{n}$ (they multiply to $n$, so such an element exists (also, they are both divisors of $n$)). Then, we have that $$\tau(d) \geq 2^{r/2} > 2^{(r-1)/2} = \sqrt{\frac{2^r}{2}} = c\sqrt{\tau(n)}.$$If $r$ is odd, let $d$ be an element in $\{p_1p_2\cdots p_{(r-1)/2}, p_{(r+1)/2}p_{(r+3)/2}\cdots p_r\}$ which is at most $\sqrt{n}$ (they multiply to $n$, so such an element exists (also, they are both divisors of $n$)). Then, we have that $$\tau(d) \geq 2^{(r-1)/2} = \sqrt{\frac{2^r}{2}} = c\sqrt{\tau(n)}.$$So in both cases, there exists such a $d$, so there always exists such a $d$ when $n$ is squarefree.
Now, we tackle the general case. Let $n = PQ$, where $$P = \prod_{\nu_p(n)=1}p,$$and $$Q = \prod_{\nu_p(n)\geq 2}p^{\nu_p(n)}.$$Then, note that since $P$ is squarefree, there exists a $P_d \mid P$ for which $P_d \leq \sqrt{P}$ and $\tau(P_d) \geq c\sqrt{\tau(P)}$. Now, let $$Q_d = \prod_{\nu_p(n) \geq 2}p^{\lfloor \nu_p(n)/2\rfloor}.$$Then, note that $Q_d \mid Q$, as $\lfloor \nu_p(n)/2\rfloor \leq \nu_p(n)$, $Q_d \leq \sqrt{Q}$, since $$Q_d = \prod_{\nu_p(n)\geq 2}p^{\lfloor \nu_p(n)/2\rfloor} \leq \prod_{\nu_p(n)\geq 2}p^{\nu_p(n)/2} = \sqrt{Q},$$and $\tau(Q_d) \geq \sqrt{\tau(Q)}$ (no, this is not a typo), since we have that $\left \lfloor \frac{x}{2}\right \rfloor + 1 \geq \sqrt{x+1}$ for all positive integral $x\geq 2$ (it is not hard to show, since in both cases, it's just a quadratic >= 0 after squaring and rearranging), so $$\tau(Q_d) = \prod_{\nu_p(n)\geq 2}\left(\lfloor \nu_p(n)/2 \rfloor + 1\right) \geq \prod_{\nu_p(n)\geq 2}\sqrt{\nu_p(n)+1} = \sqrt{\tau(Q)}.$$
Therefore, we have that if $d = P_dQ_d$, then since $P_d\mid P, Q_d\mid Q$, we have $$d = P_dQ_d \mid PQ = n,$$since $P_d \leq \sqrt{P}, Q_d\leq \sqrt{Q}$, we have $$d = P_dQ_d \leq \sqrt{PQ} = \sqrt{n},$$and since $\gcd(P,Q) = \gcd(P_d, Q_d) = 1$, $\tau(P_d) \geq c\sqrt{\tau(P)}$, $\tau(Q_d) \geq \sqrt{\tau(Q)}$, we have $$\tau(d) = \tau(P_dQ_d) = \tau(P_d)\tau(Q_d) \geq (c\sqrt{\tau(P)})(\sqrt{\tau(Q)}) = c\sqrt{\tau(P)\tau(Q)} = c\sqrt{\tau(PQ)} = c\sqrt{\tau(n)},$$so such a $d$ satisfies the conditions for $c = \frac{1}{\sqrt{2}}$ no matter which $n\geq 2$ we choose, as desired.
Thus, $c = \frac{1}{\sqrt{2}}$ is the maximal constant, as claimed. $\blacksquare$
giannis2006
31.08.2023 16:55
For $n=30$ we get that $c \leq \frac{1}{\sqrt{2}}$. I will prove that it satisfies. Firstly suppose that $n$ is squarefree. Let $ n= \prod_{i=1}^{k} p_i$, then $\tau(n)=2^k$ and $c\sqrt{\tau(n)}=\frac{1}{\sqrt{2}} \cdot \sqrt{2^k}=2^{\frac{k-1}{2}}$. I will prove it with induction in $k$. For $k=1,2,3$ it is obvious. Now suppose that it holds for $k=m$ and I will show it for $k=m+2$. Let $n=\prod_{i=1}^{m+2} p_i$ and suppose WLOG $p_1$ be the smallest of $p_i$. Applying the inductive ypothesis for $k=m$ we get that there exist a divisor $d'$ of $\frac{n}{p_1p_2}$ such that $d'\leq \sqrt{\frac{n}{p_1p_2}}$ and $\tau(d')\geq c \sqrt{\tau(\frac{n}{p_1p_2})}=2^{\frac{m-1}{2}}$. I choose $d=d'p_1$. Then we have that: $\tau(d)=\tau(d') \tau(p_1) = 2\tau(d') \geq 2^{\frac{m+1}{2}}=c \sqrt{\tau(n)}$ and also $d=d'p_1 \leq \sqrt{\frac{n}{p_1p_2}} \cdot p_1 < \sqrt{n}$, hence the induction is completed. Now let $ n= \prod_{i=1}^{k} p_i^{a_i}$ and I will prove it with induction in $k$. For $k=1$ it is obvious. Suppose that it is true for $k=m$. I will prove it for $k=m+1$. If $a_i=1$ for all $i$, then $n$ is squarefree and we return to the previous case. So let $a_j>1$ for some $j$. Let WLOG $j=1=>a_1>1$. Applying the inductive hypothesis for $\frac{n}{p_1^{a_1}}$, we get that there exist a divisor $d'$ of $\frac{n}{p_1^{a_1}}$ satisfying the condition for $\frac{n}{p_1^{a_1}}$. I choose $d=d' \cdot p_1^{\left\lfloor\frac{a_1}{2}\right\rfloor}$. Then applying the inductive ypothesis we get that: $\tau(d)=\tau(d') \tau(p_1^{\left\lfloor\frac{a_1}{2}\right\rfloor}) = (\left\lfloor\frac{a_1}{2}\right\rfloor+1) \tau(d') \geq (\left\lfloor\frac{a_1}{2}\right\rfloor+1) c \sqrt { \tau(\frac{n}{p_1^{a_1}})} \geq c\sqrt {\tau(n)}$, where the last inequality holds because $a_1>1$. Also $d' \leq \sqrt{\frac{n}{p_1^{a_1}}} => d' \cdot p_1^{\frac{a_1}{2}} \leq \sqrt{n} => d' \cdot p_1 ^{\left\lfloor\frac{a_1}{2}\right\rfloor} \leq \sqrt{n} => d \leq \sqrt{n} $ and the induction is completed. Hence, indeed, the largest value of $c$ is $\frac{1}{\sqrt{2}}$.