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

Re: Formula

Expand Messages
  • djbroadhurst
    ... 6531 of such numbers are primes or prime powers, and they can all be written as the sum of two relatively prime squares only once. It appears that numbers
    Message 1 of 11 , Oct 3, 2009
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "marku606" <mark.underwood@...> wrote:

      >> Just checked up to 300,000 for numbers of the form 8n+5:
      6531 of such numbers are primes or prime powers, and they
      can all be written as the sum of two relatively prime
      squares only once. It appears that numbers of the form 8n+5
      which are not prime or prime powers cannot be written as the
      sum of two relatively prime powers only once.
      For number of the form 8n+1: 6572 of such numbers are
      primes or prime powers, but only 6510 of these can be
      written as the sum of two relatively prime squares only
      once. The sixty two that cannot are all primes powers,
      specifically, primes raised to an even power.
      As in the case for numbers of the form 8n+5, it appears
      that numbers of the form 8n+1 which are not prime or prime
      powers cannot be written as the sum of two relatively prime
      powers only once. <<

      All this is very simply explained
      by unique factorization in K(sqrt(-1)).

      1) A number N is the sum of two squares if and only if
      every prime divisor of N that is congruent to 3 mod 4
      occurs to an even power.

      2) An odd number N is the sum of two coprime squares in precisely
      one way if only if N is a prime congruent to 1 mod 4
      or a power of such a prime.

      Note that (1) is a consequence of Theorem 252 of Hardy and Wright,
      that the primes of K(sqrt(-1)) are: 1 + I, the rational primes
      congruent to 3 mod 4, the factors a + b*I of the rational primes
      congruent to 1 mod 4, and the associates of these primes.

      To understand (2), suppose that
      p = norm(a+I*b) = a^2 + b^2 and
      q = norm(c+I*d) = c^2 + d^2
      are distinct rational primes congruent to 1 mod 4.
      Then we may write
      p*q = norm((a+I*b)*(c+I*d)) = (a*c-b*d)^2 + (b*c+a*d)^2
      p*q = norm((a+I*b)*(c-I*d)) = (a*c+b*d)^2 + (b*c-a*d)^2
      in two essentially different ways.
      But for any power k of p, the only sum of coprime squares is
      p^k = norm((a+I*b)^k)
      since if we try something like
      p^k = norm((a+I*b)^(k-j)*(a-I*b)^j)
      with k > j > 0, then p will divide both of the resultant squares.

      David
    • marku606
      ... Yes, of course. :) Simplicity is one thing; understanding the simple can be downright elusive to the untrained. Thank you David for your explanation. By
      Message 2 of 11 , Oct 3, 2009
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
        >

        > All this is very simply explained
        > by unique factorization in K(sqrt(-1)).

        Yes, of course. :)

        Simplicity is one thing; understanding the simple can be downright elusive to the untrained. Thank you David for your explanation. By the powers of heaven, one day I'm going to understand it.

        Mark
      • djbroadhurst
        In primenumbers@yahoogroups.com, ... This is clearly false. Simply consider 20 = 2^2 + 4^2. David
        Message 3 of 11 , Oct 4, 2009
        • 0 Attachment
          In primenumbers@yahoogroups.com,
          Kermit Rose <kermit@...> wrote:

          > An integer z is a sum of two squares in exactly one way
          > if and only if it is one of the following forms:
          > (1) an odd power of 2, z = 2**(2*m+1) for m > 0
          > (2) a prime equal to 1 mod 4
          > (3) the square of a prime equal to 1 mod 4 or
          > (4) z = p*h**2 where p is either 2, or an odd prime
          > equal to 1 mod 4, or the square of an odd prime equal
          > to 1 mod 4, and h has all prime factors equal to 3 mod 4.

          This is clearly false. Simply consider 20 = 2^2 + 4^2.

          David
        • djbroadhurst
          ... and then Kermit Rose mistakenly claimed ... with the irrelevant observations ... Note that 10^2 and 5^2 are not coprime. David
          Message 4 of 11 , Oct 4, 2009
          • 0 Attachment
            I wrote:

            > An odd number N is the sum of two coprime squares in precisely
            > one way if and only if N is a prime congruent to 1 mod 4
            > or a power of such a prime.

            and then "Kermit Rose" mistakenly claimed

            > David, a Minor correction is needed here

            with the irrelevant observations

            > 2**2 + 11**2 = 5**3
            > 10**2 + 5**2 = 5**3

            Note that 10^2 and 5^2 are not coprime.

            David
          Your message has been successfully submitted and would be delivered to recipients shortly.