mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2010-01-28, 10:19   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default Sum of two squares: Peculiar property

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 2n-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 pn 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 p12*p2 or p19*p27*p3, etc. where the pi's are distinct prime numbers of the form 1 (mod 4) only? This is rather looking up to be somewhat tedious only...

Last fiddled with by Raman on 2010-01-28 at 10:20
Raman is offline   Reply With Quote
Old 2010-01-28, 15:26   #2
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

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)2 =
= 4n2 + 4n + 1
= 4(n2 + n) + 1

If n itself is also odd, n2 + 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 = (n2 + 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)
Quote:
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..

Quote:
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)
Quote:
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

Last fiddled with by only_human on 2010-01-28 at 15:33 Reason: changes a factor mistake from 2 to 4
only_human is offline   Reply With Quote
Old 2010-01-29, 07:27   #3
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

Quote:
Originally Posted by only_human View Post
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.
only_human is offline   Reply With Quote
Old 2010-01-29, 11:00   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×593 Posts
Default

Quote:
Originally Posted by only_human View Post
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:

(a2 + b2) * (x2 + y2) =

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

This pretty little formula has a simple generalization for numbers of the form a2+nb2 (n fixed; n=1 above)
wblipp is offline   Reply With Quote
Old 2010-01-29, 15:17   #5
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

100111010012 Posts
Default

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.

Quote:
Originally Posted by Raman View Post
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?

Last fiddled with by Raman on 2010-01-29 at 15:19
Raman is offline   Reply With Quote
Old 2010-02-02, 20:59   #6
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

23518 Posts
Default

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 x2+y2, such
that gcd(x,y) = 1.

Proof: Since p|N, so p|x2+y2. 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 = x2+y2 = 0 (mod p), x2(1+u2) = 0 (mod p).
p does not divide x, so (1+u2) = 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 u2 = -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 pc divide N, and pc+1 does not divide N, where c is odd,
let N = x2+y2 with gcd(x,y) = d.
then N = d2(X2+Y2) with gcd(X,Y)=1.
Putting X2+Y2 = n, N = d2n.
Let pm be the highest power of p, that divides d.
Since n = N/d2, so highest power of p that divides n is c-2m.
Since c is odd, c-2m > 0. So, p divides n. Since, n = X2+Y2,
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 x2+y2 = 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 z2 is quadratic residue,
so is -z2. Since k2 mod p = (p-k)2 mod p, the
quadratic residues are symmetric, so the distinct quadratic residues are from
k2, where k is between 1 to (p-1)/2 only.

Within this range, for some quadratic residue x2, there exist some other
value of y such that y2 = -x2 mod p. So, x2+y2 = 0 (mod p).
Let x2 + y2 = mp. Clearly, m>0.
Since, x2 + y2 <= 2*((p-1)/2)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 x2+y2 = p.

Proof by method of infinite descent.
If m=1, then there is nothing to prove at all.
If m>1, then x2+y2 = mp, so that x2+y2 = 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,
r2+s2 = 0 (mod m).
r and s cannot be both zero simultaneously, because if so, then m divides both x and y,
so m2 divides x2+y2 = mp, so m divides p. This is false
since p is prime.
Let r2+s2 = nm. Since, -m/2 < r,s < m/2, so n < m.

(x2+y2)(r2+s2) = m2np
(xr+ys)2 + (xs - yr)2 = m2np
Since x and r belong to the same residue class (mod m), and so does y and s,
m divides (xr+ys), since x2+y2 = 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
a2m2 + b2m2 = m2np
or that, a2 + b2 = np, where n < m.
This says that there exist integers a, b such that a2+b2 = np, where n<m.
We can keep continuing this descent until we get some integers u and v such that
u2+v2 = p, where p is a prime of form 1 (mod 4).

6) Next we have to prove such representation is unique.
Let N = a2+b2 = c2+d2, 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 a2+b2 = c2+d2
thus, a2-c2 = d2-b2
(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 = a2 + b2 + c2 + d2
4N = 2a2 + 2c2 + 2b2 + 2d2
4N = (a+c)2 + (a-c)2 + (d+b)2 + (d-b)2
4N = t2v2 + u2g2 + t2u2 + v2g2
4N = (t2+g2)(u2+v2)
N = ((t/2)2+(g/2)2)(u2+v2)
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 4b(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 (a2+b2)(c2+d2)
= (ac+bd)2 + (ad-bc)2
= (ac-bd)2 + (ad+bc)2
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 2k-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(a2+b2) = (a+b)2 + (a-b)2
Continuing this up only, we will get that
4(a2+b2) = (2a)2 + (2b)2
Are these the only ways of such representation? Sure enough already? Only this much?

Last fiddled with by Raman on 2010-02-02 at 21:00
Raman is offline   Reply With Quote
Old 2010-02-03, 02:53   #7
cmd
 
cmd's Avatar
 
"(^r'°:.:)^n;e'e"
Nov 2008
;t:.:;^

23·53 Posts
Question assonance

Quote:
Originally Posted by Raman View Post
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 x2+y2, such
that gcd(x,y) = 1.

Proof: Since p|N, so p|x2+y2. 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 = x2+y2 = 0 (mod p), x2(1+u2) = 0 (mod p).
p does not divide x, so (1+u2) = 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 u2 = -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 pc divide N, and pc+1 does not divide N, where c is odd,
let N = x2+y2 with gcd(x,y) = d.
then N = d2(X2+Y2) with gcd(X,Y)=1.
Putting X2+Y2 = n, N = d2n.
Let pm be the highest power of p, that divides d.
Since n = N/d2, so highest power of p that divides n is c-2m.
Since c is odd, c-2m > 0. So, p divides n. Since, n = X2+Y2,
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 x2+y2 = 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 z2 is quadratic residue,
so is -z2. Since k2 mod p = (p-k)2 mod p, the
quadratic residues are symmetric, so the distinct quadratic residues are from
k2, where k is between 1 to (p-1)/2 only.

Within this range, for some quadratic residue x2, there exist some other
value of y such that y2 = -x2 mod p. So, x2+y2 = 0 (mod p).
Let x2 + y2 = mp. Clearly, m>0.
Since, x2 + y2 <= 2*((p-1)/2)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 x2+y2 = p.

Proof by method of infinite descent.
If m=1, then there is nothing to prove at all.
If m>1, then x2+y2 = mp, so that x2+y2 = 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,
r2+s2 = 0 (mod m).
r and s cannot be both zero simultaneously, because if so, then m divides both x and y,
so m2 divides x2+y2 = mp, so m divides p. This is false
since p is prime.
Let r2+s2 = nm. Since, -m/2 < r,s < m/2, so n < m.

(x2+y2)(r2+s2) = m2np
(xr+ys)2 + (xs - yr)2 = m2np
Since x and r belong to the same residue class (mod m), and so does y and s,
m divides (xr+ys), since x2+y2 = 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
a2m2 + b2m2 = m2np
or that, a2 + b2 = np, where n < m.
This says that there exist integers a, b such that a2+b2 = np, where n<m.
We can keep continuing this descent until we get some integers u and v such that
u2+v2 = p, where p is a prime of form 1 (mod 4).

6) Next we have to prove such representation is unique.
Let N = a2+b2 = c2+d2, 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 a2+b2 = c2+d2
thus, a2-c2 = d2-b2
(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 = a2 + b2 + c2 + d2
4N = 2a2 + 2c2 + 2b2 + 2d2
4N = (a+c)2 + (a-c)2 + (d+b)2 + (d-b)2
4N = t2v2 + u2g2 + t2u2 + v2g2
4N = (t2+g2)(u2+v2)
N = ((t/2)2+(g/2)2)(u2+v2)
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 4b(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 (a2+b2)(c2+d2)
= (ac+bd)2 + (ad-bc)2
= (ac-bd)2 + (ad+bc)2
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 2k-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(a2+b2) = (a+b)2 + (a-b)2
Continuing this up only, we will get that
4(a2+b2) = (2a)2 + (2b)2
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] ).

Last fiddled with by cmd on 2010-02-03 at 02:54 Reason: color
cmd is offline   Reply With Quote
Old 2010-02-09, 09:19   #8
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2×1,877 Posts
Default

Quote:
Originally Posted by wblipp View Post
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:

(a2 + b2) * (x2 + y2) =

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

This pretty little formula has a simple generalization for numbers of the form a2+nb2 (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
Quote:
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 x2 + y2 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 (x2 + y2)(x'2 + y'2) = (xx' - yy')2 + (xy' + x'y)2, easily verifiable since both sides equal x2x'2 + y2y'2 + x'2y2 + x2y'2. He used this formula to build up solutions to the equation x2 + y2 = 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:
Quote:
Let Q(x,y) = x2 + y2
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]
Quote:
Fermat's theorem on sums of two squares asserts that an odd prime number p can be expressed as

p = x2 + y2

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.
Quote:
Contents

* 1 Euler's proof by infinite descent
* 2 Lagrange's proof through quadratic forms
* 3 Dedekind's two proofs using Gaussian integers
* 4 Zagier's "one-sentence proof"
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.

Last fiddled with by only_human on 2010-02-09 at 09:26 Reason: fix superscripts in quote
only_human is offline   Reply With Quote
Old 2010-02-09, 18:40   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×593 Posts
Default

Quote:
Originally Posted by only_human View Post
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 a2+k*b2 with k fixed. Easily shown by


(a2+k*b2) * (x2+k*y2)

= (ax+kby)2 + k (ay-bx)2
= (ax-kby)2 + k (ay+bx)2
wblipp is offline   Reply With Quote
Old 2010-02-10, 23:31   #10
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2×1,877 Posts
Default a minor tidbit of a puzzle

Quote:
Originally Posted by wblipp View Post
I was thinking of closure under multiplication of numbers of the form a2+k*b2 with k fixed. Easily shown by


(a2+k*b2) * (x2+k*y2)

= (ax+kby)2 + k (ay-bx)2
= (ax-kby)2 + k (ay+bx)2
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 12. 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?
only_human is offline   Reply With Quote
Old 2010-02-11, 10:19   #11
nibble4bits
 
nibble4bits's Avatar
 
Nov 2005

2·7·13 Posts
Cool

Quote:
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.
Quote:
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

Last fiddled with by nibble4bits on 2010-02-11 at 10:23 Reason: Note on how to prove this is always true
nibble4bits is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Peculiar activity in the 1M range... petrw1 PrimeNet 5 2011-01-14 18:01
Peculiar behaviour of prime numbers ..... spkarra Math 8 2009-07-20 22:47
Peculiar Case of Benjamin Button is AWESOME!!!!!!! jasong jasong 7 2009-01-01 00:50
A particularly peculiar problem fivemack Puzzles 7 2008-11-14 07:56
Special property for mod dsouza123 Math 4 2003-10-31 05:49

All times are UTC. The time now is 21:25.


Tue Aug 16 21:25:59 UTC 2022 up 40 days, 16:13, 1 user, load averages: 0.89, 1.17, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔