$2^{\omega(n)} \le \tau(n) \le 2^{\Omega(n)}$2omeganLeTaunLe2Omegan2006-07-29 12:57:352008-01-01 12:12:20Theorem\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfrag}
\usepackage{graphicx}
\usepackage{amsthm}
\usepackage{xypic}
\newtheorem*{thm*}{Theorem}
\newtheorem*{cor*}{Corollary}Throughout this entry, $\omega$, $\tau$, and $\Omega$ denote the number of distinct prime factors function, the divisor function, and the \PMlinkname{number of (nondistinct) prime factors function}{NumberOfNondistinctPrimeFactorsFunction}, respectively.
\begin{thm*}
For any positive integer $n$, $2^{\omega(n)} \le \tau(n) \le 2^{\Omega(n)}$.
\end{thm*}
\begin{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{center}
$\begin{array}{rl}
\displaystyle 2^{\omega(p^k)} & =2 \\
\\
\tau(p^k) & =k+1 \\
\\
\displaystyle 2^{\Omega(p^k)} & = 2^k \end{array}$
\end{center}
Hence, $2^{\omega(p^k)} \le \tau(p^k) \le 2^{\Omega(p^k)}$. It follows that $2^{\omega(n)} \le \tau(n) \le 2^{\Omega(n)}$.
\end{proof}
This theorem has an obvious corollary.
\begin{cor*}
For any squarefree positive integer $n$, $2^{\omega(n)}=\tau(n)=2^{\Omega(n)}$.
\end{cor*}