13
$\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$
0

2 Answers 2

11
$\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$
3
  • $\begingroup$ Alexey, is that really the way you spell your surname? $\endgroup$ Apr 29, 2010 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$ Apr 29, 2010 at 21:37
  • $\begingroup$ Now my name is correct. $\endgroup$ May 4, 2010 at 22:49
4
$\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 and acknowledge you have read our privacy policy.

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