# Prove an odd natural integer is composite if and only if it can be written in the form $n=x^2-y^2, y+1 < x$

Prove an odd natural integer is composite if and only if it can be written in the form $n=x^2-y^2, y+1 < x$

I do not see why $y+1 < x$ and I do not really know where to start.

Proof:

$\leftarrow$

Consider $n= x^2-y^2$

We can factor this as:

$n=(x-y)(x+y)$ and thus we have a factorization for the composite integer $n$.

However, we must ensure that n is composite and not prime. Therefore for $n$ to be composite $(x-y)$ or $(x+y)$ must not equal $1$. Clearly, $(x-y)$ is the only factor that could equal $1$. So we set up the inequality:

$x-y > 1 \iff x > y+1$ Hence, we have shown this direction. (How do I show $n$ is odd)

-
HINT: Do you know the standard factorisation $(x^2-y^2)=(x+y)(x-y)$? That should get you started. You'll need the other condition later - what is the difference between a prime and a composite number? To go the other way you will need to start from a factorisation of your composite odd number and work backwards. – Mark Bennet Oct 2 '12 at 13:06
thanks! I think I got one direction. I'll add that in to my question! – CodeKingPlusPlus Oct 2 '12 at 13:15
Actually, my edit does not show that $n$ is odd – CodeKingPlusPlus Oct 2 '12 at 13:25
It is a hypothesis that $n$ is odd, prior the the equivalence that must be shown, so for both directions you may assume $n$ to be odd. Indeed $3^2-1^2=8$ shows that even numbers can also occur as $x^2-y^2$. You still need to do the "only if" part though: for odd $n$ to be composite, it must be that $n=x^2-y^2$ for some appropriate $x,y$. – Marc van Leeuwen Oct 2 '12 at 13:36
Clearly $x,y$ must be integer and non-negative (without the latter $5=3^2-(-2)^2$ gives a counterexample to "if"). Is $x$ or $y$ allowed to be $0$? – Marc van Leeuwen Oct 2 '12 at 13:44

Hint: More precisely, we want to prove that if $n$ is composite, there are non-negative integers $x$ and $y$, such that $x^2-y^2=n$ and $x \gt y+1$.
Suppose that $n$ is positive, odd, and composite. Then there exist positive odd integers $a$ and $b$, with $1\lt a\le b\lt n$ such that $ab=n$. Are there reasonable choices for $x+y$ and $x-y$?
Remark: $1.$ One wants to insist that our integers $x$ and $y$ are non-negative, since as pointed out by Marc van Leeuwen, the criterion would not distinguish between composites and non-composites.
We cannot avoid allowing $y=0$. For if $n=p^2$ where $p$ is an odd prime, then the only representations using non-negative integers are $\left(\frac{p+1}{2}\right)^2 -\left(\frac{p-1}{2}\right)^2$, in which case $y+1=x$, and $p^2-0^2$. For a concrete example use, say, $n=9$.
$2.$ Tiny comment: In your proof that if $n$ is non-composite, then $n$ does not have the requisite kind of representation, the non-composite number $1$ was not considered.