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


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.


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.