Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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