MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 $0 < a < 1$ be fixed, and integer $n$ tends to infinity. It is not hard to show that the number of integers $k$ coprime to $n$ such that $1\leq k\leq an$ asymtotically equals $(a+o(1))\varphi(n)$. The question is: what are the best known estimates for the remainder and where are they written?

Many thanks!

share|cite|improve this question
up vote 7 down vote accepted

Vinogradov, I. M. An introduction to the theory of numbers, Ch. 2, problem N 19. It gives error term $O(\tau(n))$. But direct application of inclusion-exclusion principle gives $O(2^{\omega(n)})$ (where $\tau$ is the number of divisors, and $\omega$ is the number of prime divisors

share|cite|improve this answer
Alexey, is that really the way you spell your surname? – Robin Chapman Apr 29 '10 at 18:09
It's my fault: I asked Alexey (Ustinov) to answer so he didn't pay enough attention to filling in his data accurately. – Wadim Zudilin Apr 29 '10 at 21:37
Now my name is correct. – Alexey Ustinov May 4 '10 at 22:49

In a similar question Bound the error in estimating a relative totient function , Alan Haynes notes in an answer that Vijayraghavan in 1951 had published a result showing many $n$ for which (for certain a) the error approaches $2^{\omega(n) - 1}$. Further, Lehmer in 1955 showed that for certain values of a (namely q/k where k divides p-1 and p divides n) that the error was 0.

share|cite|improve this answer

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.