Let $\omega(n)$ be the number of distinct primes dividing $n$.
- 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))$.
- 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).