Prove that every positive integer less than or equal to the square root of a is a near factor of a

Question

In many computer languages, the division operation ignores remainders. Let's denote this by the operation $//$, so for instance $13//3 = 4$. If for some $b$, $a//b = c$ then we say that $c$ is a near factor of $a$. Thus, the near factors of $13$ are $1,2,3,4$ and $6$. Let $a$ be a positive integer. Prove that every positive integer less than or equal to $\sqrt{a}$ is a near factor of $a$.

Answer 1

Let $k$ be a positive integer with $k\le\sqrt{a}$.

Use the division algorithm to write $a=kq+r$ where $0\le r <k$.

Note that $q\ge k$ (this follows since $k\cdot k\le a$, so the quotient in dividing $a$ by $k$ is at least $k$). And so $r<q$.

From $a=kq+r$, we obtain $\frac{a}{q}=k+\frac{r}{q}$, but $\frac{r}{q}<1$. So we conclude that $a//q=k$, and thus $k$ is a near factor of $a$.

Answer 2

Disclaimer: This is not quite a complete solution. It proves that every $\boldsymbol{k}$ with $\boldsymbol{k+1 \le \sqrt{a}}$ is a near factor.

Let $m$ be the smallest integer for which $m(m+1) > a$. Consider the (not necessarily strictly) decreasing sequence $$ a // m, a // (m+1), a // (m+2), \ldots, a // (a-1), a // a = 1. \tag{1} $$ Note that for $m \le k \le a-1$, \begin{align*} 0 \le a // k - a // (k+1) &< \left(\frac{a}{k}\right) - \left(\frac{a}{k+1} - 1\right) \\ &= 1 + a \left(\frac{1}{k} - \frac{1}{k+1}\right) \\ &= 1 + \frac{a}{k(k+1)} \\ &\le 1 + \frac{a}{m(m+1)} \\ &< 1 + \frac{a}{a} \\ &= 2. \end{align*} But since $a // k - a // (k+1)$ is an integer, and it is $\ge 0$ and $< 2$, we have $a // k - a // (k+1) \in \{0,1\}$. Therefore the sequence in (1) goes down $1$ or $0$ at a time, and as it ends in $1$ it hits every integer between $1$ and $a // m$.

Just how large is $a // m$? Well, Since $m$ is the smallest integer for which $m(m+1) > a$, $(m-1)m \le a$. So $(m-1)^2 < a$, so $m < \sqrt{a} + 1$. Then $$ a // m > \frac{a}{m} - 1 > \frac{a}{\sqrt{a}+1} - 1 = \frac{a + \sqrt{a}}{\sqrt{a}+1} - \frac{\sqrt{a}}{\sqrt{a}+1} - 1 > \sqrt{a} - 2 > \lfloor \sqrt{a} \rfloor - 2 $$ which implies, since $a // m$ is an integer, that $$ a // m \ge \lfloor \sqrt{a} \rfloor - 1. $$ Therefore, every integer $1, 2, 3, \ldots, \lfloor \sqrt{a} \rfloor - 1$ is found in the sequence (1). I.e., every $k$ with $k + 1 \le \sqrt{a}$.