These Maths deal with Mersenne, Wagstaff and Fermat numbers, and with primality tests for these numbers.
About Mersennes, the « Lucas-Lehmer Test for Mersenne numbers » (LLT in short) is the most efficient primality test ever built for any number.
About Fermats, the Pépin test is usually used ; however I’ve produced a primality test for Fermats that makes use of a LLT with 5 as seed, and I’ve recently discovered that Kustaa Inkeri provided in 1960 a proof of such a LLT with 8 as seed.
About Wagstaff numbers, no efficient primality test is known yet. However, there exist tests that can show that a Wagstaff number is a PRP (Probable Prime), or not.
Using the LLT means that we travel from a seed (4 for Mersennes ; 5 for Fermats) to 0 after steps for a Mersenne and steps for a Fermat. There are many possible seeds that can be used ; but only a small number of fixed (independent of q or n) seeds are known. All the possible seeds and the intermediate values that are crossed build a Tree (2 branches lead to 1). The complete graph is called a DiGraph under modulo a prime number (see Shallit & Vasiga work). Such a DiGraph is made of Trees and Cycles. Look at the DiGraph (figure by A. Vrba) of . Often, small trees are attached to cycles.
About Mersenne and Fermat numbers, the DiGraph is made of one unique big Tree and of many Cycles, with length dividing .
About Wagstaff numbers, there are only Cycles ; so the LLT does not work here. For a Wagstaff number, it could be possible of « proving » (once the conjecture is proven…) that it is a prime only thanks to a Cycle (this is called a modified LLT) : instead of reaching 0 after a number of steps, the iterations return to the seed .
I also guess that using Cycles instead of the Tree could speed up the proof that a Mersenne or a Fermat number is NOT prime. About Fermat numbers, it could help to know the status of F33 faster.
However, one must first build a proof that using a Cycle of the DiGraph CAN be used as a primality test, and not only as PRP test. So Mathematicians are invited to study these conjectures : the one that will be able to prove the Wagstaff primality test conjectured by Anton Vrba (called LLTWm here below) will have his name in Number Theory books, because it will be the first efficient primality test for a number N such that N-1 and N+1 cannot be factorized easily (like Mersennes and Fermats). I suggest to start proving my Conjecture about Mersenne numbers (called LLTm).
Jean Penné has implemented the Vrba-Reix PRP test for Wagstaff numbers in the 3.7.2 version and now 3.8.0 version of the LLR (Lucas-Lehmer-Rieseil) tool.
With that tool, and as a member of a project named DUR (Diepeeven-Underwood-Reix), I’ve discovered the 3rd biggest PRP ever found: .
For the first part of each of the three conjectures a proof has been built (see below).
I’ve published the DRAFT work I’ve done for trying to build a proof for the second part of the conjecture for Mersennes. The method I tried to use deals with the period of a Lucas Sequences modulo a Mersenne prime or composite.
Oh, I forgot to say: I’ll give 100 euros to the first guy/lady who provides a proof for one of the 3 conjectures.
Theorem LLT. (Lucas-Lehmer Test, for Mersennes) Let with q odd prime. Then is prime if and only if vanishes modulo , where is given by the recursion .
Theorem LLRT. (Lucas-Lehmer-Reix Test, for Fermats) Let . Then is prime if and only if vanishes modulo , where is given by the recursion .
Conjecture LLTm. (modified Lucas-Lehmer Test, for Mersennes, based on a cycle) Let with q odd prime. Then is prime if and only if and if there is no integer for which , where is given by the recursion .
Conjecture LLTFm. (modified Lucas-Lehmer-Reix Test, for Fermats, based on a cycle) Let . Then is prime if and only if and if there is no integer for which , where is given by the recursion .
Conjecture LLTWm. (modified Lucas-Lehmer Test, for Wagstaffs, based on a cycle) Let with q odd prime. Then is prime if and only if and if there is no integer for which , where is given by the recursion .
* Lifchitz’s paper about the first PRP test for Wagstaffs
* Shallit & Vasiga : Digraph under or modulo a Mersenne or Fermat prime
* Cycles under modulo a Mersenne
* Proof of the LLRT for Fermats (Revision for Inkeri)
* Another proof of the LLRT for Fermats by R. Gerbicz
* Proof of first part of Conjecture LLTm
* Proof of first part of Conjectures LLTFm and LLTWm (for Fermats and Wagstaffs, by Robert Gerbicz)
* Proof of first part of Conjectures LLTWm (for Wagstaffs, by Anton Vrba)