elementary number theory - 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.

Answer

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.