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

primes and squares

Expand Messages
  • Mark Underwood
    Hi all, Some observations follow. These will be old news to number theorists (I assume), but I ve found it quite interesting. I make no guarantee that the
    Message 1 of 6 , Apr 3, 2005
    • 0 Attachment
      Hi all,

      Some observations follow. These will be old news to number theorists
      (I assume), but I've found it quite interesting. I make no guarantee
      that the (rather hasty) observations below are entirely correct :)


      ********


      One way to consider all the (odd) primes is by grouping them
      according to the remainder when divided by 8. Four (about equal)
      groups result, each with their particular modulus eight value: 1,3,5
      or 7. Four sample primes from each group respectively are 17,19,13
      and 23.

      Now it turns out that each of these groups has a distinctive feature
      as they relate to 3 quadratic expressions:

      x^2 + y^2
      x^2 + 2*y^2
      x^2 - 2*y^2

      where y is less than half the expression.

      Each prime from the mod8 == 1 group has exactly one solution for each
      of the above three quadratic relations.

      Each prime from the mod8 == 3 group has exactly one solution for the
      x^2 + 2y^2 relation and none for the other two.

      Each prime from the mod8 == 5 group has exactly one solution for the
      x^2 + y^2 relation and none for the other two.

      Each prime from the mod8 == 7 group has exactly one solution for the
      x^2 - 2y^2 relation and none for the other two.

      It appears that a composite number n can and will look like a prime
      in this regard if and only if

      n = p * 2^m

      n = p^2 * 2^m

      n = p1^2 * p2 * 2^m The two primes involved must be from different
      groups, and not from the mod8 ==1 group.

      n = p1^2 * p2^2 * p3 * 2^m The three primes involved must be from
      three different groups and not from the mod8 == 1 group.


      ****


      More observations, but I'll spare you :)


      Mark
    • Michael Gian
      Mark, Please humor a newbie; I m not sure I understand what has a solution means in context of this message. ... theorists ... guarantee ... correct :) ...
      Message 2 of 6 , Apr 3, 2005
      • 0 Attachment
        Mark,

        Please humor a newbie; I'm not sure I understand what "has a
        solution" means in context of this message.

        --- In primenumbers@yahoogroups.com, "Mark Underwood"
        <mark.underwood@s...> wrote:
        >
        > Hi all,
        >
        > Some observations follow. These will be old news to number
        theorists
        > (I assume), but I've found it quite interesting. I make no
        guarantee
        > that the (rather hasty) observations below are entirely
        correct :)
        >
        >
        > ********
        >
        >
        > One way to consider all the (odd) primes is by grouping them
        > according to the remainder when divided by 8. Four (about equal)
        > groups result, each with their particular modulus eight value:
        1,3,5
        > or 7. Four sample primes from each group respectively are
        17,19,13
        > and 23.
        >
        > Now it turns out that each of these groups has a distinctive
        feature
        > as they relate to 3 quadratic expressions:
        >
        > x^2 + y^2
        > x^2 + 2*y^2
        > x^2 - 2*y^2
        >
        > where y is less than half the expression.
        >
        > Each prime from the mod8 == 1 group has exactly one solution for
        each
        > of the above three quadratic relations.

        When you say "has exactly one solution for each of the above three
        quadratic relations" do you mean that there exists a unique pair,
        (x,y) such that:
        x^2 + y^2 == 1 mod 8 and
        x^2 + 2*y^2 == 1 mod 8 and
        x^2 - 2*y^2 == 1 mod 8 ?

        I count at least four (x,y)that solve all three:
        {(1,0), (3,0), (5,0), (7,0)},
        and many more that solve one, if not two of them.
        I am also finding many pairs which solve {3, 5, 7} mod 8, per what
        is said below.

        Perhaps you can explain where I am missing the meaning of "solves".

        Michael

        >
        > Each prime from the mod8 == 3 group has exactly one solution for
        the
        > x^2 + 2y^2 relation and none for the other two.
        >
        > Each prime from the mod8 == 5 group has exactly one solution for
        the
        > x^2 + y^2 relation and none for the other two.
        >
        > Each prime from the mod8 == 7 group has exactly one solution for
        the
        > x^2 - 2y^2 relation and none for the other two.
        >
        > It appears that a composite number n can and will look like a
        prime
        > in this regard if and only if
        >
        > n = p * 2^m
        >
        > n = p^2 * 2^m
        >
        > n = p1^2 * p2 * 2^m The two primes involved must be from
        different
        > groups, and not from the mod8 ==1 group.
        >
        > n = p1^2 * p2^2 * p3 * 2^m The three primes involved must be from
        > three different groups and not from the mod8 == 1 group.
        >
        >
        > ****
        >
        >
        > More observations, but I'll spare you :)
        >
        >
        > Mark
      • Mark Underwood
        Hi Michael Yes I wasn t very clear. Here s an example. The prime 17 is in the mod8==1 group. (Actually the smallest member.) According to the model there
        Message 3 of 6 , Apr 3, 2005
        • 0 Attachment
          Hi Michael

          Yes I wasn't very clear. Here's an example.

          The prime 17 is in the mod8==1 group. (Actually the smallest member.)
          According to the model there should be

          exactly one way in which x^2 + y^2 = 17,
          exactly one way in which x^2 + 2*y^2 = 17
          exactly one way in which x^2 - 2*y^2 = 17.

          where y < 17/2.

          Solutions are:

          1^2 + 4^2 = 17 (x=1,y=4)
          3^2 + 2*2^2 = 17 (x=3,y=2)
          5^2 - 2*2^2 = 17 (x=5,y=2)


          Of course it would be more interesting to try higher primes like
          100913, which is also of the mod8=1 variety. So like 17 it should
          (and does) have exactly one solution for each of the three equations.


          The prime 100999 is of the mod8=7 variety. So
          x^2 + y^2 = 100999 should (and does) have no solution.
          x^2 + 2*y^2 = 100999 should (and does) have no solution.
          x^2 - 2*y^2 = 100999 should (and does) have exactly one solution.


          Compare this to the composite number 100521.

          x^2 + y^2 = 100521 has 2 solutions.
          x^2 + 2*y^2 = 100521 has 10 solutions.
          x^2 - 2*y^2 = 100521 has 2 solutions.


          I'm embarrassed to say that I have no idea how mundane such
          observations are.


          Mark





          --- In primenumbers@yahoogroups.com, "Michael Gian" <work.gian@s...>
          wrote:
          >
          > Mark,
          >
          > Please humor a newbie; I'm not sure I understand what "has a
          > solution" means in context of this message.
          >
          > --- In primenumbers@yahoogroups.com, "Mark Underwood"
          > <mark.underwood@s...> wrote:
          > >
          > > Hi all,
          > >
          > > Some observations follow. These will be old news to number
          > theorists
          > > (I assume), but I've found it quite interesting. I make no
          > guarantee
          > > that the (rather hasty) observations below are entirely
          > correct :)
          > >
          > >
          > > ********
          > >
          > >
          > > One way to consider all the (odd) primes is by grouping them
          > > according to the remainder when divided by 8. Four (about equal)
          > > groups result, each with their particular modulus eight value:
          > 1,3,5
          > > or 7. Four sample primes from each group respectively are
          > 17,19,13
          > > and 23.
          > >
          > > Now it turns out that each of these groups has a distinctive
          > feature
          > > as they relate to 3 quadratic expressions:
          > >
          > > x^2 + y^2
          > > x^2 + 2*y^2
          > > x^2 - 2*y^2
          > >
          > > where y is less than half the expression.
          > >
          > > Each prime from the mod8 == 1 group has exactly one solution for
          > each
          > > of the above three quadratic relations.
          >
          > When you say "has exactly one solution for each of the above three
          > quadratic relations" do you mean that there exists a unique pair,
          > (x,y) such that:
          > x^2 + y^2 == 1 mod 8 and
          > x^2 + 2*y^2 == 1 mod 8 and
          > x^2 - 2*y^2 == 1 mod 8 ?
          >
          > I count at least four (x,y)that solve all three:
          > {(1,0), (3,0), (5,0), (7,0)},
          > and many more that solve one, if not two of them.
          > I am also finding many pairs which solve {3, 5, 7} mod 8, per what
          > is said below.
          >
          > Perhaps you can explain where I am missing the meaning of "solves".
          >
          > Michael
          >
          > >
          > > Each prime from the mod8 == 3 group has exactly one solution for
          > the
          > > x^2 + 2y^2 relation and none for the other two.
          > >
          > > Each prime from the mod8 == 5 group has exactly one solution for
          > the
          > > x^2 + y^2 relation and none for the other two.
          > >
          > > Each prime from the mod8 == 7 group has exactly one solution for
          > the
          > > x^2 - 2y^2 relation and none for the other two.
          > >
          > > It appears that a composite number n can and will look like a
          > prime
          > > in this regard if and only if
          > >
          > > n = p * 2^m
          > >
          > > n = p^2 * 2^m
          > >
          > > n = p1^2 * p2 * 2^m The two primes involved must be from
          > different
          > > groups, and not from the mod8 ==1 group.
          > >
          > > n = p1^2 * p2^2 * p3 * 2^m The three primes involved must be
          from
          > > three different groups and not from the mod8 == 1 group.
          > >
          > >
          > > ****
          > >
          > >
          > > More observations, but I'll spare you :)
          > >
          > >
          > > Mark
        • Décio Luiz Gazzoni Filho
          ... Fermat has proven that all primes p == 1 mod 4 are uniquely represented as a sum of two squares, while primes p == 3 mod 4 have no such representation. p
          Message 4 of 6 , Apr 3, 2005
          • 0 Attachment
            On Sunday 03 April 2005 23:48, you wrote:
            > The prime 100999 is of the mod8=7 variety. So
            > x^2 + y^2 = 100999 should (and does) have no solution.

            Fermat has proven that all primes p == 1 mod 4 are uniquely represented as a
            sum of two squares, while primes p == 3 mod 4 have no such representation. p
            == 7 mod 8 is also == 3 mod 4.

            > x^2 + 2*y^2 = 100999 should (and does) have no solution.

            I believe this is related to the theory of imaginary quadratic fields (and in
            particular elliptic curves with complex multiplication, which I'm a little
            bit more familiar with, despite what David might rightly say after my
            blunders on the primeform list). Now, someone correct me if I'm wrong, but
            you can show that there's indeed only one solution, related to the
            decomposition of 100999 in the field Q(sqrt(-2)). You can use Cornacchia's
            algorithm to efficiently search for solutions or show that there are none.

            > x^2 - 2*y^2 = 100999 should (and does) have exactly one solution.

            Now this is out of my territory, but by symmetry I would risk the very
            uneducated guess that it is related to the theory of real quadratic fields.

            > Compare this to the composite number 100521.
            >
            > x^2 + y^2 = 100521 has 2 solutions.

            I believe this is related to the fact that 100521 can be factorized in two
            different ways (up to units, of course) in the ring of Gaussian integers
            Z[i]: 3^4*(4 - i)*(3 + 8i) and 3^4*(4 + i)*(3 + 8*i).

            > x^2 + 2*y^2 = 100521 has 10 solutions.

            Similarly, I believe this should be factorable in Q(sqrt(-2)) in 10 different
            ways up to units.

            > x^2 - 2*y^2 = 100521 has 2 solutions.

            Won't comment here, but I'm hoping the idea about real quadratic fields and
            its extension here is correct.

            Décio


            [Non-text portions of this message have been removed]
          • Dario Alpern
            ... Solutions of x^2 - 2*y^2 = 100999: x0=357, y0=115 Xn+1 = 3 Xn + 4 Yn Yn+1 = 2 Xn + 3 Yn so we can deduce: x1=1531, y1=1059 x2=8829, y2=6239 x3=51443,
            Message 5 of 6 , Apr 4, 2005
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "Mark Underwood"
              <mark.underwood@s...> wrote:
              >
              ...
              > x^2 - 2*y^2 = 100999 should (and does) have exactly one solution.
              >
              ...
              > Mark
              >

              Solutions of x^2 - 2*y^2 = 100999:

              x0=357, y0=115

              Xn+1 = 3 Xn + 4 Yn
              Yn+1 = 2 Xn + 3 Yn

              so we can deduce:

              x1=1531, y1=1059
              x2=8829, y2=6239
              x3=51443, y3=36375
              x4=299829, y4=212011
              x5=1747531, y5=1235691
              x6=10185357, y6=7202135
              x7=59364611, y7=41977119
              x8=346002309, y8=244660579
              x9=2016649243, y9=1425986355
              ....

              We can also negate x_n and/or y_n.

              You can find the solution using my Quadratic Diophantine Equation
              Solver at:

              http://www.alpertron.com.ar/QUAD.HTM

              Best regards,

              Dario Alpern
              Buenos Aires - Argentina
            • Mark Underwood
              Thank you Decio and Dario Decio I looked up Fermat s 4n+1 Theorem and it is as you say, and proved by Euler. (That is, every prime of the form 4n+1 can be
              Message 6 of 6 , Apr 4, 2005
              • 0 Attachment
                Thank you Decio and Dario

                Decio I looked up Fermat's "4n+1" Theorem and it is as you say, and
                proved by Euler. (That is, every prime of the form 4n+1 can be
                uniquely expressed as x^2 + y^2.) Thanks for the input on the other
                forms. I have a lot to learn.

                Dario, your data was great, thanks. Because of it I am going to
                investigate something further. I had only done solutions counts, not
                investigated the properties of the actual solutions before.

                Your data showed many solutions, and I said their was only one
                solution for p = x^2 -2*y^2 , p = 8m+7. What gives?

                Brings out another one of my mistakes! I had said that y<p/2, but
                what I meant to say was that y < p^2 /2. In such a case there is only
                one solution.

                I've book marked your very cool site BTW!

                Mark








                --- In primenumbers@yahoogroups.com, "Dario Alpern" <alpertron@h...>
                wrote:
                >
                > --- In primenumbers@yahoogroups.com, "Mark Underwood"
                > <mark.underwood@s...> wrote:
                > >
                > ...
                > > x^2 - 2*y^2 = 100999 should (and does) have exactly one solution.
                > >
                > ...
                > > Mark
                > >
                >
                > Solutions of x^2 - 2*y^2 = 100999:
                >
                > x0=357, y0=115
                >
                > Xn+1 = 3 Xn + 4 Yn
                > Yn+1 = 2 Xn + 3 Yn
                >
                > so we can deduce:
                >
                > x1=1531, y1=1059
                > x2=8829, y2=6239
                > x3=51443, y3=36375
                > x4=299829, y4=212011
                > x5=1747531, y5=1235691
                > x6=10185357, y6=7202135
                > x7=59364611, y7=41977119
                > x8=346002309, y8=244660579
                > x9=2016649243, y9=1425986355
                > ....
                >
                > We can also negate x_n and/or y_n.
                >
                > You can find the solution using my Quadratic Diophantine Equation
                > Solver at:
                >
                > http://www.alpertron.com.ar/QUAD.HTM
                >
                > Best regards,
                >
                > Dario Alpern
                > Buenos Aires - Argentina
              Your message has been successfully submitted and would be delivered to recipients shortly.