# On the asymptotic behavior of a function related to the number of distinct prime divisors

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).
• 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. – Greg Martin Dec 19 '11 at 23:50