Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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
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$? –  Marc van Leeuwen Oct 2 '12 at 13:44

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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