# Number of integers coprime to l

A long time ago I've seen a paper considering, given $\ell$ fixed, estimates for

$$\sum_{n \leq x, (n, \ell) = 1} 1$$

Of course, this is easy to estimate with a trivial error term of $O(\varphi(l))$. However in the paper I am looking for the authors attempted obtaining better bounds, using some Fourier analysis (in particular the Fourier series for the fractional part of x). I think, bounds in the sum

$$\sum_{n \leq x} (n, \ell)$$ are essentially an equivalent variation of the problem, so references on this problem are welcome aswell.

The reason why I am interested in this problem is ... pure curiosity. I am curious to see how the Fourier methods meshed in, and what kind of bounds they gave, even though of course we cannot really expect anything too fantastic in this problem.

-
I vaguely remember that the journal in question is likely to be the Canadian Math. Bulletin, or the Canadian Math. Journal, but I could be completely wrong on this hunch (so far my attempts at googling with "canadian" have failed). – kolik May 30 '12 at 8:56

It is easy to explain "how the Fourier analysis meshed in". Namely, using the standard notation for the Möbius function, the Euler's totient function, and the integer / fractional part functions, your sum can be written as $$\sum_{n\le x} \sum_{d\mid(n,l)} \mu(d) = \sum_{d\mid l} \mu(d) \lfloor x/d \rfloor = x \sum_{d\mid l} \frac{\mu(d)}d + R = \frac{\phi(l)}lx + R,$$ where $$R = \sum_{d\mid l} \mu(d) \{x/d\}.$$ As Fedor Petrov observed, this already suffices to improve the remainder term from $\phi(l)$ to $\tau(l)$ and indeed, to the number of square-free divisors of $l$, which is $2^{\omega(l)}$. To get better estimates, one can try to plug in the Fourier expansion for $\{x/d\}$ and estimate the resulting sums.

As to the paper you mention, I think I was able to spot it out: is it "Extremal values of $\Delta(x,N)=\sum_{n<xN,(n,N)=1} 1-x\phi(N)$" by P. Codeca and M. Nair, published in Canad. Math. Bull. 41 (3) (1998), pp. 335–347? Another paper by the same authors on the same subject: "Links between $\Delta(x,N)=\sum_{n<xN,(n,N)=1} 1-x\phi(N)$ and character sums", Boll. Unione Mat. Ital. Sez. B Artic. Ric. Mat. 6 (2) (2003), pp. 509–516. I could find one more paper on this problem published in a Canadian journal: "The distribution of totatives" by D.H. Lehmer, Canad. J. Math. 7 (1955), pp. 347–357.

-
It already gives much better bound then $O(\varphi(l))$, namely, $O(\tau(l))$. – Fedor Petrov May 30 '12 at 10:39
Well, I know how it meshed in. I want to see the real work :-) – kolik May 30 '12 at 11:19
Thank you ! It is amazing that you've found the reference :-) – kolik Jun 2 '12 at 3:21
I was looking for the paper by Codeca and Nair in the Math. Bulletin – kolik Jun 2 '12 at 3:22

As written above by Seva, one is led with exponential sums of the form $$\sum_{d|\ell} \mu(d) e^{\frac{2 i \pi y}{d}}$$ where $y = hx$ is an integer multiple of $x$. If one wants to reduce the trivial error term $O( \tau(\ell))$ to $O(\varepsilon \tau(\ell))$, one must consider the range $h \ll \frac {1}{\varepsilon}$ (at least). But I doubt that something really useful can be said about this particular sum, due to presence of the arithmetic factor $1_{d| \ell}$ (let alone the Möbius function).

If the condition $d|\ell$ is dropped (the sum is over a whole interval), then the best known results (to my knowledge) on this kind of sums are contained in this paper of Y.-F.S. Pétermann.

Note also that sieve methods give nontrivial bounds on the quantity $\sum_{n \leq x, (n, \ell) = 1} 1$ (without Fourier analysis).

-