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

$\endgroup$
1

3 Answers 3

22
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Consider the ordered pairs of complementary divisors of $n$, $(d_1,\frac nd_1),(d_2,\frac nd_2),\dots,(d_r,\frac nd_r),(\sqrt n,\sqrt n),(\frac nd_1,d_1),(\frac nd_2,d_2),\dots,(\frac nd_r,d_r)$

where $d_i\le\sqrt n\quad\forall i=1,2,\dots,r$

If $n$ is not a perfect square we exclude $(\sqrt n,\sqrt n)$. Let $S=\{(d_1,\frac nd_1),(d_2,\frac nd_2),\dots,(d_s,\frac nd_s)\}$ be the set of all the ordered pair where the first elements are $d_i's$; $d_s=d_r$ if $n$ is not a perfect square and $d_s=\sqrt n$ if $n$ is a perfect square. Let $m$ denote the number of elements of $S$. It is clear that $$d(n)\le2m\dots(1)\Bigl(d(n)\lt2m,\text{if $n$ is a perfect square and $d(n)=2m$ if $n$ is not a perfect square$\Bigl)$}$$ The number of elements of $S$ is equal to the number of $d_i's$. Suppose $n$ is divisible by all integers $\le\sqrt n\;$, then $d_1=1,d_2=2,d_3=3,\dots d_s=\sqrt n,$ then the number of $d_i's$ is $\sqrt n\;$ and therefore the number of $d_i's$ is at most $\sqrt n\,$. Thus, for every integer $n\ge 1$, the number of $d_i's\le\sqrt n\,$. Then, $$m\le\sqrt n\,\dots(2)$$ Now from equation $(1)$ and $(2)$, we get $$d(n)\le2\sqrt n$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .