Help verify the proof that $\min \left({\lfloor{N/2}\rfloor, \lfloor{(N + 2)/p}\rfloor}\right) = \lfloor{(N + 2)/p}\rfloor$ for $N \ge p$

Question

Well, I think that I have this correct, however my proof seams cumbersome, so can someone check these results or suggest a simplified proof.

Prove that ($N \ge p$)

\begin{equation*} \min \left({\left\lfloor{\frac{N}{2}}\right\rfloor, \left\lfloor{\frac{N + 2}{p}}\right\rfloor}\right) = \left\lfloor{\frac{N + 2}{p}}\right\rfloor \end{equation*}

for prime $p \ge 3$ with $N \ge p$ and $N \in \mathbb{Z}^{+}$. To see this, let $N = k\, p + m$ where $k \in \mathbb{Z}^{+}$ and $m \in \left\{{0}\right.$, $1$, $\cdots$, $\left.{p - 1}\right\}$ by the Quotient Remainder Theorem, then show that this equation holds for all values of $k$. Starting with

\begin{equation*} \left\lfloor{\frac{N + 2}{p}}\right\rfloor = \left\lfloor{\frac{k\, p + m + 2}{p}}\right\rfloor = k + {\delta}_{2} \end{equation*}

where

\begin{equation*} {\delta}_{2} = \left\lfloor{\frac{m + 2}{p}}\right\rfloor = \begin{cases} 0, & \text{for } m \le p - 3, \\ 1, & \text{for } m \in \left\{{p - 2, p - 1}\right\}. \end{cases} \end{equation*}

Also

\begin{equation*} \left\lfloor{\frac{N}{2}}\right\rfloor = \left\lfloor{\frac{k\, p + m}{2}}\right\rfloor = \left\lfloor{\frac{k\, p}{2} + \frac{m}{2}}\right\rfloor. \end{equation*}

Therefore

\begin{equation*} k + {\delta}_{2} \le \left\lfloor{\frac{k\, p}{2} + \frac{m}{2}}\right\rfloor. \end{equation*}

If $k$ is even then we have

\begin{equation*} k + {\delta}_{2} \le \frac{k\, p}{2} + \left\lfloor{\frac{m}{2}}\right\rfloor. \end{equation*}

Solving for $k$ gives

\begin{equation*} k \ge \frac{2 \left({{\delta}_{2} - \left\lfloor{m/2}\right\rfloor}\right)}{p - 2}. \end{equation*}

If ${\delta}_{2} = 0$ or ${\delta}_{2} = 1$ then $k \ge 2$ since $k$ is even and ${\delta}_{2} - \left\lfloor{m/2}\right\rfloor \le 1$. Now if $k$ is odd then we have three cases to consider starting with

\begin{equation*} k + {\delta}_{2} \le \frac{\left({k + 1}\right) p}{2} + \left\lfloor{\frac{m - p}{2}}\right\rfloor. \end{equation*}

Solving for $k$ gives

\begin{equation*} k \ge \frac{2 \left({{\delta}_{2} - p/2 - \left\lfloor{\left({m - p}\right)/2}\right\rfloor}\right)}{p - 2}. \end{equation*}

With $m = 0$, then ${\delta}_{2} = 0$ and

\begin{equation*} k \ge \frac{2}{p - 2} \left({- \frac{p}{2} + \left\lceil{\frac{p}{2}}\right\rceil}\right) = \frac{1}{p - 2} \ge 1 \end{equation*}

since $\left\lceil{p/2}\right\rceil = \left({p - 1}\right)/2 + \left\lceil{1/2}\right\rceil = \left({p + 1}\right)/2$ with $p \ge 3$. For the last two cases $m = p - 2$ or $m = p - 1$, $\delta = 1$, then

\begin{equation*} k \ge \frac{4 - p}{p - 2} \ge 1 \end{equation*}

for $p \ge 3$. Thus the primary equation holds for $p \ge 3$.

Answer 1

You can prove this a bit easier using for example using proof by contradiction:

Let's assume $\left\lfloor{\frac{N}{2}}\right\rfloor < \left\lfloor{\frac{N + 2}{p}}\right\rfloor$. This implies $\frac{N}{2} < \frac{N+2}{p}$ or after simplification $p < 2+\frac{4}{N}$.

Now cases where $N\leq 4$ can be easily checked by hand, so let's assume $N>4$, but then $p<3$ and we have a contradiction with $p\geq 3$.

Notice that the proof did not use the assumption that $p$ is a prime, so it whole applies for any natural number $p$.

Answer 2

Show that

\begin{equation*} \left\lfloor{\frac{N}{2}}\right\rfloor < \left\lfloor{\frac{N + 2}{p}}\right\rfloor \end{equation*}

is not valid. Let $N = k\, p + m$ where $k \in \mathbb{Z}^{+}$ and $m \in \left\{{0}\right.$, $1$, $\cdots$, $\left.{p - 1}\right\}$ by the Quotient Remainder Theorem. Then show this holds for all values of $k$ and $m$. Starting with the left-hand side

\begin{equation*} \left\lfloor{\frac{N}{2}}\right\rfloor = \left\lfloor{\frac{p\, k + m}{2}}\right\rfloor = \left\lfloor{\frac{2\, k + \left({p - 2}\right) k + m}{2}}\right\rfloor = k + \left\lfloor{\frac{\left({p - 2}\right) k + m}{2}}\right\rfloor \end{equation*}

then the right-hand side

\begin{equation*} \left\lfloor{\frac{N + 2}{p}}\right\rfloor = \left\lfloor{\frac{p\, k + m + 2}{p}}\right\rfloor = k + \left\lfloor{\frac{m + 2}{p}}\right\rfloor \end{equation*}

then

\begin{equation*} \left\lfloor{\frac{\left({p - 2}\right) k + m}{2}}\right\rfloor < \left\lfloor{\frac{m + 2}{p}}\right\rfloor = {\delta}_{2} = \begin{cases} 0, & \text{for } m \le p - a - 1, \\ 1, & \text{for } m \in \left\{{p - a, \cdots, p - 2, p - 1}\right\}. \end{cases} \end{equation*}

Then

\begin{equation*} \min \left({\left\lfloor{\frac{N}{2}}\right\rfloor, \left\lfloor{\frac{N + 2}{p}}\right\rfloor}\right) = \left\lfloor{\frac{N + 2}{p}}\right\rfloor \end{equation*}

for $p \ge 3$. To see this, establish a contradiction. Then

\begin{equation*} \left\lfloor{\frac{\left({p - 2}\right) k + m}{2}}\right\rfloor < {\delta}_{2}. \end{equation*}

Now with $m \in \left\{{0}\right.$, $1$, $\cdots$, $\left.{p - 3}\right\}$, then ${\delta}_{2} = 0$ and $\left({p - 2}\right) k + m \ge 1$ with $\left\lfloor{\left[{\left({p - 2}\right) k + m}\right]/2}\right\rfloor \ge 0$ which leads to $0 < 0$ which is a contradiction. Next $m = p - 2$ and ${\delta}_{2} = 1$ then

\begin{equation*} \left\lfloor{\frac{\left({p - 2}\right) \left({k + 1}\right)}{2}}\right\rfloor < 1 \end{equation*}

with $\left({p - 2}\right) \left({k + 1}\right) \ge 2$ leads to $1 < 1$ which is a contradiction. Next $m = p - 1$ and ${\delta}_{2} = 1$ then

\begin{equation*} \left\lfloor{\frac{\left({p - 2}\right) k + p - 1}{2}}\right\rfloor < 1 \end{equation*}

with $\left({p - 2}\right) k + p - 1 \ge 3$ leads to $1 < 1$ which is a contradiction. Therefore there are no cases.