Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 3 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|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

 
discard

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.