Sieving modulo non-prime residue classes Let $n$ be a positive integer, and consider the set $\{1, \dots, n\}$. If we remove from this set all the numbers $a$ which satisfy 
$$
a \equiv 0 \mod d  
$$
for at least one divisor $d$ of $n$ (where we only consider $d \neq 1$, of course), then it is well-known that the total number of remaining elements is given by the Euler totient function $\varphi(n)$. This is quite easy to show - note that it uses the fact that actually it is sufficient to consider those divisors $d$ which are primes, since then all composite divisors are incorporated automatically. 
Now here is my problem. Let $\gamma \in [0,1]$ be a fixed real number. For a real number $y$, let $[y]$ denote the integer which is closest to $y$. From the set $\{1, \dots, n\}$ I have to remove all the elements $a$ for which
$$
a \equiv [\gamma d] \mod d
$$
for at least one divisor $d$ of $n$ (where again we only consider $d \neq 1$). How many elements remain? In contrast to the case $\gamma=0$, now it obviously is not sufficient anymore to consider only prime divisors $d$. A trivial lower bound for the number of remaining elements is 
$$
n - \sum_{d | n, ~d \neq 1} \frac{n}{d} = n - \sum_{d | n, ~d \neq n} d,  
$$
since for every divisor $d$ we remove at most one residue class (which contains $n/d$ elements). 
Question: Is there any significantly better lower bound for the number of remaining elements? (Note that I do not want to assume anything whatsoever on $n$ or $\gamma$.)
 A: Let $D=\{ d>1\ :\ d\mid n \}$ be the set of nontrivial divisors of $n$. Then by inclusion-exclusion, the number of elements remaining after sieving based on $a\equiv 0\pmod{d}$ equals
$$\sum_{S\subseteq D} (-1)^{|S|}\frac{n}{\mathrm{lcm}(S)},$$
where $\mathrm{lcm}(S)$ is the least common multiple of the elements of set $S$ with $\mathrm{lcm}(\emptyset):=1$. Here $\frac{n}{\mathrm{lcm}(S)}$ is the number of solutions from $\{1,2,\dots,n\}$ to the system of congruences $\{ x\equiv 0\pmod{d}\ :\ d\in S\}$. One can easily see that this system is always soluble and equivalent to a single congruence $x\equiv 0\pmod{\mathrm{lcm}(S)}$. It is an exercise to show that the above sum equals $\varphi(n)$.
Similar formula holds when the sieving is done based on $a\equiv [\gamma d]\pmod{d}$. The number of remaining elements in this case equals
$$R := \sum_{S\subseteq D} (-1)^{|S|} N_S,$$
where $N_S$ is the number of solutions from $\{1,2,\dots,n\}$ to the system of congruences $\{ x\equiv [\gamma d]\pmod{d}\ :\ d\in S\}$. If such system is soluble, we again have $N_S=\frac{n}{\mathrm{lcm}(S)}$; otherwise $N_S=0$. So, to evaluate $R$ one needs to identify the subsets $S$ corresponding to soluble systems.
A system $\{ x\equiv [\gamma d]\pmod{d}\ :\ d\in S\}$ is soluble iff every pair of congruences in it is consistent, i.e., iff for every $d_1,d_2\in S$, $\gcd(d_1,d_2)\mid ([\gamma d_1] - [\gamma d_2])$.
Let us consider the graph $G$ on the vertices being elements of $D$, where vertices $d_1,d_2\in D$ are connected with an edge whenever $\gcd(d_1,d_2)\mid ([\gamma d_1] - [\gamma d_2])$. Then
$$R = \sum_{C} (-1)^{|C|}\frac{n}{\mathrm{lcm}(C)},$$
where the sum is taken over all cliques $C$ in $G$. 
Using the result about $\varphi(n)$, the last sum can further be reduced to just maximal cliques in $G$. Namely, let $\mathfrak{C}$ be the set of all maximal cliques in $G$. Then
$$R = \sum_{\emptyset\ne J\subseteq \mathfrak{C}} (-1)^{|J|-1} \frac{n}{\mathrm{lcm}(\cap_J)}\cdot\varphi(\mathrm{lcm}(\cap_J)),$$
where $\cap_J := \bigcap_{C\in J} C$.
