Sum of two squares: Peculiar property

[Raman]

Yesterday, I had some fun with WIMS online calculator on decomposing any positive integer N
into sum of two squares.

On playing with it, I found that, as it says
A positive integer cannot be a sum of two squares if it has a prime factor of the form 3 (mod 4) to an odd power. Why? I would like to see a proof for it!

Since any square will be of the form 0 or 1 (mod 4) only, it is directly quite obvious that sum of two squares cannot be 3 (mod 4). A square can only be 0, 1, 4 or 9 (mod 16).
But even if it is the product of two distinct primes of the form 3 (mod 4), or something else multiplied with it, that make the product equal to 1 (mod 4), still is it not possible at all, to be a sum of two squares? How come? :surprised Any proof that is being available anywhere for this case only?

Further, that decomposition into two squares has many more surprising properties.
1) If N is the product of n distinct primes of the form 1 (mod 4), then the number of ways that N can be written as sum of two squares is 2^n-1. Show how!
2) If N has even one single prime factor of form 3 (mod 4) to an odd power, then decomposing N as sum of two squares is impossible!
3) If p is a prime of the form 1 (mod 4), then the number of ways that pⁿ can be written up as sum of two squares is given by Int((n/2)+1). Again why?
4) A number multiplied with a power of 2, does not change the number of ways of decomposing that number into sum of two squares at all!
5) Further, how to determine the number of ways of decomposing into sum of two squares for some complex expressions of the form p₁²*p₂ or p₁⁹*p₂⁷*p₃, etc. where the p_i's are distinct prime numbers of the form 1 (mod 4) only? This is rather looking up to be somewhat tedious only...

[only_human]

I'm going to take a small stab at this but I will botch it because I don't swim with the big fish.

In binary, it is helpful to notice that odd numbers squared are not only of the form 1 (mod) 4, they are are more specifically of the form 1 (mod) 8. In a binary representation that means they always ends in 001. This is because:
(2n+1)² =
= 4n² + 4n + 1
= 4(n² + n) + 1

If n itself is also odd, n² + n will be even (odd number + odd number equals even number) so another 2 can be factored out making the total result of the odd number squared = 8k + 1. This is the form 1 (mod) 8.
(k = (n² + n)/2)

An even number will always have a 0 bit less significant than the least significant 1 bit. These number of these least significant 0s will be doubled after squaring (as they do in any integer base i.e. 10 * 10 = 100 etc.)

The binary representation of squaring the bits starting from the least significant 1 bit will be exactly like any odd number squared (except for the magnitude/position as changed by doubling the number of 0s to the right of it)

4) A number multiplied with a power of 2, does not change the number of ways of decomposing that number into sum of two squares at all!

The power of 2 is completely represented by the 0s to the right of the least significant one. All of it is merely a representation of magnitude (in binary) and does not affect how the more significant bits are added together.

So if I have made this at all clear, adding squares can be directly thought of as selecting patterns ending in either 00 or 001 and adding a combination of them together..

Since any square will be of the form 0 or 1 (mod 4) only, it is directly quite obvious that sum of two squares cannot be 3 (mod 4). A square can only be 0, 1, 4 or 9 (mod 16).
But even if it is the product of two distinct primes of the form 3 (mod 4), or something else multiplied with it, that make the product equal to 1 (mod 4), still is it not possible at all, to be a sum of two squares? How come? Any proof that is being available anywhere for this case only?

The sum of two squares can only be 1 (mod 4) if it is also 1 (mod 8).

That is, the sum of two squares will only be values that can be attained by adding selections ending in 00 or 001 together)

2) If N has even one single prime factor of form 3 (mod 4) to an odd power, then decomposing N as sum of two squares is impossible!

Since the binary representation of squares ends in 00 or 001, there is no way to select two values ending like these and add them together get a value ending in 11 (adding three values ending in 001 would work, but not two)..

I'm stopping here because the rest doesn't come so easily to me and I think I have already bitten off more than I can chew

[only_human]

Originally Posted by only_human

The power of 2 is completely represented by the 0s to the right of the least significant one. All of it is merely a representation of magnitude (in binary) and does not affect how the more significant bits are added together

Don't invest too much time trying to figure out what I meant by this; I blurred sums and products in my thinking and was waving my hands without the chops to do so.

Thank you, everyone, for the mercy of not replying directly to my message but I don't want to derail the thread so feel free to answer the puzzle. I, myself am still thinking about the puzzles numbered section and may join in again on that aspect.

[wblipp]

Originally Posted by only_human

I, myself am still thinking about the puzzles numbered section and may join in again on that aspect.

You may find it helpful to know that the product of two numbers that are a sum of squares is again a sum of squares:

(a² + b²) * (x² + y²) =

(ax+by)² + (ay-bx)²

This pretty little formula has a simple generalization for numbers of the form a²+nb² (n fixed; n=1 above)

[Raman]

It is quite puzzling that every prime number of the form 1 (mod 4) has
UNIQUE representation as sum of two squares,
while every prime number of the form 3 (mod 4) has no such representation.
This is obvious though, as I had only mentioned up above already.

Originally Posted by Raman

Even if it is the product of two distinct primes of the form 3 (mod 4), or something else multiplied with it, that make the product equal to 1 (mod 4), still is it not possible at all, to be a sum of two squares?

Any number with prime factor of the form 3 (mod 4), to an odd power has no representation as sum of two squares at all. In order to prove this fact:

If all prime factors are of the form 1 (mod 4), then product is 1 (mod 4)
If the product is 3 (mod 4), it quite obviously has no decomposition into two squares.
In order to make the product equal to 1 (mod 4), there should be even number of primes of the form 3 (mod 4), atleast one of them much be distinct from the others, such that it has no decomposition into two squares, as by the rule saying.

A square can be only 0,1,4,9 (mod 16) or 0,1,4 (mod 8)
Trying to prove that fact:
If all primes are of form 1 (mod 16), then the product is 1 (mod 16)
If there are two distinct primes of the form 3 (mod 4), then the product is 9 (mod 16), no there can be a prime of the form 9 (mod 16), or more primes of the form 3 (mod 4), and then the product can be 1 (mod 16) as well.
There can be primes of the form 9 (mod 16) as well, that are of the form 1 (mod 4). With these primes, with primes of form 1 (mod 16), the product can be 1 (mod 16) or 9 (mod 16) as well.
With these, with primes of form 5 (mod 16) and then 13 (mod 16), the product can be either 1 (mod 16), 5 (mod 16), 9 (mod 16), or 13 (mod 16).
Each has its own way of splitting up into sum of two squares.
If N is 1 (mod 16), it can be sum of two squares of form 0 (mod 16) & 1 (mod 16)
If N is 9 (mod 16), it can be sum of two squares of form 0 (mod 16) & 9 (mod 16)
If N is 5 (mod 16), it can be sum of two squares of form 4 (mod 16) & 1 (mod 16)
If N is 13 (mod 16), it can be sum of two squares of form 4 (mod 16) & 9 (mod 16) as well.
Sum of two squares can be only 0,1,2,4,5,8,9,10,13 (mod 16).
But even then, it covers up all sums of the form 1 (mod 4).

The fact to be proved is that: If a number of the form 1 (mod 4) has some decomposition into sum of two squares, then it has no prime factors of the form 3 (mod 4) to an odd power at all. How to approach it up?

[Raman]

Got up the proofs from one of the books within library only...

1) It is obvious that a square can be only 0 or 1 (mod 4). So, sum
of two squares cannot be 3 (mod 4).

2) Next, the proof that if p divides N, and p is prime of form 3 (mod 4)
then N has no sum of two squares representation in lowest terms.
That is, N cannot be represented as x²+y², such
that gcd(x,y) = 1.

Proof: Since p|N, so p|x²+y². If p|x, then p|y also,
so gcd(x,y) is not 1. So, p cannot divide x or y. So, x and y are congruent
between 1 and p-1 (mod p). Let y=ux, where 1 <= u <= p-1. Then, since
N = x²+y² = 0 (mod p), x²(1+u²) = 0 (mod p).
p does not divide x, so (1+u²) = 0 (mod p). So, -1 is a quadratic residue
(mod p). This is false when p is a prime of form 3 (mod 4). So, N has no sum of two
squares representation in lowest terms (x,y) = 1. If it exists, it should be such
that y = ux (mod p) such that u² = -1 (mod p), where p is a prime of form 3 (mod 4) only.

3) Next the proof that if N has a prime factor p of form 3 (mod 4) to an odd power,
then N has no sum of two squares representation at all.
Let p^c divide N, and p^c+1 does not divide N, where c is odd,
let N = x²+y² with gcd(x,y) = d.
then N = d²(X²+Y²) with gcd(X,Y)=1.
Putting X²+Y² = n, N = d²n.
Let p^m be the highest power of p, that divides d.
Since n = N/d², so highest power of p that divides n is c-2m.
Since c is odd, c-2m > 0. So, p divides n. Since, n = X²+Y²,
with gcd(X,Y) = 1, p dividing N with p being a prime of form 1 (mod 4). This is
not possible by (2). Hence the result.

Even if N contains power of p to an even power, the representation of N as sum
of two squares can be only multiples of those values of N divided by all those primes
that are congruent to 3 (mod 4).

4) If p is a prime of form 1 (mod 4), then there exist values of x,y less than p
such that x²+y² = mp, where 0 < m < p.

Proof: If p is prime of form 1 (mod 4), then -1 is a quadratic residue (mod p).
If z is quadratic residue, then so is -z. Since z² is quadratic residue,
so is -z². Since k² mod p = (p-k)² mod p, the
quadratic residues are symmetric, so the distinct quadratic residues are from
k², where k is between 1 to (p-1)/2 only.

Within this range, for some quadratic residue x², there exist some other
value of y such that y² = -x² mod p. So, x²+y² = 0 (mod p).
Let x² + y² = mp. Clearly, m>0.
Since, x² + y² <= 2*((p-1)/2)², so m<p.

5) Next comes the proof that for any prime p of form 1 (mod 4), there exist values of
x,y such that x²+y² = p.

Proof by method of infinite descent.
If m=1, then there is nothing to prove at all.
If m>1, then x²+y² = mp, so that x²+y² = 0 (mod m).
Let r and s be minimal residues of x and y (mod m), such that -m/2 < r,s < m/2.
r is congruent to x (mod m) and y is congruent to s (mod m). So,
r²+s² = 0 (mod m).
r and s cannot be both zero simultaneously, because if so, then m divides both x and y,
so m² divides x²+y² = mp, so m divides p. This is false
since p is prime.
Let r²+s² = nm. Since, -m/2 < r,s < m/2, so n < m.

(x²+y²)(r²+s²) = m²np
(xr+ys)² + (xs - yr)² = m²np
Since x and r belong to the same residue class (mod m), and so does y and s,
m divides (xr+ys), since x²+y² = 0 (mod m),
m also divides (xs-yr) = (xy-yx) mod m = 0 (mod m).
Let (xr+ys) = am, and that (xs-yr) = bm, then
a²m² + b²m² = m²np
or that, a² + b² = np, where n < m.
This says that there exist integers a, b such that a²+b² = np, where n<m.
We can keep continuing this descent until we get some integers u and v such that
u²+v² = p, where p is a prime of form 1 (mod 4).

6) Next we have to prove such representation is unique.
Let N = a²+b² = c²+d², with two distinct sum
of two squares representation. Then N is composite.

Proof: Since even number other than 2 is composite, we will consider only the case when N is odd.
2 has only one such representation, by the way.
If N is odd. One of a,b is odd, and so is c,d pair as well.
Let a,c be odd. b,d be even. Let a>c, then b<d.
Since we have that a²+b² = c²+d²
thus, a²-c² = d²-b²
(a-c)(a+c) = (d-b)(d+b) where a-c, a+c, d-b, d+b are all even.
Let gcd(a-c,d-b) = g, where g is clearly even.
Let a-c = ug, d-b = vg, where gcd(u,v)=1. Then,
ug(a+c) = vg(d+b), u(a+c) = v(d+b). So u divides d+b, v divides a+c.
Let a+c = tv. Putting that, then it becomes that d+b = tu.
Since that gcd(u,v)=1 and a+c and d+b are both odd, hence that t is being even only.

So, 2N = a² + b² + c² + d²
4N = 2a² + 2c² + 2b² + 2d²
4N = (a+c)² + (a-c)² + (d+b)² + (d-b)²
4N = t²v² + u²g² + t²u² + v²g²
4N = (t²+g²)(u²+v²)
N = ((t/2)²+(g/2)²)(u²+v²)
Since t and g are both odd, so we have that (t/2) and (g/2) are both integers.
So, N is representable as product of two integers, both being clearly > 1 only.
Thus, N is composite.

EVERY PRIME OF FORM 1 (MOD 4) CAN BE UNIQUELY REPRESENTED AS SUM OF TWO SQUARES.

7) It is also given in the book that every number that is not of form 4^b(8c+7)
can be represented as sum of three squares.

8) Regarding number of ways of representing an arbitrary value of N as sum of two squares:
Since (a²+b²)(c²+d²)
= (ac+bd)² + (ad-bc)²
= (ac-bd)² + (ad+bc)²
The product of two distinct primes of form 1 (mod 4) can be represented as sum of two squares
in two ways. Pending exercise to prove that these are the only ways of such representation.
Why is it so?
Continuing up in this way, it is certainly possible to see that the product of k distinct primes of form
1 (mod 4) can be represented in 2^k-1 ways. Only that much? Sure about that?

9) Regarding product with a power of 2 will not change the number of ways of representation at all:
This is because of the fact that
2(a²+b²) = (a+b)² + (a-b)²
Continuing this up only, we will get that
4(a²+b²) = (2a)² + (2b)²
Are these the only ways of such representation? Sure enough already? Only this much?

[cmd]

Originally Posted by Raman

Got up the proofs from one of the books within library only...

1) It is obvious that a square can be only 0 or 1 (mod 4). So, sum
of two squares cannot be 3 (mod 4).

2) Next, the proof that if p divides N, and p is prime of form 3 (mod 4)
then N has no sum of two squares representation in lowest terms.
That is, N cannot be represented as x²+y², such
that gcd(x,y) = 1.

Proof: Since p|N, so p|x²+y². If p|x, then p|y also,
so gcd(x,y) is not 1. So, p cannot divide x or y. So, x and y are congruent
between 1 and p-1 (mod p). Let y=ux, where 1 <= u <= p-1. Then, since
N = x²+y² = 0 (mod p), x²(1+u²) = 0 (mod p).
p does not divide x, so (1+u²) = 0 (mod p). So, -1 is a quadratic residue
(mod p). This is false when p is a prime of form 3 (mod 4). So, N has no sum of two
squares representation in lowest terms (x,y) = 1. If it exists, it should be such
that y = ux (mod p) such that u² = -1 (mod p), where p is a prime of form 3 (mod 4) only.

3) Next the proof that if N has a prime factor p of form 3 (mod 4) to an odd power,
then N has no sum of two squares representation at all.
Let p^c divide N, and p^c+1 does not divide N, where c is odd,
let N = x²+y² with gcd(x,y) = d.
then N = d²(X²+Y²) with gcd(X,Y)=1.
Putting X²+Y² = n, N = d²n.
Let p^m be the highest power of p, that divides d.
Since n = N/d², so highest power of p that divides n is c-2m.
Since c is odd, c-2m > 0. So, p divides n. Since, n = X²+Y²,
with gcd(X,Y) = 1, p dividing N with p being a prime of form 1 (mod 4). This is
not possible by (2). Hence the result.

Even if N contains power of p to an even power, the representation of N as sum
of two squares can be only multiples of those values of N divided by all those primes
that are congruent to 3 (mod 4).

4) If p is a prime of form 1 (mod 4), then there exist values of x,y less than p
such that x²+y² = mp, where 0 < m < p.

Proof: If p is prime of form 1 (mod 4), then -1 is a quadratic residue (mod p).
If z is quadratic residue, then so is -z. Since z² is quadratic residue,
so is -z². Since k² mod p = (p-k)² mod p, the
quadratic residues are symmetric, so the distinct quadratic residues are from
k², where k is between 1 to (p-1)/2 only.

Within this range, for some quadratic residue x², there exist some other
value of y such that y² = -x² mod p. So, x²+y² = 0 (mod p).
Let x² + y² = mp. Clearly, m>0.
Since, x² + y² <= 2*((p-1)/2)², so m<p.

5) Next comes the proof that for any prime p of form 1 (mod 4), there exist values of
x,y such that x²+y² = p.

Proof by method of infinite descent.
If m=1, then there is nothing to prove at all.
If m>1, then x²+y² = mp, so that x²+y² = 0 (mod m).
Let r and s be minimal residues of x and y (mod m), such that -m/2 < r,s < m/2.
r is congruent to x (mod m) and y is congruent to s (mod m). So,
r²+s² = 0 (mod m).
r and s cannot be both zero simultaneously, because if so, then m divides both x and y,
so m² divides x²+y² = mp, so m divides p. This is false
since p is prime.
Let r²+s² = nm. Since, -m/2 < r,s < m/2, so n < m.

(x²+y²)(r²+s²) = m²np
(xr+ys)² + (xs - yr)² = m²np
Since x and r belong to the same residue class (mod m), and so does y and s,
m divides (xr+ys), since x²+y² = 0 (mod m),
m also divides (xs-yr) = (xy-yx) mod m = 0 (mod m).
Let (xr+ys) = am, and that (xs-yr) = bm, then
a²m² + b²m² = m²np
or that, a² + b² = np, where n < m.
This says that there exist integers a, b such that a²+b² = np, where n<m.
We can keep continuing this descent until we get some integers u and v such that
u²+v² = p, where p is a prime of form 1 (mod 4).

6) Next we have to prove such representation is unique.
Let N = a²+b² = c²+d², with two distinct sum
of two squares representation. Then N is composite.

Proof: Since even number other than 2 is composite, we will consider only the case when N is odd.
2 has only one such representation, by the way.
If N is odd. One of a,b is odd, and so is c,d pair as well.
Let a,c be odd. b,d be even. Let a>c, then b<d.
Since we have that a²+b² = c²+d²
thus, a²-c² = d²-b²
(a-c)(a+c) = (d-b)(d+b) where a-c, a+c, d-b, d+b are all even.
Let gcd(a-c,d-b) = g, where g is clearly even.
Let a-c = ug, d-b = vg, where gcd(u,v)=1. Then,
ug(a+c) = vg(d+b), u(a+c) = v(d+b). So u divides d+b, v divides a+c.
Let a+c = tv. Putting that, then it becomes that d+b = tu.
Since that gcd(u,v)=1 and a+c and d+b are both odd, hence that t is being even only.

So, 2N = a² + b² + c² + d²
4N = 2a² + 2c² + 2b² + 2d²
4N = (a+c)² + (a-c)² + (d+b)² + (d-b)²
4N = t²v² + u²g² + t²u² + v²g²
4N = (t²+g²)(u²+v²)
N = ((t/2)²+(g/2)²)(u²+v²)
Since t and g are both odd, so we have that (t/2) and (g/2) are both integers.
So, N is representable as product of two integers, both being clearly > 1 only.
Thus, N is composite.

EVERY PRIME OF FORM 1 (MOD 4) CAN BE UNIQUELY REPRESENTED AS SUM OF TWO SQUARES.

7) It is also given in the book that every number that is not of form 4^b(8c+7)
can be represented as sum of three squares.

8) Regarding number of ways of representing an arbitrary value of N as sum of two squares:
Since (a²+b²)(c²+d²)
= (ac+bd)² + (ad-bc)²
= (ac-bd)² + (ad+bc)²
The product of two distinct primes of form 1 (mod 4) can be represented as sum of two squares
in two ways. Pending exercise to prove that these are the only ways of such representation.
Why is it so?
Continuing up in this way, it is certainly possible to see that the product of k distinct primes of form
1 (mod 4) can be represented in 2^k-1 ways. Only that much? Sure about that?

9) Regarding product with a power of 2 will not change the number of ways of representation at all:
This is because of the fact that
2(a²+b²) = (a+b)² + (a-b)²
Continuing this up only, we will get that
4(a²+b²) = (2a)² + (2b)²
Are these the only ways of such representation? Sure enough already? Only this much?

( ... seems to us that [a, b, c, d], they play as much as [b, d, p, q] ).

[only_human]

Originally Posted by wblipp

You may find it helpful to know that the product of two numbers that are a sum of squares is again a sum of squares:

(a² + b²) * (x² + y²) =

(ax+by)² + (ay-bx)²

This pretty little formula has a simple generalization for numbers of the form a²+nb² (n fixed; n=1 above)

I find myself a bit reluctant to see this thread go just yet without taking note of the many people that have stepped on its' path and how far their steps traveled.

One book on my shelf is Harvey Cohn's Advanced Number Theory. On page 2 of the introduction he tells me

The first step in the general theory of quadratic diophantine equations was probably the famous theorem of Fermat (1640) relating to a (homogeneous) form in x, y. A prime number is representable in an essentially unique manner by the form x² + y² for integral x and y if and only if p is congruent to 1 modulo 4 (or p = 2). [...] Fermat used an identity from antiquity (x² + y²)(x'² + y'²) = (xx' - yy')² + (xy' + x'y)², easily verifiable since both sides equal x²x'² + y²y'² + x'²y² + x²y'². He used this formula to build up solutions to the equation x² + y² = m for values of m which are not necessarily prime.

It then goes on to tell me that Fermat's result generalized slightly to allow x and y not relatively prime is stated more compactly (and generalizing slightly to allow x and y not relatively prime) as Q(x,y) = m. This is interesting for what follows:

Let Q(x,y) = x² + y²
Then all relatively prime solutions to the problem of representing Q(x,y) = m for any integer are achieved by the successive application of two results called the Genus Theorem and the Composition Theorem [...] In the intervening years until about 1800, Euler, Lagrange, Legendre, and others invented analogous results for a variety of quadratic forms. Gauss (1800) was the first on to see the larger problem and achieve a main result that is too involved even to state here

Well last little bit is really saying something (at least to me) because this book always requires a cup of coffee and still generates a headache.
Wblip's comment about the generalization intrigued me so I did a little online searching and was a bit surprised at the directions some of it led. First Proofs of Fermat's theorem on sums of two squares [Wikipedia]

Fermat's theorem on sums of two squares asserts that an odd prime number p can be expressed as

p = x² + y²

with integer x and y if and only if p is congruent to 1 (mod 4). The statement was announced by Fermat in 1640, but he supplied no proof.

The "only if" clause is easy: a perfect square is congruent to 0 or 1 modulo 4, hence a sum of two squares is congruent to 0, 1, or 2. An odd prime number is congruent to either 1 or 3 modulo 4, and the second possibility has just been ruled out. The first proof that such a representation exists was given by Leonhard Euler in 1747 and was quite complicated. Since then, many different proofs have been found. Among them, the proof using Minkowski's theorem about convex sets and Don Zagier's stunningly short proof based on involutions especially stand out.

I look at bit further at the identity wblipp mentioned and learn that it is "Brahmagupta's identity, also sometimes called Fibonacci's identity" which tells me that "The identity is a special case (n = 2) of Lagrange's identity" I think that this n is the exponent and not the second term coefficient that wblipp mentioned so perhaps I have stepped a bit astray. Then I read that Lagrange's identity is itself "a special form of the Binet–Cauchy identity" (to which I then look). This mentions in passing "Lagrange's identity, which is a stronger version of the Cauchy–Schwarz inequality for the Euclidean space." Well, even I have heard of the Cauchy-Schwarz inequality, so I know that I have spanned a great deal of mathematics with all these little steps. Or then again I might be thinking about "Schwarz-Christoffel" but anyway I am sure that I am not in Kansas anymore.

And these steps have skirted an elephant in the room (I presume): Quadratic Reciprocity. That is Chapter 11 in Harvey Cohn's book. This scares me a bit because I feel some would say that all of this would best start there.

[wblipp]

Originally Posted by only_human

I think that this n is the exponent and not the second term coefficient that wblipp mentioned so perhaps I have stepped a bit astray.

I was thinking of closure under multiplication of numbers of the form a²+k*b² with k fixed. Easily shown by

(a²+k*b²) * (x²+k*y²)

= (ax+kby)² + k (ay-bx)²
= (ax-kby)² + k (ay+bx)²

[only_human]

Originally Posted by wblipp

I was thinking of closure under multiplication of numbers of the form a²+k*b² with k fixed. Easily shown by

(a²+k*b²) * (x²+k*y²)

= (ax+kby)² + k (ay-bx)²
= (ax-kby)² + k (ay+bx)²

Thank you, I was wondering about that.

As one might notice, my approach to mathematics is really more like a survey with wonder but not much real work. In this vein, I noticed something about odd squares that I don't recall ever hearing explicitly mentioned. It doesn't merit a thread or any real work but I present it as a minor tidbit of a puzzle:

As I mentioned earlier in the thread, the binary representation of an odd integer squared ends with "001." For the puzzle, we lop this invariant portion off the representation and consider what is left.

To avoid quibbles I prefer to skip 1². In sequence the next would be 3 squared followed by 5 squared... Looking at the binary representations of the squares these are 1001 and 11001... After lopping off the "001" tail these numbers are "1" and "11" in binary. So looking at all of the "trimmed" numbers, what are they often called?

[nibble4bits]

prev&=0
FOR i& = 3 TO 9999 STEP 2
j& = (i& ^ 2)
j& = INT(j& / 8)
PRINT i&, j&, j& - prev&
prev& = j&
NEXT i&

That should work in QBASIC. Here's some C++ code to do roughly the same thing. Obviously a snippet. Add headers, etc. yourself.

int i=0, j=0, prev=0, diff=0;
for(i=3; i<10000; i+=2){
j=(i/8) * i;
diff=prev - j;
cout << "odd integer: " << i << "\t right-shifted square: " << j << "\t difference: " << diff << endl;
}

Recognize the pattern? ;)

::EDIT:: If you want a proof, consider the property of (n+1)^2-n^2 = n^2+2n+1-n^2 = 2n+1