Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is this proof correct:

An odd integer $n \in \mathbb{N}$ is composite iff it can be written in the form

$n = x^2 - y^2, y+1 < x$



Want: $n = ab$ Where $a$ and $b$ are odd integers (since $n$ is odd)

Let $n = x^2 - y^2, x > y + 1$. Let $x = \dfrac{a+b}{2}$ and let $y= \dfrac{a-b}{2}$ where $a$ and $b$ are odd integers.

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

$ = (x+y)(x-y) \iff (\dfrac{a+b}{2} + \dfrac{a-b}{2})\cdot(\dfrac{a+b}{2} - \dfrac{a-b}{2})$

Thus we have $ab$.

Now I could do similar steps backwards to prove the other direction.

share|cite|improve this question
It looks solid, except that you should explicitly mention where the condition that $x\gt y+1$ comes into play (hint; there's another condition on $a$ and $b$ that you haven't mentioned - actually, two more, one being $a\geq b$ since $y$ is positive...) – Steven Stadnicki Sep 30 '12 at 17:32
Is it the fact that $x \geq \lceil \sqrt n \rceil$? – CodeKingPlusPlus Sep 30 '12 at 17:49
No, that's actually moot - it's what that condition implies about $a$ and $b$. (Slightly larger hint: every number $n$ has a factorization $n=ab$; what do you need to ensure that $n$ isn't prime?) – Steven Stadnicki Sep 30 '12 at 18:55
$a \neq 1$ and $b \neq 1$ – CodeKingPlusPlus Sep 30 '12 at 20:51

The part when you say "Let $x=\frac{a+b}2$ and let $y$..." is not really clear. In the $\Leftarrow$ direction $x$ and $y$ should be considered as given, and define $a$ and $b$ using them, and show that they are integers.

share|cite|improve this answer

Your Answer


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.