I'm reading through Crandall and Pomerance's "Prime Numbers: A Computational Perspective", and they give a brief description of the well known Fermat factorization method (Algorithm 5.1.1).
The algorithm takes an input $N$, and for each $a$ in the sequence $\lceil \sqrt{N} \rceil, \lceil \sqrt{N} \rceil +1, ...$ it calculates $c =a^2 -N$. If this number is a square, then we can write it as $c=b^2$ for some $b$, and so $N$ factors as $N = (a+b)(a-b)$. Indeed, all factorizations of odd, composite numbers occur in this way for some $a,b$, so we can be assured that the algorithm does terminate.
However, the authors note that the algorithm must terminate with a non-trivial factorization before we reach $$a = \left\lfloor \frac{N+9}{6} \right\rfloor,$$ (and this worst case only occurs when $N = 3p$ where $p$ is some prime) but I don't see why this should be the case.
Does anyone have any idea why the above should be true?
Suppose $N$ is an odd composite number, and let $d$ is the smallest factor of $N$ that is greater than $\sqrt N$, so that $N=de$ (with $e=N/d$) is the factorization that the Fermat method will find.
The Fermat method finds this factorization as $N=(a+b)(a-b)$, so we have $a+b=d$ and $a-b=e=N/d$; solving for $a$ yields $a=\frac12(d+N/d)$.
The function $\frac12(d+N/d)$ is an increasing function of $d$ for $d>\sqrt N$. Therefore the worst case is when $d$ is as large as possible. That happens when $e$ is as small as possible, that is, when $e=3$. We conclude that $a = \frac12(d+N/d) \le \frac12(N/3+3) = \frac16(N+9)$.