# Prove that a positive odd integer $N>1$ has a unique representation in the form $N=x^2-y^2$ iff N is prime

Here x and y range over the nonnegative integers. I was wondering how to show that if n is a odd integer which has a unique representation in that form, then n is prime.

-
Dear Z_Fang, please don't use homework as the only tag for your question. Your question is related to some mathematical subject; use a tag pertaining to that subject! – J. M. Oct 15 '11 at 1:10
Er... Thanks for your edition. – Vladimir Oct 15 '11 at 1:13

HINT $\$ Nonuniquness is an immediate consequence of the following composition law

$\rm\qquad\qquad\ (a^2-b^2)\ (A^2-B^2)\ =\ (a\:A+b\:B)^2-(a\:B+A\:b)^2$

$\rm\qquad\qquad\ \phantom{(a^2-b^2)\ (A^2-B^2)}\ =\ (a\:A-b\:B)^2-(a\:B-A\:b)^2$

E.g. composing $\rm\ 7 = 4^2 - 3^2\$ with $\ 11 = 6^2 - 5^2\$ yields for $\rm\: 7\cdot 11\:$ the following $2$ rep's

$\rm\qquad\qquad\ (4^2-3^2)\ (6^2-5^2)\ =\ (4\cdot 6+3\cdot 5)^2-(4\cdot 5+6\cdot 3)^2\ =\ 39^2 - 38^2$

$\rm\qquad\qquad\ \phantom{(4^2-3^2)\ (6^2-5^2)}\ =\ (4\cdot 6-3\cdot 5)^2-(4\cdot 5-6\cdot 3)^2\ =\ 9^2 - 2^2$

-

Hint: Let $n$ be an odd composite (positive) integer. Then there exist (odd) integers $a \gt 1$, $b \gt 1$ such that $n=ab$. Use this factorization to produce a solution of the equation $x^2-y^2=n$ in non-negative integers other than $x=\frac{n+1}{2}$, $y=\frac{n-1}{2}$.

Added: Without loss of generality we may assume that $a \ge b$. Then we can take $$x=\frac{a+b}{2}, \qquad y=\frac{a-b}{2}.$$

-
you mean $x=\frac{n+1}{2}$ and the same remark for $y$ – Elaqqad Jan 28 at 13:46
@Elaqqad: Thank you! It is never too late to fix things. – André Nicolas Jan 28 at 14:22

Hint: Factor $x^2-y^2$ as the product of two polynomials.

-
Yes, I have known that any odd prime p can be written uniquely as $p=\left(\frac{p+1}{2}\right)^2-\left(\frac{p-1}{2}\right)^2$. And I was wondering how to show that if n is a odd integer which has a unique representation in that form, then n is prime. – Vladimir Oct 15 '11 at 2:43
@Z_Fang: it was not $p$ that should be factored, but $x^2-y^2$ – Ross Millikan Oct 15 '11 at 2:59
$p=x^2-y^2=(x+y)(x-y).$ And necessarily we have $x-y=1$ and $x+y=p$, from which it might be inferred that $x=\frac{p+1}{2}, y=\frac{p-1}{2}$, thus... Is it wrong? – Vladimir Oct 15 '11 at 3:11
@Z_Fang: not wrong, but the first shows that if the factorization is unique that $p$ is prime. Then if $p$ is prime, there is only one factorization, which shows $x-y=1$ or else there would be another. My point was that $x=\frac{p+1}{2}, y=\frac{p-1}{2}$ was not as useful this time. – Ross Millikan Oct 15 '11 at 4:37