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

Question

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 1

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.

Answer 2

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