I'm new to asking questions on MathOverflow, so forgive me if this question is not the kind of thing to be asked here.


Let $q$ be a positive integer and let $N$ be an integer with $1 \leq N \leq q$. The estimate
$$
\sum\_{\substack{n= 1\\ (n,q)=1}}^N 1 = N \frac{\phi(q)}{q} + O(2^{\omega(q)})
$$
is a classical and straightforward application of Mobius inversion. The error term can be given explicitly by
$$
\sum\_{d\mid q} \mu(d) \left\{ \frac{N}{d}\right\}.
$$
If $q$ has few distinct prime factors, then the bound
$$
\Big|\sum\_{d\mid q} \mu(d) \left\{ \frac{N}{d}\right\}\Big| \leq 2^{\omega(q)}
$$
is sharp. For instance, if $q=p^k$ for some prime $p$, then $2^{\omega(q)} = O(1)$. Writing $N=Mp+r$, where $0\leq r < p$, gives
$$
\sum\_{d\mid q} \mu(d) \left\{ \frac{N}{d}\right\} = - \frac{r}{p},
$$
and this can genuinely be size $O(1)$.


On the other hand, I suspect that the bound $2^{\omega(q)}$ is quite wasteful when $q$ has many distinct prime factors. From some numerical calculations ($q \leq 10^6$), I suspect that
$$
\tag{1}
\Big|\sum\_{d\mid q} \mu(d) \left\{ \frac{N}{d}\right\}\Big| \ll \log\log q.
$$
If, if for instance, $q$ is the product of the first $k$ primes, then $q \ll (k\log k)^k$, and so $\log\log q \ll \log k$, whereas $2^{\omega(q)} = 2^k$. Thus my actual question:


**Does the estimate (1) hold in general?** It might be possible to establish this estimate using sieve methods (via upper and lower bounds on the original sum), but I am not familiar enough with sieve theory to pursue this avenue myself. I have not been able to find any results of this kind in the literature, so I would gladly welcome any ideas and/or references on this topic.



Improving the error term in a classic sieving problem
In fact there are moduli $q$ with arbitrarily many prime factors where the error term can be shown to be as large as $2^{\omega(q)-2}$. The following construction is due to D.H. Lehmer, [The distribution of totatives](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/distribution-of-totatives/A1B6054448396406512E4ECE51DC6ADD).


Let $q$ be the product of $k$ distinct prime numbers all of which are $ 3 \pmod 4$, and take $N=q/4$. Then $\frac 12 -\{ N/d\} = \pm 1/4$ depending on whether $q/d$ has an even or odd number of prime factors. Therefore
$$ 
\Big| \sum\_{d|q} \mu(d) \{N/d\} \Big| = \Big| \sum\_{d|q} \mu(d) (1/2- \{N/d\})\Big| = \frac 14 \sum\_{d|q} |\mu(d)| = \frac 14 2^{\omega(q)}. 
$$


One interesting application of this idea (which is how I know it) is Montgomery's work on the error term in the counting function of $\phi(n)$: see [Fluctuations in the mean ...](https://link.springer.com/article/10.1007/BF02837826).


