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

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.


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?

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer

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



share|cite|improve this answer

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$.)

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.