- 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:>

if

> 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

> 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

> - 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 - A beautifull day,

> It's this:

I just calculate it for p=5 and p=7 and p=11,

>

> 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 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 - 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

> - 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

I found 3 other exception 2^81, 2^171, 2^243 besides.

> p=3 the composites are generated when x+1 is a power of two (with

> just one known exception),

The numbers get a little bigger. :-)

Nice Greetings from the primes

Bernhard