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$.
-
$\begingroup$ Side note: How about marking those "a"s differently according to the symbolic meaning of each instance? (I would consider replacing it with $x$, to be honest). $\endgroup$– barak manosAug 16, 2015 at 7:39
-
$\begingroup$ $1 \leq x \leq \sqrt{a} \implies \sqrt{a} \leq a//x \leq a$. Q.E.D. $\endgroup$– barak manosAug 16, 2015 at 7:44
-
$\begingroup$ @barakmanos I don't follow your argument. $\endgroup$– Caleb StanfordAug 16, 2015 at 8:30
-
$\begingroup$ Could you elaborate? I don't exactly follow. $\endgroup$– 0327Aug 16, 2015 at 8:48
2 Answers
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$.
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}$.
-
$\begingroup$ And for $\lfloor\sqrt{a}\rfloor$, we have $\lfloor \sqrt{a}\rfloor = a//\lfloor \sqrt{a}\rfloor$ or $\lfloor \sqrt{a}\rfloor = a//(\lfloor \sqrt{a}\rfloor + 1)$, depending on whether $a < \lfloor\sqrt{a}\rfloor\cdot(\lfloor\sqrt{a}\rfloor+1)$ or not. $\endgroup$ Aug 16, 2015 at 9:35