First, let me clarify that I am working solely with positive integers (natural numbers).
These proofs are not very formal, sorry. Typing them is a bit more tedious than writing them on paper
Theorem: All integers except those of the form 4n+2 are the difference of two squares.
Proof:Here, I will simply show by cases.
Let A be odd, B be even. That is, A=2n+1, B=2m. Then:
- A2-B2=
- (2n+1)2-(2m)2=
- 4n2+4n+1-4m2=
- 4(n2+n-m2)+1=
- 4l+1
Now, let A be even, B be odd. That is, A=2n, B=2m+1. Then:
- A2-B2=
- (2n)2-(2m+1)2=
- 4n2-4m2-4m-1=
- 4(n2-m2-m)-1=
- 4k-1=
- 4(k-1)+3=
- 4l+3=
If both are even, you have:
- A2-B2=
- (2n)2-(2m)2=
- 4n2-4m2=
- 4(n2-m2)=
- 4l
If both are odd, you have:
- A2-B2=
- (2n+1)2-(2m+1)2=
- 4n2+4n+1-4m2-4m-1=
- 4(n2+n-m2-n)
+1-1=
- 4l
[qed]
These are all the possible case, so you can have 4l,4l+1,and 4l+3 as the difference of two squares.
As a very simple proof that all odd integers can be the difference of two squares, just plug in the trivial solution (c+1)/2 and (c-1)/2 for A and B respectivels. Since c is odd, c+1 and c-1 are even, so you can divide by two. For a process to arrive to this conclusion, forst note that the difference of two consecutive squares is odd. That is:
(n+1)
2-n
2=
n2+2n+1-
n2=2n+1
So if you want to find, say, 23 as the difference of squares, 23=2n+1 means n=11. So 12
2-11
2=23. The powerful result of the math hack I presented says that because 23 is prime, this is the only solution.
Theorem: If c is composite and odd, then there is a non-trivial solution for A
2-B
2=c.
Proof:Let c be composite. That is, let c=n*m where n and m are neither 1. Since A
2-B
2=(A-B)(A+B), let n=(A-B) and m=(A+B). Then:
n+2B=A+B
n+2B=m
2B=n-m
B=(n-m)/2 ;since c is odd, n and m are odd, so n-m is even.
A=(n+m)/2 ;This, too, is an integer.
[qed]
Theorem: If c is an odd prime, then the non-trivial solution for A
2-B
2=c is the only solution.
Proof:Assume there is a non trivial solution for A and B, A=D, B=E. This implies that (D-E) and (D+E) are factors of c. Since c is prime, the only factors are 1 and c. Therefore, (D-E)=1, (D+E)=c. This means:
D+E=1+2E, D+E=c
1+2E=c
E=(c-1)/2
D=(c+1)/2
However, this is the trivial solution, so we have met a contradiction. Therefore, the trivial solution is the only solution
[qed]
EDIT: I opened up my notes and followed through some of my work and what I have found so far:
If there is a non-trivial solution for A
2-B
2=c, then it is of the form (A+2d)
2-(B-4e)
2 where d and e are integers. This will let me speed up my code as I can forget about half or 3/4 of the potential values. I am still working on cutting that down even more :)