# Prove that $N - \lfloor{N/p}\rfloor = \lfloor{\frac{p-1}{p}\left({N + 1}\right)}\rfloor$ for positive $N$ and prime $p$

I am counting the number of positive integers less than or equal to some positive integer $$N$$ and not divisible by some prime $$p$$. This gets generalized for $$k$$ primes where I use the principle of inclusion-exclusion for this result. The simple result for a single prime is $$N - \lfloor{\frac{N}{p}}\rfloor$$. However, I have noticed by experiment that this is also equal to $$\lfloor{\frac{p-1}{p} \left({N + 1}\right)}\rfloor$$. I am looking for a proof of this relation if true.

Consider that $$N$$ may be expressed as $$N = ap + b$$ for an integer $$a$$ and integer $$0 \le b \le p - 1$$. Using this, the left side of your equation becomes

$$N - \lfloor N/p \rfloor = ap + b - a \tag{1}\label{eq1}$$

Consider the numerator of the right side of your equation, i.e.,

$$\left(p - 1\right)\left(N + 1\right) = \left(p - 1\right)\left(ap + b + 1\right) = ap^2 + \left(b + 1 - a\right)p - \left(b + 1\right) \tag{2}\label{eq2}$$

Since $$0 \leq b \leq p - 1$$, then $$1 \leq b + 1 \leq p$$. As such, for any integer $$M$$, including $$M = 0$$, we have that

$$\lfloor \frac{Mp - \left(b + 1\right)}{p} \rfloor = M - 1 \tag{3}\label{eq3}$$

Using $$\eqref{eq2}$$ and $$\eqref{eq3}$$ in the right side of your equation gives

$$\lfloor \frac{\left(p - 1\right)\left(N + 1\right)}{p} \rfloor = ap + \left(b + 1 - a\right) + \lfloor \frac{-\left(b + 1\right)}{p} \rfloor = ap + b - a \tag{4}\label{eq4}$$

As such, the LHS (from \eqref{eq1}) is always equal to the RHS (from \eqref{eq4} above), so your equation always holds. Note, this is true not only for primes $$p$$, but for all positive integers $$p$$, as I didn't use any particular properties of primes anywhere in the proof above.

let $$f(N) = N - \lfloor \frac{N}{p} \rfloor$$

then $$f(N+1) - f(N) = 1 - \bigg(\lfloor \frac{N+1}{p} \rfloor - \lfloor \frac{N}{p} \rfloor \bigg)$$

thus when $$N$$ is incremented by 1, $$f(N)$$ is also incremented by 1 except when $$N \equiv_p -1$$. in this case $$f(N+1) = f(N)$$

if now we let $$g(N) = \lfloor{\frac{p-1}{p} \left({N + 1}\right)}\rfloor$$ a little rearrangement gives $$g(N) = \lfloor N+1 - \frac{N+1}p \rfloor= N+1 + \lfloor -\frac{N+1}p \rfloor$$ and $$g(N+1) - g(N) = 1 + \bigg(\lfloor -\frac{N+2}{p} \rfloor - \lfloor -\frac{N+1}{p} \rfloor \bigg)$$

since $$N$$ is positive we again find that when $$N$$ increases by 1 the increment of $$g$$ is 1 except when $$N \equiv_p -1$$.

since $$f(1)=g(1)=1$$ the result is demonstrated