Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

up vote 6 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|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
add comment

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.