Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.