Lucas and Fibonacci primes

[Batalov]

There were 64 known prime Lucas numbers (including PRPs) and many of them are packed in clusters. Unexpectedly, there is a huge gap after the last previously known prime. (And similarly in Fibonacci primes, - observe the gap between 1968721 and 2904353, not quite as large but still 1.5x )

As agreed with R. and H.Lifschitz, I started the search at n>1800000, and found one more (though they reported that no primes were found in the substantial range between - where they searched since 2009). L(2316773) is a PRP after L(1051849). The size of the gap makes one suspect that something is amiss (there may be another prime). Or not!
...Makes one think - the same could happen to Mersennes. Like, you know, a jump from 74,207,281 to >150,000,000.

[paulunderwood]

Originally Posted by Batalov

L(2316773) is a PRP

? n=2316773;N=fibonacci(n+1)-fibonacci(n-1);write("Lucas_2316773",N)

time ../../coding/gwnum/lucasPRP Lucas_2316773
Lucas testing on x^2 - 3*x + 1 ...
Is Lucas PRP!

real	51m50.458s
user	148m41.324s
sys	5m29.136s

I guess GIMPS is more fastidious about their RES64. Did R&H keep theirs for you to compare with? -- I guess you all used OpenPFGW.

[Batalov]

Originally Posted by paulunderwood

-- I guess you all used OpenPFGW.

Yes. (That's the Achilles' heel of this project.)

They have their sieve, and I have my sieve, and with regards to sieving -- PFGW itself is doing quite a good job: you can sieve to ~49-50 bits just by doing the proper command-line:
pfgw64 -V -N -k -l -f200"{2p}" -q"L(p)"
where 200 is optional.

Don't know anything about residues, they probably do. I only had one email exchange with them with an answer to 'how far did they test'. Verifying residues is of course possible.

[sweety439]

Please see the thread http://mersenneforum.org/showthread.php?t=21814 for the n-Fibonacci primes and the n-step Fibonacci primes.

[paulunderwood]

Originally Posted by paulunderwood

? n=2316773;N=fibonacci(n+1)-fibonacci(n-1);write("Lucas_2316773",N)

This should be N=fibonacci(n+1)+fibonacci(n-1)

[Batalov]

Originally Posted by paulunderwood

This should be N=fibonacci(n+1)+fibonacci(n-1)

Wait, was the "-" form a "Is Lucas PRP!", too?!

[paulunderwood]

Originally Posted by Batalov

Wait, was the "-" form a "Is Lucas PRP!", too?!

Not likely! I think I screen-scraped the correct value and tested it, before using Pari/GP to write the file afresh with wrong value -- I am testing it now, but it was not Fermat 7-PRP

[paulunderwood]

Wow! The bad value is Lucas-PRP with respect to x^2-3*x+1.

I am now testing the good value, which is using x^2-5*x+1.

[paulunderwood]

../../coding/gwnum/lucasPRP Lucas_2316773 
Lucas testing on x^2 - 5*x + 1 ...
Is Lucas PRP!

I checked F(2316773) (for that is what it is) and it is not Fermat 2-PRP, but it is Lucas PRP w.r.t. x^2-3*x+1

[Dr Sardonicus]

Originally Posted by paulunderwood

I checked F(2316773) (for that is what it is) and it is not Fermat 2-PRP, but it is Lucas PRP w.r.t. x^2-3*x+1

There is a simple explanation for this. It is analogous to the fun fact that, if p is prime, then M_p = 2^p - 1 is a base-2 pseudoprime, whether M_p is prime or not.

In the present instance, the zeroes of the polynomial f = x^3 - 3*x + 1 are the squares of the zeroes of x^2 - x - 1. Consequently, if s = Mod(2*x - 3, f) [so that s is a square root of 5], then we may write

Mod(x, f)^n = Mod((L_2*n + F_2*n*s)/2, f).

Now, given a modulus N > 1, we see that Mod(x, f)^n == 1 (mod N) when L_2*n == 2 (mod N) and F_2*n == 0 (mod N).

Now let p be an odd prime number, and (5/p) = -1 (i.e. p == 3 or 7 (mod 10)). Then p remains prime in the ring R = Z[Mod(x, f)] (which is the maximal order of K = Q[Mod(x, f)]), and

r^p == r' (mod pR) for any r in R, where ' is conjugation in K/Q ["Frobenius automorphism"]. Consequently, we have

F_p+1 == 0 (mod pR) and L_p+1 == L₁ = 2 (mod pR), so that Mod(x, f)^p+1 == 1 (mod pR).

Now, we show that, if P = F_p, then Mod(x, f)^P+1 == 1 (mod PR), whether P is prime or not, regardless of whether (5/P) = 1 or -1.

We also have (again assuming (5/p) = -1) F_p == -1 (mod p). This means [since P = F_p] that

p|(P + 1), so that P|F_P+1. Therefore P|F_2*(P+1) also. Now, in order to show that

Mod(x, f)^P+1 == 1 (mod PR),

we only need to show that

L_2*(P+1) == 2 (mod P).

Since P+1 is even, we have

(L_(P+1))² - 5*(F_P+1)² = 4, so that

(L_(P+1))² == 4 (mod P). Again, since P+1 is even, we have

L_2*(P+1) = (L_(P+1))² - 2, whence

L_2*(P+1) == 2 (mod P),

and the proof is complete.

Remarks: I drew a blank on L_(P+1) (mod P), apart from its square being 4 (mod P). If P were prime, L_(P+1) would be == -2 (mod P). If it turned out to be anything other than 2 or -2 (mod P), it would immediately give a factorization of P.

One has (5/p) = (5/F_p) = -1 when p == 7, 13, 23, 37, 47, or 53 (mod 60); 2316773 == 53 (mod 60).