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.
 A: 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.
A: 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
