# Prove that $d(n)\leq 2\sqrt{n}$

In Waclaw Sierpinski’s book Elementary Theory of Numbers on page 168 there is the following exercise:

“Exercises. 1. Prove that for natural numbers $n$ we have $d(n) \leq 2\sqrt{n}$,” where $d(n)$ is the number of divisors of n.

As a hint right below is given: “The proof follows from the fact that of two complementary divisors of a natural number $n$ one is always not greater than $\sqrt{n}$.

I understand the hint but I don’t know how it can be used to prove $d(n)\leq 2\sqrt{n}$.

Complementary divisors are pairs of divisors that when multiplied gives the number that is to be divided. For example the number $120$ has the complementary divisors:
\begin{align*}
& 1, 120 \\
& 2, 60 \\
& 3, 40 \\
& 4, 30 \\
& 5, 24 \\
& 6, 20 \\
& 8, 15 \\
& 10, 12 \\
\end{align*}
How do you prove that $d(n) \leq 2\sqrt{n}$?

#### Solutions Collecting From Web of "Prove that $d(n)\leq 2\sqrt{n}$"

Suppose first that $n$ is not a square. Then to each divisor less than $\sqrt{n}$ there is one and only one “complementary” divisor which is greater than $\sqrt{n}$. So the number of divisors of $n$ is equal to twice the number of divisors of $n$ that are smaller than $\sqrt{n}$.

How many divisors can $n$ have that are smaller than $\sqrt{n}$? Can you give a very trivial upper bound to that quantity?

The argument is essentially the same if $n$ is a perfect square, except that in that case you have one special divisor, namely, $\sqrt{n}$, which is not paired up with anyone. Yet the bounding argument should still be (essentially) the same.

The function which sends a divisor $d$ of $n$ to the smallest of $d$ and $n/d$ is at most $2$-to-$1$ hence the size of the source set is at most twice the size of the target set. The source set is the set of divisors of $n$ and has size $d(n)$. The target set is made of (some) positive integers not greater than $\sqrt{n}$ hence it has size at most $\sqrt{n}$. QED.