# A Proposition related to Fermat Factorization Method

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?

• Please show what you've tried and where you're stuck to get better help from the community. – Saad Oct 4 '18 at 1:25
• Consider $n=ab=(x-y)(x+y)$. – Saad Oct 4 '18 at 1:26

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.