# Thread: Number Theoretic Function t(n) or "tao" Proof

1. ## Number Theoretic Function t(n) or "tao" Proof

t(n) = number of positive divisors of n

For n => 1, prove that t(n) <= 2sqrt(n)

Hint: If d | n, then one of d or n/d is less than or equal to sqrt(n).

I do not know where to start with this problem. This is a homework question so I just need some assistance getting started with this problem. Also, I'm not sure how to use the hint in this problem. Thanks for your help.

2. ## Re: Number Theoretic Function t(n) or "tao" Proof

If you don't know how to handle a problem, you should try to look at a few examples first (and in this case, see how the hint plays a role in the example).

Let's take a look at the problem for $n=60$. We'd like to count up the number of divisors for $60$. We can just use the "elementary school" method, by looking at pairs of divisors (we get one "big" and one "small): $1$ and $60$, $2$ and $30$, $3$ and $20$, and so on. When can we stop checking? We stop at $\lfloor \sqrt{60}\rfloor=7$, since $8$ and its corresponding "big" divisor would exceed $60$. (In other words, they would have to multiply to $64$ or more.) So with respect to the original problem, if we want to count up the divisors, we only need to find the divisors less that $\sqrt{60}$ and double them (since everything comes in pairs). In this case, there are $12$ divisors, which is less that $2 \sqrt{60}$.

Can you see how to apply this for the general $n$?

3. ## Re: Number Theoretic Function t(n) or "tao" Proof

Ok, that makes sense. So here is what I'm thinking: Clearly, the result holds for prime numbers of n since t(n) = 2 if n is prime and 2 <= 2sqrt(n) holds for any prime n. Thus, if n is composite, then n = d*e for some integers d and e. Either d <= sqrt(n) or n/d = e <= sqrt(n) meaning that one of these divisors is less than or equal to sqrt(n). Then since divisors come in pairs, there are t(n)/2 many divisors each less than or equal to sqrt(n). But then, how would I show that t(n)/2 <= sqrt(n)? Now, this part I'm stuck on.

4. ## Re: Number Theoretic Function t(n) or "tao" Proof

You're almost there. You only have to consider the worst case scenario: maybe all of the numbers less than or equal to $\sqrt{n}$ are divisors. (By the way, can you find an example where this happens?) Then, $\tau(n)/2=\sqrt{n}$. Otherwise, the number of divisors is less than that: $\tau(n)/2<\sqrt{n}$. In summary, we can say $\tau(n)/2\leq \sqrt{n}$, which gives the result.

How does that sound?

5. ## Re: Number Theoretic Function t(n) or "tao" Proof

Originally Posted by roninpro
You're almost there. You only have to consider the worst case scenario: maybe all of the numbers less than or equal to $\sqrt{n}$ are divisors. (By the way, can you find an example where this happens?) Then, $\tau(n)/2=\sqrt{n}$. Otherwise, the number of divisors is less than that: $\tau(n)/2<\sqrt{n}$. In summary, we can say $\tau(n)/2\leq \sqrt{n}$, which gives the result.

How does that sound?
oh, oh i know this one! 6, right? or is it 12?

6. ## Re: Number Theoretic Function t(n) or "tao" Proof

I'm having trouble making the connection that t(n)/2 <= sqrt(n). I see that there are t(n)/2 many divisors less than sqrt(n) but I don't see how I can determine that t(n)/2 itself is less than or equal to sqrt(n).

7. ## Re: Number Theoretic Function t(n) or "tao" Proof

suppose n is a perfect square. then n has exactly one divisor that occurs as its own quotient. all the others occur in pairs, one is less than √n, and the other is greater than √n.

therefore, in this case τ(n) ≤ 2(√n-1) + 1 = 2√n - 1 < 2√n.

on the other hand, suppose that n is not a perfect square. then all divisors of n occur in pairs, one is less than √n, one is greater than √n.

if k is the greatest integer less than √n, then τ(n) ≤ 2k < 2√n

the pairing we are making, is pairing d with n/d, for each divisor d ≤ √n.

8. ## Re: Number Theoretic Function t(n) or "tao" Proof

I figured it out now. Thanks to all who responded to this!