2
$\begingroup$

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?

1 Answers 1

4

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

  • 0
    $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? ;)2011-11-07