Number of Positive Divisors

**demode** · March 2nd 2011, 10:10 PM

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.

**PaulRS** · March 3rd 2011, 02:08 AM

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

**tonio** · March 3rd 2011, 02:11 AM

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.

.

**demode** · March 4th 2011, 01:00 PM

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

.

**demode** · March 5th 2011, 09:17 PM

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...

**PaulRS** · March 6th 2011, 03:35 AM

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.

Thread: Number of Positive Divisors

LinkBack

Thread Tools

Display

Number of Positive Divisors

Similar Math Help Forum Discussions

Number of positive divisors of n

How many positive divisors of n^2...

Running Through Positive Divisors

Positive divisors

positive integral divisors

Search Tags