# 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.

-
There is a typo in your post. –  Kerry Dec 9 '11 at 5:22
As written, this can't possibly be right. Surely the $\phi(x)$ is meant to be $\phi(n)$. But also $\phi(x,n)\to x\phi(n)$ doesn't make sense. Maybe $\phi(x,n)$ is asymptotic to $x\phi(n)$? –  Gerry Myerson Dec 9 '11 at 8:16
@GerryMyerson Can you explain more about the second problem? –  Kou Dec 19 '11 at 22:17
I think I'll echo Greg's answer. It's really not hard to get from the 1st problem to the 2nd, if you know what that symbol means. –  Gerry Myerson Dec 20 '11 at 4:05

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