# Find the full solution to $\left\lfloor{\frac{N}{a}}\right\rfloor = \left\lfloor{\frac{N}{p}}\right\rfloor - a$ where $N \geq p^2, p > 1$

I am looking for the full solution for $a$ to the floor function equation where $\left\lfloor{\frac{N}{a}}\right\rfloor = \left\lfloor{\frac{N}{p}}\right\rfloor - a$. I have tried the quadratic solution when dropping the floor functions and this does identify most of the solutions for $a$. However there are a few more solutions that are not identified by this method. The conditions are $p > 1$ (actually $p$ is prime), $N \ge {p}^{2}$, $a > 0$, and $N, a, p \in \mathbb{Q}$, and $1 \le a \le N$.

Also I am using Mathematica and it does handle equations with floor functions when using Solve or Reduce. For example Mathematica does not solve $\left\lfloor{a}\right\rfloor = 0$ where the solution is $0 \le a < 1$.

Clearly, $a$ must be a positive integer. Let $q=\lfloor \frac Np\rfloor$. Note that $q\ge p$. We have $\frac Na\le \lfloor \frac Na\rfloor<\frac Na+1$, hence necessarily $$N\le q a -a^2<N+a$$ so that $a$ must be between (inclusively) the roots $\frac {q\pm\sqrt{q^2-4N}}2$ of $x^2-q a+N$, and strictly not between the roots $\frac{q-1\pm\sqrt{(q-1)^2-4N}}2$ of $x^2-(q-1)x+N$. Thus $$\left\lceil\tfrac {q-\sqrt{q^2-4N}}2\right\rceil\le a\le \left\lceil\tfrac{q-1-\sqrt{(q-1)^2-4N}}2\right\rceil-1\text{ or } \left\lfloor\tfrac{q-1+\sqrt{(q-1)^2-4N}}2\right\rfloor +1\le a\le \left\lfloor\tfrac {q+\sqrt{q^2-4N}}2\right\rfloor$$
Note that it is possible that $q^2<4N$, in which case the first quadratic has no real roots - and the original problem has no solutions. On the other hand, if $(q-1)^2<4N$ that's fine and there simply is no restriction imposed by the second quadratic, i.e., $$\left\lceil\tfrac {q-\sqrt{q^2-4N}}2\right\rceil\le a\le \left\lfloor\tfrac {q+\sqrt{q^2-4N}}2\right\rfloor\qquad\text{ if }(q-1)^2<4N.$$
• Using the case where $p = 11$ and $N = 500$ the last formula gives $20 \le a \le 25$, while the full solution is $18 \le a \le 28$. I also duplicated the above derivation using the two end points of $\left\lfloor{N/a}\right\rfloor$. So why are we missing these other solutions? – Lorenz H Menke Aug 14 '16 at 23:19
• I would fix the third sentence to read: We have $\left\lfloor{N/a}\right\rfloor = N/a - \alpha$ where $0 \le \alpha < 1$, hence necessarily ... – Lorenz H Menke Aug 16 '16 at 1:27
Clearly, $a$ must be a positive integer. Let $q = \left\lfloor \frac{N}{p}\right\rfloor$. Note that $q \ge p$. We have $\frac{N}{a} - 1 < \left\lfloor \frac{N}{a}\right\rfloor \le \frac{N}{a}$, hence necessarily $$N - a < q a - a^2 \le N$$ so that $a$ must be strictly not between the roots $\frac {q + 1 \pm \sqrt{\left({q + 1}\right)^{2} - 4\, N}}{2}$ of $a^2 - \left({q + 1}\right) a + N$, and be between (inclusively) the roots $\frac{q \pm \sqrt{{q}^{2} - 4\, N}}{2}$ of $a^2 - q\, a + N$. Thus \begin{equation*} 0 < a \le \left\lfloor{\frac{1}{2} \left({q - \sqrt{{q}^{2} - 4\, N}}\right)}\right\rfloor \quad \text{or} \quad a \ge \left\lceil{\frac{1}{2} \left({q + \sqrt{{q}^{2} - 4\, N}}\right)}\right\rceil \quad \text{if} \quad N < \frac{{q}^{2}}{4} \end{equation*} and \begin{equation*} a > 0 \quad \text{if} \quad N \ge \frac{{q}^{2}}{4}. \end{equation*} On the other hand, if $N < \left({q + 1}\right)^{2}/4$ that's fine and there simply is no restriction imposed, i.e., \begin{equation*} \left\lceil{\frac{1}{2} \left({q + 1 - \sqrt{\left({q + 1}\right)^{2} - 4\, N}}\right)}\right\rceil \le a \le \left\lfloor{\frac{1}{2} \left({q + 1 + \sqrt{\left({q + 1}\right)^{2} - 4\, N}}\right)}\right\rfloor \quad \text{if} \quad N < \frac{\left({q + 1}\right)^{2}}{4}. \end{equation*} For example, when $p = 11$ and $N = 500$ then $500 < 529$ and $18 \le a \le 28$.