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?

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.