A Proposition related to Fermat Factorization Method

Question

The following proposition is so related to Fermat Factorization method. The proposition states the following:

Let $n$ be an odd positive integer. If $n$ is composite, then there is an integer $x$ in the interval $[\sqrt{n},\frac{n+1}{2})$ that makes $x^2-n$ a square.

How can such proposition be proven?

Answer 1

Building upon @Alex Francisco useful comment and combining it with my instructor notes,

Here is The Proof:

since $n$ is an odd composite number, it can be written as $n=ab$.

Define $x,y$ such that: $$x = \frac{a-b}{2}$$ and $$y =\frac{a+b}{2}$$ Hence: $$y^2 - x^2 = (y-x)(y+x) = ab = n$$ or: $$y^2 = x^2+n$$ This proves the existence. What remains is to show that $y$ lies in the interval $[\sqrt{n}, \frac{n+1}{2})$.

1. Since $(y^2 = x^2+n)\geq n$, then $y \geq \sqrt{n}$.
2. Since $a-b < ab+1$, then $(\frac{a-b}{2} = y) < (\frac{ab+1}{2} = \frac{n+1}{2})$.

From $(1)$ and $(2)$, the result holds as desired.