## You are here

Home$2^{\omega(n)} \le \tau(n) \le 2^{\Omega(n)}$

## Primary tabs

# $2^{{\omega(n)}}\leq\tau(n)\leq 2^{{\Omega(n)}}$

Throughout this entry, $\omega$, $\tau$, and $\Omega$ denote the number of distinct prime factors function, the divisor function, and the number of (nondistinct) prime factors function, respectively.

###### Theorem.

For any positive integer $n$, $2^{{\omega(n)}}\leq\tau(n)\leq 2^{{\Omega(n)}}$.

###### Proof.

Note that $2^{{\omega(n)}}$, $\tau(n)$, and $2^{{\Omega(n)}}$ are multiplicative. Also note that, for any positive integer $n$, the numbers $2^{{\omega(n)}}$, $\tau(n)$, and $2^{{\Omega(n)}}$ are positive integers. Therefore, it will suffice to prove the inequality for prime powers.

Let $p$ be a prime and $k$ be a positive integer. Thus:

$\begin{array}[]{rl}\displaystyle 2^{{\omega(p^{k})}}&=2\\ \\ \tau(p^{k})&=k+1\\ \\ \displaystyle 2^{{\Omega(p^{k})}}&=2^{k}\end{array}$

Hence, $2^{{\omega(p^{k})}}\leq\tau(p^{k})\leq 2^{{\Omega(p^{k})}}$. It follows that $2^{{\omega(n)}}\leq\tau(n)\leq 2^{{\Omega(n)}}$. ∎

###### Corollary.

For any squarefree positive integer $n$, $2^{{\omega(n)}}=\tau(n)=2^{{\Omega(n)}}$.

## Mathematics Subject Classification

11A25*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Unproven?

Why is this theorem classified as unproven? The proof provided convinces me well enough, I don't know about the rest of you.

## Re: Unproven?

In cases like this one, just fill a meta correction requesting that it be marked as proven.

## Re: Unproven?

The reason is that the "contains own proof" box was not checked.

This happens all the time, either because someone forgets to

change the box or some glich in the system and is no big deal.

## Re: Unproven?

Mravinci,

Sometimes when a theorem gets edited, the "contains own proof" box gets unchecked, a bug that yark has pointed out before. I went back and fixed all of the ones to which the user mps filed a correction.

## Re: Unproven?

Wkbj79 writes:

> Sometimes when a theorem gets edited, the

> "contains own proof" box gets unchecked,

> a bug that yark has pointed out before.

I don't think I was the first to point this out. But I did point out that (as far as I can tell) it only happens if you use the preview button.

## Re: Unproven?

Oh yeah, that explains it. Sometimes when I use the preview button twice, the TeX images look blown up and pixellated, but it doesn't affect the look of the object after saving. Now I know to watch out for this other bug that does affect the saved object. Thanks you yark. Mrav

## Avoiding ambiguity

The proof starts: "Note that the three functions involved in the inequality are multiplicative." I would suggest replacing "functions" with "expressions" - on first reading, my automatic assumption was that the "functions" were \omega(n), \tau(n) and \Omega(n).

Hugo van der Sanden