20170730, 00:29  #1 
"Sam"
Nov 2016
2·163 Posts 
A second proof for the LucasLehmer Test
The LucasLehmer test is a test for Mersenne Numbers 2^n1.
2^n1 is prime if and only if 2^n1 divides S(4, n2). Here S(4, n) = S(4, n1)^22 starting with S(4, 0) = 4 now suppose we replace S(4, 0) = 4 with S(x, 0) = x. We get the following polynomial sequence S(x, 0) = x S(x, 1) = x^22 S(x, 2) = x^44*x^2+2 S(x, 3) = x^88*x^6+20*x^416*x^2+2 S(x, 4) = x^1616*x^14+104*x^12352*x^10+660*x^8672*x^6+336*x^464*x^22 ... Now we see that the discriminant D of S(x, n) = 2^r where r = (n+1)*2^n1 Since the exponent r is odd, each prime factor q dividing S(x, n) has the form k*2^(n+1)+1. Now assume 2^n1 divides S(4, n2). This shows that each prime factor of 2^n1 must have the form k*2^(n1)+1. Since k*2^(n1)+1 > sqrt(2^n1) is always true for k > 0, there is no prime factor less than or equal to sqrt(2^n1) with that form. By trial division test if c is composite, there exists a prime p < sqrt(c) that divides c. Therefore, 2^n1 must be prime. Please feel free to comment, suggest, improve or ask on this. Thanks!!! Last fiddled with by carpetpool on 20170730 at 00:31 
20170730, 00:44  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
19·491 Posts 

20170730, 09:21  #3  
"Robert Gerbicz"
Oct 2005
Hungary
10110100100_{2} Posts 
Quote:
This is very false, it fails even for n=3: 2 divides S(3), but you can't write 2 in the k*2^4+1 form. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
LucasLehmer test proof etc.  science_man_88  Miscellaneous Math  48  20100714 23:33 
proof the lucas lehmer test  kurtulmehtap  Math  13  20091002 12:12 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
LucasLehmer Test proof  alpertron  mersennewiki  16  20060318 07:23 