## This has to be flaky

Expand Messages
• I m sure this must fall down - can someone confirm pointing out where? Cheers, David All primes of the form 4n+1 are the sum of two squares For every odd
Message 1 of 14 , Jan 3 2:04 PM
I'm sure this must fall down - can someone confirm pointing out where?

Cheers,

David

All primes of the form 4n+1 are the sum of two squares

For every odd integer n there are two squares a and b such that a - b = n.

Further for each n there is a number m which is the sum of a and b.

Assume a is odd and b is even

lemma 1) Each m is of the form 4n+1

Proof :

lemma 2) Any odd number which is multiplied by itself has the form 4n+1

Proof: As far as odd numbers are concerned there are those that mod 4 = 1
and those that mod 4 = 3, giving us two forms

4n + 1 and 4n + 3

Multiplying an odd number of the form 4n + 1 by itself produces another
number mod 4 = 1:

(4n + 1)(4n + 1)

16n + 4n + 4n + 1

24n + 1

24n mod 4 = 0

1 mod 4 = 1

Multiplying an odd number of the form 4n + 3 by itself produces a number mod
4 = 1:

(4n + 3)(4n + 3)

16n + 12n + 12n + 9

40n + 9

40n mod 4 = 0

9 mod 4 = 1

This proves lemma 2.

lemma 3) Any even number which is multiplied by itself has the form 4n

This is pretty much self evident.

Going back to lemma 1 we have 1 odd square of the form 4n + 1 and 1 even
square of the form 4q

4q + 4n + 1 mod 4 = 1

This proves lemma 1: m = a + b = 4n + 1

-----------------------------------------------------------------

lemma 4) A number of the form 4n + 1 can be the product of

(4x + 1) * (4y + 1)

or

(4x + 3) * (4y + 3)

but not

(4x + 3) * (4y + 1)

case 1)

(4x + 1) * (4y + 1) mod 4 = 1

16xy + 4x + 4y + 1

16xy mod 4 = 0

4x mod 4 = 0

4y mod 4 = 0

1 mod 4 = 1

case 2)

(4x + 3) * (4y + 3) mod 4 = 1

16xy + 12x + 12y + 9

16xy mod 4 = 0

12x mod 4 = 0

12y mod 4 = 0

9 mod 4 = 1

case 3)

(4x + 3) * (4y + 1) mod 4 !=1

16xy + 4x + 12y + 3

16xy mod 4 = 0

4x mod 4 = 0

12y mod 4 = 0

3 mod 4 = 3

Based on lemma 4 m must be of the form (4x + 1)*(4y + 1) or (4x + 3)*(4y +
3). But numbers of the form (4x + 3)*(4y + 3) are composite with each term
having a minimum value of 3 so this leaves numbers of the form (4x + 1)*(4y
+ 1)

therefore for m to be prime

m = a + b = (4x + 1) * (4y + 1)

but if m is prime then one of x or y must be 0

m = a + b = 1 * (4y + 1)

m = a + b = 4y + 1

and this satisfies lemma 1 proving that all primes of the form 4n+1 are the
sum of two squares
• All primes of the form 4n+1 are the sum of two squares This is a known fact, proved by Hardy, and involves fairly simple algebra and the pigeon-hole
Message 2 of 14 , Jan 4 4:26 AM
'All primes of the form 4n+1 are the sum of two squares'

This is a known fact, proved by Hardy, and involves fairly simple algebra
and the pigeon-hole principle (given n balls and n-1 holes, at least one
hole will contain 2 balls). So you are attempting to prove this some other
way.

'For every odd integer n there are two squares a and b such that a - b = n.'

Very obvious, (a+1)^2 - a^2 = 2a+1

'Further for each n there is a number m which is the sum of a and b.'

And so m=2a^2+2a+1

'Assume a is odd and b is even'

How? and Why?

'Lemma1''Lemma2''Lemma3''Lemma4'

These are all fine, although most mathematicians would let you assume these
facts without proof.

'Based on lemma 4 m must be of the form (4x + 1)*(4y + 1) or (4x + 3)*(4y +
3). #But numbers of the form (4x + 3)*(4y + 3) are composite with each term
having a minimum value of 3@ so this leaves numbers of the form (4x + 1)*(4y
+ 1)

#therefore for m to be prime

m = a + b = (4x + 1) * (4y + 1)@

#but if m is prime then one of x or y must be 0@

m = a + b = 1 * (4y + 1)

m = a + b = 4y + 1

#and this satisfies lemma 1 proving that all primes of the form 4n+1 are the
sum of two squares'@

I can't follow this at all. I have marked particularly confusing passages
with a #@.

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
• Er, Phil, Hardy seems a bit late to credit. What about Fermat, for goodness sakes?
Message 3 of 14 , Jan 4 5:24 AM
Er, Phil, Hardy seems a bit late to credit.
What about Fermat, for goodness sakes?
• Thanks for the reply, Jon. Here is some clarification ... + ... term ... 1)*(4y ... But numbers of the form (4x + 3)*(4y + 3) are composite with each term
Message 4 of 14 , Jan 4 6:45 AM
Thanks for the reply, Jon. Here is some clarification

> 'Based on lemma 4 m must be of the form (4x + 1)*(4y + 1) or (4x + 3)*(4y
+
> 3). #But numbers of the form (4x + 3)*(4y + 3) are composite with each
term
> having a minimum value of 3@ so this leaves numbers of the form (4x +
1)*(4y
> + 1)

But numbers of the form (4x + 3)*(4y + 3) are composite with each term
having a minimum value of 3.

(4x + 3)*(4y + 3)
let x = 0 and y = 0
(4*0+3)*(4*0+3) = 9
The smallest value therefore for (4x + 3)*(4y + 3) is 9 which means that for
any x or y (4x + 3)*(4y + 3) must be composite.

>
> #therefore for m to be prime
>
> m = a + b = (4x + 1) * (4y + 1)@
>

Because all odd numbers that mod 4 =1 and are of the form (4x + 3)*(4y + 3)
must be composite then this means that if m is to be prime it must be of the
form (4x + 1) * (4y + 1).

> #but if m is prime then one of x or y must be 0@

If m is prime then either (4y + 1) must equal 1 or (4x + 1) must equal 1. If
neither equal 1 then (4x + 1)*(4y + 1) must be composite and therefore not
prime. For (4x + 1) to equal 1 x must be 0, and for (4y + 1) to equal 1 y
must be 0. So if m is prime either x or y is 0 and the one which isn't 0
must be =>1.

<FLAKY>
>
> m = a + b = 1 * (4y + 1)
>
> m = a + b = 4y + 1
>
> #and this satisfies lemma 1 proving that all primes of the form 4n+1 are
the
> sum of two squares'@
>
</FLAKY>

This is the bit I'm not really sure whether it follows logically. We've
decided that if m is prime then either (4x + 1) equals 1 or (4y + 1) = 1.
For the sake of argument I chose (4x + 1) to equal 1 giving us

m = a + b = 1 * (4y + 1)

This is equivalent to

m = a + b = 4y + 1
or
m = 4y+1

In lemma 1 we have "Each m is of the form 4n+1".
And as m = 4y + 1 is equivalent to m = 4n+1 then we satisfy that m is of the
"right form" and therefore all primes that mod 4 =1 are the sum of two
squares.

I hope this clarifies this more.

Cheers,
David

> I can't follow this at all. I have marked particularly confusing passages
> with a #@.
>
> Jon Perry
> perry@...
> http://www.users.globalnet.co.uk/~perry/maths/
> BrainBench MVP for HTML and JavaScript
> http://www.brainbench.com
>
>
>
>
>
>
• ... Shurely Shome mishtake, Mrsh Moneypenny? Phil ===== The answer to life s mystery is simple and direct: Sex and death. -- Ian Lemmy Kilminster
Message 5 of 14 , Jan 4 7:56 AM
> Er, Phil, Hardy seems a bit late to credit.
> What about Fermat, for goodness sakes?

Shurely Shome mishtake, Mrsh Moneypenny?

Phil

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• Phil ... Yep, I was misattributing a misattribution, sorry. Here I try to set the history straight. Theorem [Fermat] : Every prime p which is congruent to 1
Message 6 of 14 , Jan 4 9:08 AM
Phil

> Shurely Shome mishtake

Yep, I was misattributing a misattribution, sorry.

Here I try to set the history straight.

Theorem [Fermat] : Every prime p which is congruent
to 1 modulo 4 can be expressed as a sum of two squares.

Jon credited this to Hardy.

Fermat proved it by a "method of descent", roughly like this:

1) We know that x^2=1 mod p has a solution.
Chose x such that 2|x|<p. Then x^2+1 is a positive
multiple of p and is less than p^2.

2) We have found a pair (x1,y1)=(x,1) with

x1^2+y1^2=m*p and m in [1,p-1].

I claim that if m>1 we can make another pair,
say (x2,y2), with

x2^2+y2^2=n*p and n in [1,m-1]

as follows:

x2=(u*x1+v*y1)/m
y2=(v*x1-u*y1)/m

with

u=x1 mod m and 2*|u|<m
v=y1 mod m and 2*|v|<m

giving

u^2+v^2=x1^2+y1^2 mod m=0 mod m

and hence

u^2+v^2=n*m for some n in [1,m-1]

and hence

x2^2+y2^2=(u^2+v^2)*(x1^2+y1^2)/m^2=(n*m)*(m*p)/m^2=n*p

as claimed.

3) Keep on trucking until you get to

x^2+y^2=p

[End sketch of Fermat's proof]

When I saw this, in a little book by
T.H. Jackson, more than a quarter of a century
ago, it took my breath away;
Fermat descent is a truly wonderful thing.

David
• This first line of the proof had a typo :-( Should be 1) We know that x^2=-1 mod p has a solution. ....................! otherwise I think it s OK.
Message 7 of 14 , Jan 4 9:19 AM
This first line of the proof had a typo :-(
Should be
1) We know that x^2=-1 mod p has a solution.
....................!
otherwise I think it's OK.
• ... [SNIP - somewhat canny maths] ... Indeed. Cornaccia-Smith (p=x^2+d.y^2) owes a lot to its ideas, methinks. Phil ===== The answer to life s mystery is
Message 8 of 14 , Jan 4 9:53 AM
> Here I try to set the history straight.
>
> Theorem [Fermat] : Every prime p which is congruent
> to 1 modulo 4 can be expressed as a sum of two squares.
>
> Jon credited this to Hardy.
>
> Fermat proved it by a "method of descent", roughly like this:

[SNIP - somewhat canny maths]

> 3) Keep on trucking until you get to
>
> x^2+y^2=p
>
> [End sketch of Fermat's proof]
>
> When I saw this, in a little book by
> T.H. Jackson, more than a quarter of a century
> ago, it took my breath away;
> Fermat descent is a truly wonderful thing.

Indeed. Cornaccia-Smith (p=x^2+d.y^2) owes a lot to its ideas, methinks.

Phil

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• Neither Bookfinder nor Amazon could find a sellable copy of Jackson: http://www.amazon.co.uk/exec/obidos/ASIN/0710079982 It was fine little book, since Walter
Message 9 of 14 , Jan 4 10:11 AM
Neither Bookfinder nor Amazon could find a sellable copy of Jackson:

http://www.amazon.co.uk/exec/obidos/ASIN/0710079982

It was fine little book, since Walter Ledermann, the series editor,
demanded the highest standards of pedagogy, aimed at good high-school

The 1975 price was 1.5 GPB ~ \$2.

David
• The proof I have is much simpler. sorry about the Hardy credit - it s in his book, and I thought I had read something somewhere which said it was Hardy s. This
Message 10 of 14 , Jan 4 10:35 AM
The proof I have is much simpler. sorry about the Hardy credit - it's in his
book, and I thought I had read something somewhere which said it was
Hardy's.

This is from Number Theory by Naoki Sato, which is freely available as a
PDF.

There exists 'a' such that a^2=-1modp

Consider the set of integer ax-y, x,y integers, o<=x<sqrt(p).

The number of possible pairs (x,y) is then
[floor(sqrt(p))+1]^2>[sqrt(p)]^2=p

So, by the pigeonhole principle, there exist 0<=x1,x2,y1,y2<sqrt(p) such
that

ax1-y1 = ax2 - y2 modp.

Let x=x1-x2 and y=y1-y2. At least one of x and y is non-zero.

Thus x^2 + y^2 is a multiple of p, and 0<x^2+y^2<sqrt(p)^2+sqrt(p)^2=2p,

Hence x^2+y^2=p.

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
• ... Your original wording offers you a get out of jail card - it probably was proved by Hardy, whether any other number of mathematicians proved it before that
Message 11 of 14 , Jan 4 1:16 PM
--- Jon Perry <perry@...> wrote:
> The proof I have is much simpler. sorry about the Hardy credit - it's in his
> book, and I thought I had read something somewhere which said it was
> Hardy's.

Your original wording offers you a get out of jail card - it probably was
proved by Hardy, whether any other number of mathematicians proved it before
that is irrelevant.

> This is from Number Theory by Naoki Sato, which is freely available as a
> PDF.
>
> There exists 'a' such that a^2=-1modp

There may exist 2.

> Consider the set of integer ax-y, x,y integers, o<=x<sqrt(p).

I assume you mean 0 not o.

> The number of possible pairs (x,y) is then

infinite, as there's no restriction on y. I assume you meant 0<=x,y<sqrt(p)

> [floor(sqrt(p))+1]^2>[sqrt(p)]^2=p
>
> So, by the pigeonhole principle, there exist 0<=x1,x2,y1,y2<sqrt(p) such
> that
>
> ax1-y1 = ax2 - y2 modp.
>
> Let x=x1-x2 and y=y1-y2. At least one of x and y is non-zero.

The pidgeon hole principle cannot immediately on its own guarantee that
both x and y are non-zero, but ax-y == 0 (mod p) implies that if one is
zero, the other is too, a contradiction. Therefore you conclude that both
are non-zero.

> Thus x^2 + y^2 is a multiple of p, and 0<x^2+y^2<sqrt(p)^2+sqrt(p)^2=2p,
>
> Hence x^2+y^2=p.

I like it. It's less constructive than the Fermat version, but nonetheless,
you can't doubt its verity. I quite like pigeonhole proofs, often they're
very elegant, this is no exception.

Phil

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• Jackson taught Fermat s original proof by descent for an excellent pedagogic reason: to prepare the student for Lagrange s tour de force, by descent, in
Message 12 of 14 , Jan 4 1:17 PM
Jackson taught Fermat's original proof by descent for an excellent
pedagogic reason: to prepare the student for Lagrange's
tour de force, by descent, in proving

Theorem [Lagrange]: Every natural number can be expressed
as a sum of four integer squares

whose proof proceeds along the same lines as the one I sketched.

Short proofs are not always the most instructive.
• From: http://turnbull.dcs.st-and.ac.uk/~history/Mathematicians/Fermat.html Fermat described his method of infinite descent and gave an example on how it could
Message 13 of 14 , Jan 5 10:33 AM
From:

http://turnbull.dcs.st-and.ac.uk/~history/Mathematicians/Fermat.html

'Fermat described his method of infinite descent and gave an example on how
it could be used to prove that every prime of the form 4k + 1 could be
written as the sum of two squares. For suppose some number of the form 4k +
1 could not be written as the sum of two squares. Then there is a smaller
number of the form 4k + 1 which cannot be written as the sum of two squares.
Continuing the argument will lead to a contradiction. What Fermat failed to
explain in this letter is how the smaller number is constructed from the
larger. One assumes that Fermat did know how to make this step but again his
failure to disclose the method made mathematicians lose interest. It was not
until Euler took up these problems that the missing steps were filled in.'

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/