Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
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? – Kou Dec 18 '11 at 23:32
@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. – Greg Martin Dec 19 '11 at 6:10
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. – Kou Dec 19 '11 at 22:19
There are many sources that explain the connection between the sieve and the Möbius function - , 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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