3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.