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

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

Expand Messages
  • 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 1 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 2 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 3 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 4 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.