1
$\begingroup$

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)

  • 1
    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$?2012-10-02

1 Answers 1

4

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.