# Can the Inclusion-Exclusion Principle be used to establish a lower bound for the number of $i$ where $an < i \le an+n$ and $\gcd(i,w)=1$

Let $\Phi(x,w) =$ the number integers $i$ where $i \le x$ and $\gcd(i,w)=1$

Let $a, n > 1, w$ be integers.

Does it follow that $\Phi(an+n,w) - \Phi(an,w) \ge \sum\limits_{d|w}\lfloor\frac{\mu(d)n}{d}\rfloor$

Here 's my reasoning:

$$\Phi(an+n,w) - \Phi(an,w) = \sum\limits_{d | w}\mu(d)\left\lfloor\frac{an+n}{d}\right\rfloor - \sum\limits_{d | w}\mu(d)\left\lfloor\frac{an}{d}\right\rfloor$$

$$= \sum\limits_{d | w}\mu(d)\left(\left\lfloor\frac{an+n}{d}\right\rfloor - \left\lfloor\frac{an}{d}\right\rfloor\right)$$

$$= \sum\limits_{d | w \text{ and }\mu(d)=1}\left(\left\lfloor\frac{an+n}{d}\right\rfloor - \left\lfloor\frac{an}{d}\right\rfloor\right) + \sum\limits_{d | w \text{ and }\mu(d)=-1}\left(\left\lfloor\frac{an}{d}\right\rfloor - \left\lfloor\frac{an+n}{d}\right\rfloor\right) \ge$$

$$\sum\limits_{d | w \text{ and }\mu(d)=1}\left(\left\lfloor\frac{n}{d}\right\rfloor\right) + \sum\limits_{d | w \text{ and }\mu(d)=-1}\left(\left\lfloor\frac{-n}{d}\right\rfloor\right) =\sum\limits_{d | w }\left(\left\lfloor\frac{\mu(d)n}{d}\right\rfloor\right)$$

Is this correct?

Edit 1: Thanks to Gerhard, I've fixed the mistake. I believe that it is now correct. I had overlooked that for $0 < a < 1$, $-\lfloor{a}\rfloor \ne \lfloor{-a}\rfloor$

• It shouldn't be correct. Take n=5 and a=2. We can pick w so that more copies to w exist below n than between an and an+n. Letting w=7*11*13, I get for your relation 2 greater than 5. Gerhard "Imagine What It Tells You" Paseman, 2017.06.09. – Gerhard Paseman Jun 9 '17 at 17:18
• Given this counterexample, you should be able to see what step failed (hint: it's the inequality step) and why. Gerhard "Always Do Some Easy Tests" Paseman, 2017.06.09. – Gerhard Paseman Jun 9 '17 at 17:29
• @Gerhard, I believe the inequality was correct. It was my last step. I fixed it and I believe it is now good (though, I am not clear what it means yet). – Larry Freeman Jun 10 '17 at 3:12
• You do not have floor(an/d) - floor((an+n)/d) greater than -floor(n/d) always. Gerhard "Try Some More Numerical Examples" Paseman, 2017.06.09. – Gerhard Paseman Jun 10 '17 at 3:25
• While your last equality is correct, you get mu on the inside of the floor, which is different from your conjectured lower bound. Gerhard "They Look Similar, But Aren't" Paseman, 2017.06.09. – Gerhard Paseman Jun 10 '17 at 3:45