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.
Prove that a positive odd integer N>1 has a unique representation in the form $N=x^2-y^2$ iff N is prime
3 Answers
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: 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
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