11
$\begingroup$

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}$?

2 Answers 2

19

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.

4

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.