Let $\omega(n)$ be the number of distinct primes dividing $n$.

  1. For $x\in(0,1)$, let $\varphi(x,n)$ be the number of positive integers $m\leq xn$ which are prime to $n$. Show that $\varphi(x,n)=x\varphi(n)+O(\tau(n))$.
  2. Deduce that as $n\to\infty,\,\varphi(x,n) \sim x\varphi(n)$.

This is an exercise in the book Fundamentals of Number Theory (page 142). I was wondering how to connect it with $\omega(n)$. Could you explain it to me or give a proof on that? Thanks in advance.


In number theory questions concerning multiplicative functions, one of the best approaches ever is to remember that the Möbius function can detect the number 1 from among all positive integers:$$ \sum_{d\mid n} \mu(d) = \begin{cases} 1, &\text{if } n=1, \\ 0, &\text{if } n>1. \end{cases}$$ Therefore you can write$$ \phi(x,n) = \sum_{\substack{m\le xn \\ \gcd(m,n)=1}} 1 = \sum_{m\le xn} \sum_{d\mid \gcd(m,n)} \mu(d) = \sum_{d\mid n} \mu(d) \sum_{\substack{m\le xn \\ d\mid n}} 1.$$ EDITED TO INCLUDE MORE DETAILS: The number of integers up to $y$ that are multiples of $d$ is exactly $\lfloor y/d\rfloor$, which is $y/d + O(1)$. Therefore$$ \phi(x,n) = \sum_{d\mid n} \mu(d) \bigg( \frac{xn}d + O(1) \bigg) = xn \sum_{d\mid n} \frac{\mu(d)}d + O \bigg( \sum_{d\mid n} |\mu(d)| \bigg). $$ The first sum is exactly $\phi(n)/n$, and the second sum is exactly $2^{\omega(n)}$ (you can check both of these identites by verifying them on prime powers, since all these functions are multiplicative). It is also true that $2^{\omega(n)} \le \tau(n)$, which you can prove in several ways (combinatorially, or by evaluating on prime powers and using multiplicativity).

  • $\begingroup$ I am sorry that I still couldn't establish the estimate. Could give me a more complete proof? Besides, this is an exercise following the section "The sieve of Eratosthenes", could we prove it using the sieve? $\endgroup$ – Kou Dec 18 '11 at 23:32
  • 1
    $\begingroup$ @Kou: hopefully these details will help. Using the Möbius function is the most compact way to write inclusion-exclusion, so we really are sieving here. $\endgroup$ – Greg Martin Dec 19 '11 at 6:10
  • $\begingroup$ Thanks a lot. I still have two questions. 1. Have you figured out how to solve the second problem? 2. Could you explain more on" Using the Möbius function is the most compact way to write inclusion-exclusion"? I couldn't see the connections between them. $\endgroup$ – Kou Dec 19 '11 at 22:19
  • 1
    $\begingroup$ There are many sources that explain the connection between the sieve and the Möbius function - en.wikipedia.org/wiki/Legendre_sieve , for example. As for deducing your second question from the first: without trying to be mean, I must say that me answering that question would actually hinder your understanding, not help it. The $\sim$ symbol has a specific definition, and you need to use question #1 to show that that definition holds in question #2. $\endgroup$ – Greg Martin Dec 19 '11 at 23:50

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.