# Thread: Number of Positive Divisors

1. ## Number of Positive Divisors

If d(n) denotes the number of divisors (+ve) of integer n. Prove that $d(n) \leq 2 \sqrt{n}$.

So, we are not told if n is prime or composite, so I don't know how to approach this proble. But if we suppose the prime factorization of n is $n=p_1^{\alpha_1} p_2^{\alpha_2}...p_r^{\alpha_r}$,

then number of divisors of n are: $d(n)=(\alpha +1)...(\alpha_r+1)$.

So, how do I show that $d(n)=(\alpha +1)...(\alpha_r+1) \leq 2 \sqrt{n}$?

I also know that if n is composite then the number of its divisors are less than or equal to $\left\lfloor \sqrt{n} \right\rfloor$ (the notation means the integer part of $\sqrt{n}$), but I don't know if that helps at all.

Any helps is really appreciated.

2. Consider the pairs $\left(d, \tfrac{n}{d} \right)$ for the divisors $d\leq \sqrt{n}$ and show that each divisor must appear as one -at least one- of the entries at some pair. (consider the cases $\text{divisor}\leq \sqrt{n}$ and $\text{divisor}\geq \sqrt{n}$ )

Can you finish the proof?

PS: For a composite, the number of divisors need not be less or equal to $\sqrt{n}$ as you stated, rather the smallest divisor ( > 1) must be less or equal than $\sqrt{n}$.

3. Originally Posted by demode
If d(n) denotes the number of divisors (+ve) of integer n. Prove that $d(n) \leq 2 \sqrt{n}$.

So, we are not told if n is prime or composite, so I don't know how to approach this proble. But if we suppose the prime factorization of n is $n=p_1^{\alpha_1} p_2^{\alpha_2}...p_r^{\alpha_r}$,

then number of divisors of n are: $d(n)=(\alpha +1)...(\alpha_r+1)$.

So, how do I show that $d(n)=(\alpha +1)...(\alpha_r+1) \leq 2 \sqrt{n}$?

I also know that if n is composite then the number of its divisors are less than or equal to $\left\lfloor \sqrt{n} \right\rfloor$ (the notation means the integer part of $\sqrt{n}$),

This is false: 36 has 9 positive divisors, and $9>6=\sqrt{36}$ . What did you really mean here?

Tonio

but I don't know if that helps at all.

Any helps is really appreciated.
.

4. Originally Posted by PaulRS
Consider the pairs $\left(d, \tfrac{n}{d} \right)$ for the divisors $d\leq \sqrt{n}$ and show that each divisor must appear as one -at least one- of the entries at some pair.
I didn't understand this line very well. Could you please explain a bit more clearly what I need to be doing? And why are you considering the pairs (d,d/n)?

Originally Posted by Tonio
This is false: 36 has 9 positive divisors, and . What did you really mean here?
Oops I made a mistake, I meant that the smallest prime divisor of a composite number n is less than or equal to .

5. Originally Posted by PaulRS
Consider the pairs $\left(d, \tfrac{n}{d} \right)$ for the divisors $d\leq \sqrt{n}$ and show that each divisor must appear as one -at least one- of the entries at some pair. (consider the cases $\text{divisor}\leq \sqrt{n}$ and $\text{divisor}\geq \sqrt{n}$ )

Can you finish the proof?
Why do you consider the pairs only for divisors such that $d\leq \sqrt{n}$? We don't care about the size of the divisors, only the number of divisors. The question only asks for the number of divisors, that's what the notation d(n) means. Furthermore I'm not sure how to prove that at least one of the divisors must appear in those pairs...

6. I meant to say that the set of positive integers dividing n can be written as: $\left \{ x \in \mathbb{Z}^+ | x \text{ divides } n \right \} = \displaystyle\bigcup_{d |n \text{ and } 1\leq d \leq \sqrt{n} } \left \{ d, \displaystyle\frac{n}{d} \right \}$ $(*)$

And clearly we have $\displaystyle\bigcup_{d |n \text{ and } 1\leq d \leq \sqrt{n} } \left \{ d, \displaystyle\frac{n}{d} \right \} \subseteq \bigcup_{d = 1}^{\lfloor \sqrt{n} \rfloor} \left \{ d, \displaystyle\frac{n}{d} \right \}$ and here the cardinal of the RHS is no more than $2\cdot \sqrt{n}$

The key to $(*)$ is noting that:
Any divisor which is less or equal to $\sqrt{n}$ appears on the RHS, now suppose $k$ were a divisor of $n$ greater than $\sqrt{n}$, in this case we have that $k\cdot \tfrac{n}{k} = n$ and so $\tfrac{n}{k}$ is a divisor of $n$ but $\tfrac{n}{k} <\sqrt{n}$ thus we have the set $\left \{ \frac{n}{k}, k \right \}$ as one of the terms of the union.
That proves that the LHS is a subset of the RHS, but of course if d is a divisor of n, then so is n/d and so ths RHS is a subset of the LHS.