7
$\begingroup$

Is it trivial that $\varphi(N)>\pi(N)$ for sufficiently big integers $N$, where $\varphi$ is Euler's totient function and $\pi$ is the prime-counting function?

The only exceptions less than $1.000.000$ are $1,2,3,4,6,8,10,12,14,18,20,24,30,42,60,90$.

Why should the number of to $N$ relative prime numbers less than $N$ be greater than the number of primes less than $N$?

Can someone please hint on this?

$\endgroup$
  • $\begingroup$ This shouldn't be too hard to prove. If a number contains too many diffrerent primes, it's big enough to contain even more primes coprime and you should be able to show you can form enough composite coprimes to compensate for the prime factors of the number. But I'm too lazy to write a precise argument as an answer. $\endgroup$ – user2345215 Nov 13 '14 at 11:29
  • $\begingroup$ We have $\varphi(n) > \frac{n}{e^\gamma \ln(\ln(n)) + \frac{3}{\ln(\ln(n))}}$ and $\pi(n) \sim \frac{n}{\ln(n)}$ $\endgroup$ – gammatester Nov 13 '14 at 11:31
  • $\begingroup$ Compare also with the answers of this question. $\endgroup$ – Dietrich Burde May 27 '18 at 16:18
3
$\begingroup$

Since: $$\phi(N)=N\prod_{p\mid N}\left(1-\frac{1}{p}\right) $$ we have: $$ \frac{N}{\phi(N)}=\exp\left(\sum_{p\mid N}-\log\left(1-\frac{1}{p}\right)\right)\leq K\exp\sum_{p\mid N}\frac{1}{p}$$ while $$\pi(N)\leq \log 4\cdot\frac{N}{\log N}$$ hence we just need to show that for any $N$ big enough: $$\exp\sum_{p\mid N}\frac{1}{p}\leq\frac{\log 4}{K}\log N$$ or: $$ \sum_{p\mid N}\frac{1}{p}\leq C +\log\log N $$ that is trivial since the LHS behaves like $\log\log\log N$.

$\endgroup$
3
$\begingroup$

Hint:-

Use $\varphi(n) >\dfrac{n}{e^\gamma \ln (\ln n)+\dfrac{3}{\ln (\ln n)}}$ and $\dfrac{n}{\ln n -(1+\epsilon)}>\pi(n)$ for all sufficiently large $n$ and for all $\epsilon>0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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