Loading ...
Sorry, an error occurred while loading the content.

This has to be flaky

Expand Messages
  • David Litchfield
    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, 2003
    • 0 Attachment
      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
    • Jon Perry
      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, 2003
      • 0 Attachment
        '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/
        http://www.users.globalnet.co.uk/~perry/DIVMenu/
        BrainBench MVP for HTML and JavaScript
        http://www.brainbench.com
      • David Broadhurst <d.broadhurst@open.ac.u
        Er, Phil, Hardy seems a bit late to credit. What about Fermat, for goodness sakes?
        Message 3 of 14 , Jan 4, 2003
        • 0 Attachment
          Er, Phil, Hardy seems a bit late to credit.
          What about Fermat, for goodness sakes?
        • David Litchfield
          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, 2003
          • 0 Attachment
            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/
            > http://www.users.globalnet.co.uk/~perry/DIVMenu/
            > BrainBench MVP for HTML and JavaScript
            > http://www.brainbench.com
            >
            >
            >
            >
            >
            >
          • Phil Carmody
            ... 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, 2003
            • 0 Attachment
              --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
              > 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!?
              Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
              http://mailplus.yahoo.com
            • David Broadhurst <d.broadhurst@open.ac.u
              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, 2003
              • 0 Attachment
                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
              • David Broadhurst <d.broadhurst@open.ac.u
                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, 2003
                • 0 Attachment
                  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.
                • Phil Carmody
                  ... [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, 2003
                  • 0 Attachment
                    --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
                    > 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!?
                    Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
                    http://mailplus.yahoo.com
                  • David Broadhurst <d.broadhurst@open.ac.u
                    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, 2003
                    • 0 Attachment
                      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
                      or first year undergrad students.

                      The 1975 price was 1.5 GPB ~ $2.

                      David
                    • Jon Perry
                      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, 2003
                      • 0 Attachment
                        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/
                        http://www.users.globalnet.co.uk/~perry/DIVMenu/
                        BrainBench MVP for HTML and JavaScript
                        http://www.brainbench.com
                      • Phil Carmody
                        ... 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, 2003
                        • 0 Attachment
                          --- 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!?
                          Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
                          http://mailplus.yahoo.com
                        • David Broadhurst <d.broadhurst@open.ac.u
                          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, 2003
                          • 0 Attachment
                            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.
                          • Jon Perry
                            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, 2003
                            • 0 Attachment
                              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/
                              http://www.users.globalnet.co.uk/~perry/DIVMenu/
                              BrainBench MVP for HTML and JavaScript
                              http://www.brainbench.com
                            • David Broadhurst <d.broadhurst@open.ac.u
                              Thanks Jon for that St Andrews link! Just goes to show that pedagogy is the enemy of good history. David
                              Message 14 of 14 , Jan 5, 2003
                              • 0 Attachment
                                Thanks Jon for that St Andrews link!
                                Just goes to show that pedagogy is the enemy of good history.
                                David
                              Your message has been successfully submitted and would be delivered to recipients shortly.