# 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$

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$.

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.

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$.

• I see what you are doing by dropping the floor function but I also looking at the case of $\min (\lfloor{N/4}\rfloor, \lfloor{\frac{N + 4}{p}}\rfloor) = \lfloor{N/4}\rfloor$ for $p = 5$ and $N \in {6, 7, 11}$ and $\lfloor{\frac{N + 4}{p}}\rfloor$ otherwise. Using the new approach gives $p < 4 + 16/N$. For $p = 5$ the cases where this is valid are for $N \in {5, 6, 7, 8}$. So we added the cases $N \in {5, 8}$ and missed the case $N = 11$. Am I wrong in assuming that this methods generates all the solutions or is it expected to show that solutions re either possible or not? Dec 21, 2016 at 2:16
• Well this was not part of the question, I suggest to make a new question with generic $k$ in place of $4$ and make clear you want to know for fixed $k$ for which $N$ and $p$ this works. Approach in this answer will give you generally sufficient but not necessary condition (it tells you that $p<k+k^2/N$, so for $N>k^2$ you already know $p<k+1$), so it allows you to prove this works for $N$ from certain point, but for below points you need to find another argument.
– Sil
Dec 21, 2016 at 10:54
• Notice that for higher $k$ values it is getting more problematic, for $k=6$ my argument allows you to show that safe $N$ to choose is $N>36$, and if you try values below, for example $N=29$ and $p=7$ it indeed will fail. For $k=10$ my argument gives safe $N>100$, and indeed, if you try below for example $N=89$,$p=11$ statement does not hold again, so below that $k^2$ its problematic... I guess you should first figure out what you are trying to achieve with this, and also provide some context, how does this problem arise and what you are trying to solve by this, it would help in this case.
– Sil
Dec 21, 2016 at 10:55
• The general problem is to find the cases of $a$ and $N$ where $\lfloor{N/a}\rfloor < \floor{(N + a)/p}\rfloor$ where $N \ge p$ and $a \in {1, 2, 3, \cdots, p - 1}$/ I know that $a = 1, 2, 3$ there are no solutions and the fist case occurs for $a = 4$ where $p = 5$ and $N = 6, 7, 11$. This is a counting problem for quadratics that factor. I am working on the prime $p$ cases. Yes in general the solution does not require that $p$ to be prime. Dec 21, 2016 at 20:10
• The general problem is to find the cases of $a$ and $N$ where $\lfloor{N/a}\rfloor < \lfloor{(N + a)/p}\rfloor$ where $N \ge p$ and $a \in {1, 2, 3, \cdots, p - 1}$/ I know that $a = 1, 2, 3$ there are no solutions and the fist case occurs for $a = 4$ where $p = 5$ and $N = 6, 7, 11$. This is a counting problem for quadratics that factor. I am working on the prime $p$ cases. Yes in general the solution does not require that $p$ to be prime. Dec 21, 2016 at 20:11