20170611, 09:40  #1 
"Serge"
Mar 2008
San Diego, Calif.
101×103 Posts 
Lucas and Fibonacci primes
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. 
20170611, 11:11  #2 
Sep 2002
Database er0rr
4811_{10} Posts 
Code:
? n=2316773;N=fibonacci(n+1)fibonacci(n1);write("Lucas_2316773",N) Code:
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 
20170611, 17:24  #3 
"Serge"
Mar 2008
San Diego, Calif.
24243_{8} Posts 
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 ~4950 bits just by doing the proper commandline: 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. 
20170612, 18:50  #4 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
E81_{16} Posts 
Please see the thread http://mersenneforum.org/showthread.php?t=21814 for the nFibonacci primes and the nstep Fibonacci primes.
Last fiddled with by sweety439 on 20170612 at 18:51 
20170620, 08:36  #5 
Sep 2002
Database er0rr
12CB_{16} Posts 

20170620, 14:31  #6 
"Serge"
Mar 2008
San Diego, Calif.
101·103 Posts 

20170620, 14:33  #7 
Sep 2002
Database er0rr
12CB_{16} Posts 
Not likely! I think I screenscraped 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 7PRP
Last fiddled with by paulunderwood on 20170620 at 14:53 
20170620, 15:38  #8 
Sep 2002
Database er0rr
17·283 Posts 
Wow! The bad value is LucasPRP with respect to x^23*x+1.
I am now testing the good value, which is using x^25*x+1. 
20170620, 16:55  #9 
Sep 2002
Database er0rr
17×283 Posts 
Code:
../../coding/gwnum/lucasPRP Lucas_2316773 Lucas testing on x^2  5*x + 1 ... Is Lucas PRP! 
20170628, 16:56  #10  
Feb 2017
Nowhere
3·7·311 Posts 
Quote:
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_{1} = 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 PF_{P+1}. Therefore PF_{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)})^{2}  5*(F_{P+1})^{2} = 4, so that (L_{(P+1)})^{2} == 4 (mod P). Again, since P+1 is even, we have L_{2*(P+1)} = (L_{(P+1)})^{2}  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). Last fiddled with by Dr Sardonicus on 20170628 at 16:57 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
LucasLehmer Primes  henryzz  And now for something completely different  42  20190603 14:09 
Primes in nfibonacci sequence and nstep fibonacci sequence  sweety439  sweety439  17  20170613 03:49 
SmarandacheFibonacci Primes  rogue  And now for something completely different  5  20160718 14:33 
Fibonacci and Lucas factors  Raman  Math  40  20100719 03:30 
Factoring Fibonacci/Lucas numbers  geoff  Factoring  13  20051223 01:59 