Sign up ×
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.

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.

share|cite|improve this question
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. is back. Oct 15 '11 at 1:10
Er... Thanks for your edition. –  Vladimir Oct 15 '11 at 1:13

3 Answers 3

up vote 2 down vote accepted

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$

share|cite|improve this answer

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

share|cite|improve this answer
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

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

share|cite|improve this answer
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

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.