# Odd numbers expressed as : $x^2-y^2$

How to prove following statement :

Conjecture:

An odd number $n$ , $(n>1)$ can be uniquely expressed as : $n= x^2-y^2$ ; $x,y \in \mathbb{Z}^{*}$

if and only if $n$ is a prime number .

If $x-y=m$ , where $m>1$ then $m \mid n$

Proof :

$n=x^2-y^2=(y+m)^2-y^2=y^2+2\cdot y\cdot m +m^2-y^2 \Rightarrow$

$\Rightarrow n=m\cdot (2\cdot y+m) \Rightarrow m \mid n$

Therefore , if $m \neq 1$ it follows that $n$ is a composite number , but how to prove that every odd

composite number ,other than $1$ , has representation : $x^2-y^2$ , where $x-y>1$ ?

-
If $n=ab$ with $a\ge b>1$ (all odd), can you find an integer solution to the pair $x+y=a$, $x-y=b$? – Jyrki Lahtonen Jan 10 '12 at 15:47
@JyrkiLahtonen,Quite simple...thanks !! – pedja Jan 10 '12 at 16:01
What exactly is $\mathbb{Z}^{*}$? Does your conjecture hold for 9 (or the square of any other odd prime)? – Mike Jan 10 '12 at 16:36
@Mike,Set of positive integers + $0$... – pedja Jan 10 '12 at 16:39
@Mike, I was wondering about 9 myself, but only looked at the condition $x-y>1$. Didn't notice $\mathbf{Z}^*$! – Jyrki Lahtonen Jan 10 '12 at 16:41

Write $n=ab$ with $b>1$ and $x^2-y^2=(x+y)(x-y)$. Solve $x+y=a$, $x-y=b$. This system has integer solutions $x=(a+b)/2$ and $y=(a-b)/2$ because $a$ and $b$ are odd and hence $a\pm b$ is even. Finally, $x-y=b>1$, as required.

-
Uniqueness is an important part of the conjecture. Also, the conjecture is a biconditional (if and only if). It is not clear where your answer addresses either of these issues. – robjohn Aug 9 '12 at 14:45
@robjohn, my answer adresses the actual question at the end of the OP text: "but how to prove that every odd composite number...". – lhf Aug 9 '12 at 16:57
fair enough :-) – robjohn Aug 9 '12 at 17:57

HINT $\$ (Non) uniqueness follows from the composition law for differences of squares

$\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$

-
An elegant solution – whitehat Jan 12 '12 at 4:54
See also this question. – Bill Dubuque Aug 9 '12 at 14:38

If $n$ is odd and factors nontrivially as $ab$ with $a\le b$, then $n$ is the sum of $a$ consecutive odd numbers of which $b$ is the center one. Since the odd numbers are the first differences of the sequence of perfect squares, this means that $n$ is $(x+a)^2-x^2$ for some integer $x$.

-
Since $a-1$ is even it follows that $n$ is even also....,so I don't understand how $n$ can be $(x+a-1)^2-x^2$ – pedja Jan 10 '12 at 16:13
@pedja -- oops, off-by-one error. I was counting numbers instead of steps-between-numbers. Fixed. – Henning Makholm Jan 11 '12 at 19:34

I tried to solve & got somewhere & I am presenting the same. This may be very long way, but it may be someway ...

We want prime numbers only by performing $x^2 - y^2$. Since all primes (except $2$) are odd, this suggests that both $x$ and $y$ are neither even nor odd. One is odd and other is even

So, Let us take $x = 2k_2 + 1$ and $y = 2k_1$, with $k_2 \geq k_1$, $k_1,k_2 \in \mathbb{N}$ (This is necessary since in $x^2 - y^2, y^2$ must not be $0$, so $y$ must not be $0$, so $k_1$ must not be $0$) (And this assumption does not take all odd numbers and so not all primes, but later we can reverse the role of $x$ and $y$)

Now, our final result $N = x^2 - y^2$ is a prime number. And we need to prove that for every prime number, we only have a unique $x$ and $y$.

Let $k_2 = k_1 + m, m \in \{0,1,2,\cdots\}$
Replacing $k_2$,
we get $N = 4m^2 + 8k_1m + 4k_1 + 4m + 1$ which is a prime number.

It is observed that the unique solution for all primes should have $x$ and $y$ as consecutive numbers. So if we prove that is $N$ has to prime, then $m$ has to $0$ for any $k_1$ that makes $N$ prime then we are done.

Taking $k_1$ as $k$,

$N = 4m(m + 2k + 1) + 4k + 1$

If we take $m = 0, N = 4k + 1$ which is superset of all primes (except $2$).

But then we need to prove that above $N$ can never be prime for any other value of $m$.

-