0
$\begingroup$

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.

3 Answers 3

3

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$

1

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

  • 0
    @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.2011-10-15
1

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

  • 0
    @Elaqqad: Thank you! It is never too late to fix things.2015-01-28