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

Expand Messages
• 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
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.

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

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
• 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
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.
>
> 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
>
• 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
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, ... 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
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
• 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
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, ... 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
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.