1
$\begingroup$

Problem: For any positive integer $n$, prove that $\tau(n)\leq 2\sqrt{n}.$

My Attempt: For every divisor $d_1<d_2...<d_k$ less than $\sqrt{n}$ we have divisors $n/d_1,n/d_2......n/d_k$. Thus $\tau(n)\leq 2k.$ How do we show that $k\leq \sqrt{n}$?

Note: Please do not mark this question as a duplicate. I have read other answers to this question and most of them provide hints or unjustified assertions such as the number of divisors less that $\sqrt{n}$ are less than $\sqrt{n}$ itself. I specifically want to know why is $k\leq \sqrt{n}$ true in order to complete the proof.

$\endgroup$
  • $\begingroup$ What is $\tau(n)$? The number of divisor of $n$? $\endgroup$ – Arthur Nov 10 '16 at 9:03
  • $\begingroup$ @Arthur Yes. $\tau(n)$ is the number of positive divisors of $n$. $\endgroup$ – nls Nov 10 '16 at 9:23
4
$\begingroup$

Well, your proof is almost complete. Notice that each of the $d_i$ is less than $\sqrt{n}$ and they are different. There could be no more than $\sqrt{n}$ positive integers less than $\sqrt{n}$. So $k\leq\sqrt{n}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.