# A problem about $\varphi(n)$

Let $\omega$ be the number of distinct primes dividing n, then $$\varphi(n)\geq n\prod_{k=2}^{\omega(n)+1}\left(1-\frac{1}{k}\right)=\frac{n}{\omega(n)+1}$$ Also $2^{\omega(n)}\leq \tau(n) \leq n$, and conclude that $$\varphi(n)\geq \frac{cn}{\log n} ,n\geq2$$ for a suitable constant $c>0.$

$\tau(n)$ denotes the number of positive divisors of $n$.

Could some give me a proof?

-

The formula for $\phi(n)$ yields:

$$\phi(n)= n \prod_{p |n} \frac{p-1}{p}$$

Now list the primes dividing n increasing $p_1,...,p_{\omega}$ and use $p_k \geq k+1$.

Then $$n \prod_{p |n} \frac{p-1}{p} \geq n \prod_{k=1}^\omega (1-\frac{1}{k+1})$$

and relabel the last product.

The inequality $2^{\omega(n)}\leq \tau(n)$ follows from the definition of $\tau(n)$ and then taking the logarithms of the inequality $2^\omega \leq n$, yields what you need

-
Could you explain that how $2^{\omega(n)}\leq \tau(n)$ follows from the definition of $\tau(n)$? – Kou Nov 6 '11 at 21:54
$n= p_1^{a_1}...p_\omega^{a_\omega} \Rightarrow \tau(n)=(a_1+1)...(a_\omega+1)$... What is the smallest value each bracket can take? ;) – N. S. Nov 7 '11 at 0:50