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

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

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