Correctness of Fermat Factorization Proof

Question

I have asked similar questions regarding this proof. But now I would like to know if my reformulation (after perseverance and different thinking) is correct.

Prove: An odd integer $n \in \mathbb{N}$ is composite $\iff$ $n$ can be written as $n = x^2 - y^2 s.t. y+1 < x$

Proof: $\leftarrow$

Let $n$ be odd and consider $n= x^2-y^2 s.t. y+1 < x$

We can factor the difference of two squares as: $(x+y)(x-y)$ and we note for $n$ to be composite (not prime) $(x-y) > 1$. Thus we have shown this direction.

$\rightarrow$

Let $n$ be odd an composite. By definition of composite we have $n=ab$ for some odd integers $a$ and $b$. Now, working backwards:

$\dfrac{4ab}{4} = \dfrac{(a^2 + 2b + b^2)}{4} - \dfrac{(a^2-2b +b^2)}{4} = (\dfrac{a+b}{2})^2 - (\dfrac{a-b}{2})^2$. Thus, we shall take $x = \dfrac{a+b}{2}$ and $y =\dfrac{a-b}{2}$. And we have $n = x^2 - y^2$.

How do I get $y+1 < x$ in this direction?

Answer 1

You can't. However, you can show that $y+1<x$, which is what you should have been asking. Here it is, with $y=(a-b)/2, x=(a+b)/2$: $$ \begin{align} y+1 = \frac{a-b}{2}+1&=\frac{a-b+2}{2}<\frac{a+b}{2}\\ &\Longleftrightarrow a-b+2<a+b\\ &\Longleftrightarrow 2<2b \\ &\Longleftrightarrow 1<b \\ \end{align} $$ which you know is true, since if $n=ab$ is composite with $b\le a$ we must have $b>1$. (Note: in your statement we can't just have $a,b$ odd integers.) Other than that, your proof is just fine.

Answer 2

You need to specify that $0\le b\le a$ and that $b$ is not $1$. If $n$ is composite, we can certainly find such $a$ and $b$. Then we have $$x-y=\frac{a+b}{2}-\frac{a-b}{2}=b\gt 1.$$ (If you want the inequality $y+1\gt x$, interchange the roles of $x$ and $y$.)

Answer 3

Since $n$ is composite $a,b>1$ (WLOG $a\geq b$)

$$x-y=\dfrac{a+b}{2}-\dfrac{a-b}{2}=b>1$$

$$x>y+1$$