10
$\begingroup$

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!

$\endgroup$
9
$\begingroup$

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. Standart solution with Mobius function also gives $O(2^{\omega(n)})$ if one take into account that $\mu(p^2)=0.$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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