20211115, 20:47  #1 
Nov 2021
2×3 Posts 
(unproven) Potential new primality conjecture for Mersenne numbers
I would like to suggest this potential new Mersenne primality test for your review:
First some notations: x == y mod p is x congruent to y modulo p 2^x two to the power of x (xp) is the Legendre symbol Gaussian Integer Z[i]: e in Z[i], e = a + bi with a in Z and b in Z The Norme of e: N(e) = a^2 + b^2 mod p In this post p is a Mersenne number p = 2^q 1 with q odd > 2 Inverse of 2 mod p: 2^1 == 2^(q1) mod p Now the proposed test: Lemma: q a rational prime q > 2 p = 2^q  1 a mersenne number let a = (2^((q+1)/2) + 1) p is prime if and only if a^(2^(q1)) == a mod p Proof: Creutzburg and Tasche in Mathematic of Computation Vol 52 Num 185 Jan 1989 Proved the following: if p = 2^q  1 is a Mersenne prime it exist e in Z[i] such that e^(2^(q+1)) == 1 mod p i.e: e is a primitive (2^(q+1))th root of unity modulo p starting from e^(2^(q+1)) == 1 mod p The following square roots modulo p in Z[i] are: sqrt(1) == 1 mod p N(1) == N(1) == 1 mod p sqrt(1) == (+/)i mod p N(i) == 1 mod p then as q is odd sqrt(i) == (2^((q1)/2) + 2^((q1)/2)*i) mod p N(2^((q1)/2) + 2^((q1)/2)*i) == 1 mod p for the next square root lets write (r + m*i)^2 == (2^((q1)/2) + 2^((q1)/2)*i) with r and m in Z we have: r^2  m^2 == 2^((q1)/2) mod p (eq1) 2*r*m == 2^((q1)/2) mod p (eq2) N(r+m*i) = r^2 + m^2 == 1 mod p (eq3) eq1 + eq3: 2(r^2) == 2^((q1)/2) + 1 mod p r^2 == (2^(q1))*(2^((q1)/2) + 1) mod p r^2 == 2^(q1) + 2^((q3)/2) mod p factoring 2^((q3)/2) one get: r^2 == (2^((q3)/2))*(2^((q+1)/2) + 1) lets set t = 2^((q3)/2) r^2 == t*a and by Creutzburg and Tasche t*a is a quadratic residue modulo p and r exist. (t*ap) = 1 <=> (tp)*(ap) = 1 By Euler criterion: (tp) == t^((p1)/2) == t^(2^(q1)1) mod p (tp) == 2^(((q3)/2)*(2^(q1)1)) mod p reducing the exponent mod q: ((q3)/2)*(2^(q1)1) == ((q3)/2)*((2^q)/2  1) mod q 2^q = 2 mod q (q is a rational prime for p to be prime) ((q3)/2)*(2^(q1)1) == ((q3)/2)*(2/2  1) == 0 mod q Therefore (tp) == 2^0 == 1 mod p Again by Euler criterion: (ap) == a^(2^(q1)1) mod p (tp) == 1 mod p => a^(2^(q1)1) == 1 mod p iff p is prime By Wilson: (p1)! == 1 mod p iff p prime and (p1)! == 1*(ap)*(a^((p1)/2)) (a^(2^(q1)))*(a^1) == 1 mod p a^(2^(q1)) == a mod p In summary Creutzburg and Tasche give (ap) = 1 if p prime Wilson give (p1)! == 1 iff p prime combine with the Euler criteria giving a^((p1)/2) == 1 mod p we get p = 2^q  1 is a Mersenne Prime IFF a = (2^((q+1)/2) + 1), a^(2^(q1)) == a mod p Voila, ETL. Below is a Python3 program using gmpy2: Caveats it is my first non trivial Python program ... En passant: One can start squaring from t * a = 2^(q1) + 2^((q3)/2) instead of: a = 2^((q+1)/2) + 1 if the program is named mptest.py to start squaring from a, call: Bash> python3 mptest.py <q> && echo "Prime!"  echo "Not prime" or to start squaring from t*a, call: Bash> python3 mptest.py <q> && echo "Prime!"  echo "Not prime" q = 607 is the default value. Code:
import sys import gmpy2 from gmpy2 import mpz, xmpz def mptest(a,q,hb,lb): msb = xmpz(0) a[hb] = 1 a[lb] = 1 a[q:2*q] = 0 n = q  1 while n > 0: a[0:2*q] *= a[0:q] msb[0:q] = a[q:2*q] a[q]=0 a += msb a += a[q] a[q:2*q] = 0 n = 1 return a if len(sys.argv) > 1: q = int(sys.argv[1]) else: q = 607 if q < 0: q = q hb = q  1 lb = (q3) // 2 else: hb = (q+1) // 2 lb = 0 v = xmpz(0) x = mptest(v,q,hb,lb) if (x[hb]+x[lb]) == 2: x[hb] = 0 x[lb] = 0 if x == 0: print ("M",q," is prime") sys.exit (0) sys.exit(1) 
20211122, 20:19  #2 
Nov 2021
2·3 Posts 
Follow up
So, is the proof above correct? Is it something already known?
While I studied mathematics at the university way back then I did not study number theory. I am getting up to speed since last year as I have now plenty of time in my hands. This test has the same computing complexity as the Lucas Lehmer test and if it is valid, it gives an other venue for verification. For further clarification the r and m can be calculated as: r == ((2^q1) + 2^((q3)/2))^(2^(q2)) mod p as p == 3 mod 4. m == ((2^q1)  2^((q3)/2))^(2^(q2)) mod p let h = 2^(q1) and t = 2^((q3)/2) r == (h + t)^(h/2) mod p m == (h  t)^(h/2) mod p equation (2) was not used to calculate r or m. 2*r*m == 2^((q1)/2) mod p r*m == 2^(q1)*2^((q1)/2) == 2^((q3)/2) == t mod p replacing r and m by their values: ((h+t)*(ht))^(h/2) == (h^2t^2)^(h/2) == t mod p (h^2  t^2) = 2^(2*(q1))  2^(q3) == 2^(q2)  2^(q3) == 2^(q3) mod p then: r*m == (2^(q3))^(2^(q2)) mod p q being prime we get: 2^(q2) == 2^q * 2^2 == 2*2^2 == 2^1 mod q r*m == (2^(q3))^(1/2) == 2^((q3)/2) == t mod p. therefore r and m satisfy equation (2) without the requirement for p to be prime. However equation (1) and (3): (h+t)^{h }  (ht)^{h} == 2^{(q1)/2} mod p (h+t)^{h} + (ht)^{h} == 1 mod p are only true if p is prime (and the previous post proof correct ;). 
20211122, 20:42  #3  
"Robert Gerbicz"
Oct 2005
Hungary
3^{2}·5^{2}·7 Posts 
Quote:
For q=3 (p=7) your test fails, otherwise it is good up to at least q=1000. I don't know how it could be good with correct proof after q=3 (not checked the whole writing), as that is "only" a prp test for a given (changing with q) base. Really not a big deal, because we use a fixed base=3, and so far there is no known false hit. 

20211122, 21:15  #4  
Apr 2020
857 Posts 
This may be a valid PRP test (i.e. "p is prime" => "condition holds") for q > 3. But you haven't proved anything in the other direction, namely "condition holds" => "p is prime". Things break down around here:
Quote:
Wilson's theorem does indeed have an "iff". But "(p1)! == 1*(ap)*(a^((p1)/2)) mod p" is clearly invalid when p isn't prime, as the LHS is just 0. So you haven't actually used the "condition holds" => "p is prime" direction of Wilson. 

20211122, 21:15  #5  
Nov 2021
2×3 Posts 
Correction needed ...
Quote:
My bad, I should have specified q > 3. q=3 doesn't work because the test value is based on the existence of a primitive 2^(q+1) root of unit of a e in Z[i] and then going backward from unity. 2^{(q+1)} : 1 > 2^{(q)}: 1 > 2^{(q1)}: i > 2^{(q2)}: 2^{(q1)/2} + 2^{(q1)/2}*i > 2^{(q3)}: r+m*i and q=3 => e^{2^(q3)} == 1 ... I will amend the post based on your comment. Thanks. 

20211123, 08:38  #6  
Nov 2021
2·3 Posts 
Downgraded from lemma to conjecture
Quote:
OK, I see that the Wilson theorem alone doesn't bring the iff to the proof. However the premises from the Creutzburg and Tasche theorem guaranty the existence of the root of unity if and only if p prime. I thought that I had bracketed (ap) == 1 mod p from both the Euler criterion and the root of unity that force the existence of the square root of r^{2}. I guess I have to go back to the drawing board so to speak ... Thank you Charybdis for the review. Until I found a better proof, if any one want to chime in ... 

20211123, 10:16  #7  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2×5,059 Posts 
Quote:
Generally, roots of unity are tricky, i.e. always exist modulo n, but are unique (in pairs) only when n is prime. For example, modulo any prime, you only have two of them, which are 1 and 1, but modulo a composite you will have more. For example, modulo 2047 (which is 2^111=23*89) you have 4 roots: beside of 1 and 2046, the 622 and its negative also work: 622^2=1 (mod 2047). What you want to do is to find a 1selfridge test for primality. Such tests can't exist, for a simple reason, called Carmichael numbers. A test of the form: 1. Pick a base which is a function of n (the number to be factored), by however complicate or simple method or calculus. 2. If some power of b (mod n or a function of n) is equal to some constant, then n is prime. This will never work. Assume you want to prove primality of some n, then you use some "rule" to pick a base b, like "the larger prime smaller than the last 13 bits of n", then compute b^(n1) (mod n), and if this is 1, then n is prime. Regardless of the rule you use, when you will run into a Carmichael number (i.e. your n is such a number, or it has similar properties), you will get 1 for every base you chose, unless you run into a factor of n as a base. To avoid getting 1 for Carmichael numbers, (i.e. to make your test "work"), it would mean that you have already a "rule" to pick a base which is a factor of n, and in that case, you already have a method to factor n, you won't need a primality proof. Last fiddled with by LaurV on 20211123 at 10:24 

20211123, 15:03  #8  
"Robert Gerbicz"
Oct 2005
Hungary
3^{2}·5^{2}·7 Posts 
Quote:
You want to use theorem 6, then check it again, what they write, also see the definition of the root, and primitive root. You're very far from a proof, btw theorem 6 is quite trivial in Maths, for the previous corollary 4 you need that 3 is a primitive root mod 2^p1, what currently gimps is using base=3. (you need that 2^p1 is a Mersenne prime for corollary 4, so when we see a false hit in Gimps you can't apply that corollary because you can't even apply it for composite 2^p1 values). Quote:
In another ring there is such close type of theorem, that is exactly the Lucas Lehmer, an equivalent version: (2+sqrt(3))^(2^(p2))=k*sqrt(3) in Z[n,sqrt(3)] if and only if n=2^p1 is prime (for odd p prime). Last fiddled with by R. Gerbicz on 20211123 at 15:09 

20211129, 21:04  #9  
Nov 2021
6_{16} Posts 
Quote:
I got that, but this particular test target Mersenne numbers and Mersenne primes, which give us additional information about the number under test, after all as pointed out by R. Gerbicz, we already have the Lucas Lehmer test. By the way is there known Carmichael number(s) that are also Mersenne number(s)? Or could it be proven that it exist Mersenne numbers that are also Carmichael numbers? 

20211129, 21:15  #10 
Nov 2021
2·3 Posts 
Recap
To recap the discussion so far:
I have only proved that if p=2^{q}  1 is prime, q > 3 then for a = 2^{(q+1)/2} + 1 a^{2^(q1)} == a mod p Is it reasonable to make the following conjecture: for q > 3 a prime, p = 2^{q}  1 and a = 2^{(q+1)/2} + 1 if a^{2^(q1)} == a mod p then p is prime ? As an aside the thread title was changed to "unproven ... conjecture". That seems a tad redoundant ;) How about "A new conjecture about Mersenne Primes". Thank you all for indulging my sudden venture into the Mersenne numbers world. 
20211129, 21:38  #11  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9942_{10} Posts 
Quote:
Because it is 100200 years too late (as a string of letters). If there is not even shard of a proof or even a sketch, then what does it add? If there is, we are eager to hear it. Well, for sure, it will cause much less harm compared to walking into a brain surgery O.R. with a stunning announcement: "Step back, I have a sudden urge to try something  I have a totally novel idea! I've never done it, but I am sure I can do it." 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Potential primality of F33, F34, and F35  siegert81  FermatSearch  37  20180722 22:09 
14° Primality test and factorization of Lepore ( conjecture )  Alberico Lepore  Alberico Lepore  48  20171230 09:43 
Use Pepin's Tests for proving primality of Mersenne numbers ?  T.Rex  Math  12  20160403 22:27 
Conjectured Primality Test for Specific Class of Mersenne Numbers  primus  Miscellaneous Math  1  20141012 09:25 
conjecture about mersenne numbers  sascha77  Math  2  20100107 08:06 