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

sufficent proof for primes p:=x^2+x+1

Expand Messages
  • Bernhard Helmes
    A beautifull day, I have examine the prime numbers which lay on the polynom f(x)=x^2+x+1 My hypothese was : if 2^[(p-1)/3] = x or 2^[(p-1)/3] =x^2, then p is
    Message 1 of 6 , Mar 6, 2006
    • 0 Attachment
      A beautifull day,

      I have examine the prime numbers which lay on the polynom
      f(x)=x^2+x+1

      My hypothese was :
      if 2^[(p-1)/3] = x or 2^[(p-1)/3] =x^2,
      then p is a prime .
      The hypothes is not sufficent, because i found some counterexamples.
      But these counterexamples are all of the same form.
      They all have the form that x+1 is a potence of 2.

      [MuPad]
      x:=2;
      while TRUE do
      p:=x^2+x+1;
      if p mod 3 = 1 then
      erg:=powermod (2, (p-1)/3, p);
      if (erg=x or erg=x^2) and isprime (p)=FALSE then
      print (p, x+1, ifactor (x+1), erg, x);
      end_if;
      end_if;
      x:=x+1;
      end_while;


      6
      4033, 64, 2 , 63, 63


      8
      65281, 256, 2 , 255, 255


      12
      16773121, 4096, 2 , 4095, 4095


      16
      4294901761, 65536, 2 , 65535, 65535


      18
      68719214593, 262144, 2 , 262143, 262143


      20
      1099510579201, 1048576, 2 , 1048575, 1048575

      I am looking for a proof that the counterexamples only appears,
      if x+1 is like 2^n

      Some thougths could be helpfull:
      p:=x^2+x+1=x*(x+1)+1
      Remember i check out if 2^[(p-1)/3] is similar to x or x^2
      There are three possibilities:
      1. The (x+1)-root of 1 is 1 <=> 2^(p-1)/(x+1)=1 mod p
      2. The x-root of 1 is 1 <=> 2^(p-1)/x=1 mod p
      3. There is a f divisor of x and g divisor of x+1 with
      f*g>squareroot of p-1 so that 2^(p-1)/(f*g) = 1

      So far so good, but how can i proof that the 3. case only appears if
      x+1 is a power of 2.

      Would be nice from you if you have a clever idea and share it to me
      Nice greetings from the primes
      Bernhard
    • Mark Underwood
      Restated, Bernhard is proposing the following: Let y = x^2 + x + 1 if x == 2^[(y-1)/3] mod y or if x^2 == 2^[(y-1)/3] mod y then y is a prime or else x+1 is a
      Message 2 of 6 , Mar 8, 2006
      • 0 Attachment
        Restated, Bernhard is proposing the following:

        Let y = x^2 + x + 1

        if x == 2^[(y-1)/3] mod y
        or
        if x^2 == 2^[(y-1)/3] mod y

        then y is a prime or else x+1 is a power of two.


        *******

        If I may generalize:

        Let y = x^2 + x + 1

        Let p be any prime.

        if x == p^[(y-1)/3] mod y
        or
        if x^2 == p^[(y-1)/3] mod y

        then y is a prime or else:

        1)if x is even, x+1 has a factor(s) of p and perhaps other factors
        less than p.
        2)if x is odd, x has a factor(s) of p and perhaps other factors less
        than p.


        Or something like that. Oh the rigour of it all.

        Granted it is true, I leave it to more capable hands for a proof. :)
        (Or I may attempt one myself if I have time. )

        Mark





        --- In primenumbers@yahoogroups.com, "Bernhard Helmes" <bhelmes@...>
        wrote:
        >
        > A beautifull day,
        >
        > I have examine the prime numbers which lay on the polynom
        > f(x)=x^2+x+1
        >
        > My hypothese was :
        > if 2^[(p-1)/3] = x or 2^[(p-1)/3] =x^2,
        > then p is a prime .
        > The hypothes is not sufficent, because i found some counterexamples.
        > But these counterexamples are all of the same form.
        > They all have the form that x+1 is a potence of 2.
        >
        > [MuPad]
        > x:=2;
        > while TRUE do
        > p:=x^2+x+1;
        > if p mod 3 = 1 then
        > erg:=powermod (2, (p-1)/3, p);
        > if (erg=x or erg=x^2) and isprime (p)=FALSE then
        > print (p, x+1, ifactor (x+1), erg, x);
        > end_if;
        > end_if;
        > x:=x+1;
        > end_while;
        >
        >
        > 6
        > 4033, 64, 2 , 63, 63
        >
        >
        > 8
        > 65281, 256, 2 , 255, 255
        >
        >
        > 12
        > 16773121, 4096, 2 , 4095, 4095
        >
        >
        > 16
        > 4294901761, 65536, 2 , 65535, 65535
        >
        >
        > 18
        > 68719214593, 262144, 2 , 262143, 262143
        >
        >
        > 20
        > 1099510579201, 1048576, 2 , 1048575, 1048575
        >
        > I am looking for a proof that the counterexamples only appears,
        > if x+1 is like 2^n
        >
        > Some thougths could be helpfull:
        > p:=x^2+x+1=x*(x+1)+1
        > Remember i check out if 2^[(p-1)/3] is similar to x or x^2
        > There are three possibilities:
        > 1. The (x+1)-root of 1 is 1 <=> 2^(p-1)/(x+1)=1 mod p
        > 2. The x-root of 1 is 1 <=> 2^(p-1)/x=1 mod p
        > 3. There is a f divisor of x and g divisor of x+1 with
        > f*g>squareroot of p-1 so that 2^(p-1)/(f*g) = 1
        >
        > So far so good, but how can i proof that the 3. case only appears
        if
        > x+1 is a power of 2.
        >
        > Would be nice from you if you have a clever idea and share it to me
        > Nice greetings from the primes
        > Bernhard
        >
      • Mark Underwood
        Apparently Bernhard is having trouble posting to the group, so I will mention that a prime guru found a counterexample to Bernhard s proposal, namely ******
        Message 3 of 6 , Mar 10, 2006
        • 0 Attachment
          Apparently Bernhard is having trouble posting to the group, so I will
          mention that a prime guru found a counterexample to Bernhard's
          proposal, namely

          ******

          Let y = x^2 + x + 1

          if x == 2^[(y-1)/3] mod y
          or
          if x^2 == 2^[(y-1)/3] mod y

          then y is a prime or else x+1 is a power of two.

          *******

          The counterexample is x = 134217728: y is not a prime and x+1 is not
          a power of two. However it turns out that x itself is a power of two:
          x = 2^27 (!).

          So Bernhard's conjecture seems to be intact thus far if we allow x+1
          or x to be a power of two.

          I would like to investigate another generalization to this, but I
          keep getting stack overflows in my GP Pari on my antiquated computer.
          It's this:

          let p be a prime.

          let y = x^(p-1) + x^(p-2) + ... + x^2 + x + 1


          Here's the question: If

          2^((y-1)/p)) == x^k mod y

          for some k from 1 to p-1,

          is it true that y is either a prime or else x or x+1 is a power of
          two?


          Mark
        • Bernhard Helmes
          A beautifull day, ... I just calculate it for p=5 and p=7 and p=11, i have listed the numbers which are not primes, x, p, ifactor (x), ifactor (x+1): For p=5
          Message 4 of 6 , Mar 11, 2006
          • 0 Attachment
            A beautifull day,

            > It's this:
            >
            > let p be a prime.
            >
            > let y = x^(p-1) + x^(p-2) + ... + x^2 + x + 1
            >
            >
            > Here's the question: If
            >
            > 2^((y-1)/p)) == x^k mod y
            >
            > for some k from 1 to p-1,
            >
            > is it true that y is either a prime or else x or x+1 is a power of
            > two?

            I just calculate it for p=5 and p=7 and p=11,
            i have listed the numbers which are not primes, x, p, ifactor (x),
            ifactor (x+1):

            For p=5 there
            2
            4, 341, 2 , 5

            3 2
            8, 4681, 2 , 3

            5
            32, 1082401, 2 , 3 11

            9 3
            512, 68853957121, 2 , 3 19

            10 2
            1024, 1100586419201, 2 , 5 41

            15 2
            32768, 1152956690052710401, 2 , 3 11 331

            For p=7
            4
            16, 17895697, 2 , 17

            8
            256, 282578800148737, 2 , 257

            10 2
            1024, 1154048505100108801, 2 , 5 41

            14
            16384, 19343993777516776559493121, 2 , 5 29 113

            16
            65536, 79229371458530977775699951617, 2 , 65537


            and for p=11


            2, 2047, 2, 3

            2
            4, 1398101, 2 , 5

            3 2
            8, 1227133513, 2 , 3

            4
            16, 1172812402961, 2 , 17

            8
            256, 1213666705181745367548161, 2 , 257

            9 3
            512, 1240362622532514091484054017, 2 , 3 19

            11
            2048, 1298708349570020393652962442872833, 2 , 3 683

            16
            65536, 1461523938416389008123852738184089783721235906561, 2 ,
            65537

            Has anybody an idea how to prove the conjecture ?

            Nice Greetings from the primes
            Bernhard
          • Mark Underwood
            Thank you Bernhard for that data, way beyond what I could generate. So your generalized conjecture seems to be holding up thus far. I don t have the foggiest
            Message 5 of 6 , Mar 11, 2006
            • 0 Attachment
              Thank you Bernhard for that data, way beyond what I could generate.
              So your generalized conjecture seems to be holding up thus far. I
              don't have the foggiest idea about how one might go about proving
              such a thing.


              And there is at least one interesting subplot: why is it that when
              p=3 the composites are generated when x+1 is a power of two (with
              just one known exception), while when p=5,7,and 11 the composites are
              generated when x is a power of two? Mysteries never cease...


              Mark




              --- In primenumbers@yahoogroups.com, "Bernhard Helmes" <bhelmes@...>
              wrote:
              >
              (snip)
              > Has anybody an idea how to prove the conjecture ?
              >
              > Nice Greetings from the primes
              > Bernhard
              >
            • Bernhard Helmes
              A nice Sunday evening, ... generate. Perhaps you need some data more. I checked the primes p:=x^2+x+1 where x is a power of 2. x:=1; while TRUE do
              Message 6 of 6 , Mar 12, 2006
              • 0 Attachment
                A nice Sunday evening,

                > Thank you Bernhard for that data, way beyond what I could
                generate.

                Perhaps you need some data more. I checked the primes p:=x^2+x+1
                where x is a power of 2.

                x:=1;
                while TRUE do
                p:=(x+1)*x+1;
                if p mod 3 = 1 then
                erg:=powermod (2, (p-1)/3, p);
                res:=powermod (erg, 3, p);
                if res=1 and (erg=x or erg=x^2) and isprime (p)=FALSE then
                print (ifactor (x), p, ifactor (x+1));
                end_if;
                end_if;
                x:=x*2;
                end_while;


                27 4
                2 , 18014398643699713, 3 19 87211

                81
                2 , 5846006549323611672814741748716771307882079584257,

                5
                3 19 163 87211 135433 272010961

                171
                2 ,

                895897896871121684222976912227377711248658198893860113275530965754434
                39658\
                67181184471134228436276477953


                3 2
                , 3 19 571 174763 160465489 19177458387940268116349766612211

                243
                2 ,

                199791907220223502808422222706762643567910281130558153654986045416023
                79129\
                859977620592666523272986616017227171838989504031362210844729986994352
                9473


                6
                , 3 19 163 1459 87211 135433 139483 272010961
                10429407431911334611


                all of the examples are where x+1 is a power of 3 with > 3

                > And there is at least one interesting subplot: why is it that when
                > p=3 the composites are generated when x+1 is a power of two (with
                > just one known exception),

                I found 3 other exception 2^81, 2^171, 2^243 besides.
                The numbers get a little bigger. :-)

                Nice Greetings from the primes
                Bernhard
              Your message has been successfully submitted and would be delivered to recipients shortly.