## Mathématiques

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 $q-2$ steps for a Mersenne and $2^n-2$ 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 $x^2-2$ 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 $W_7 = (2^7+1)/3$. 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 $q-1$.
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 $S_j = S_{j-1}^2 - 2$ return to the seed $S_0$.
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: $\ \ (2^{4031399}+1)/3\ \$.

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 Reix $\ \ 2^q-1 = (8x)^2 - (3qy)^2 \ , \ q > 3 \ .$

Theorem LLT. (Lucas-Lehmer Test, for Mersennes) Let $M_q = 2^q-1$ with q odd prime. Then $M_q$ is prime if and only if $S_{q-2}$ vanishes modulo $M_q$, where $S_{q-2}$ is given by the recursion $S_j = S_{j-1}^2 - 2 \ ; \quad S_0 = 4$ .

Theorem LLRT. (Lucas-Lehmer-Reix Test, for Fermats) Let $F_n = 2^{2^n}+1$ . Then $F_n$ is prime if and only if $S_{2^n-2}$ vanishes modulo $F_n$, where $S_{2^n-2}$ is given by the recursion $S_j = S_{j-1}^2 - 2 \ ; \quad S_0 = 5$.

Conjecture LLTm. (modified Lucas-Lehmer Test, for Mersennes, based on a cycle) Let $M_q = 2^q-1$ with q odd prime. Then $M_q$ is prime if and only if $S_{q-1} \equiv S_{0} \ \mod{M_q}$ and if there is no integer $0 < i < q - 1$ for which $S_i \equiv S_0 \ \mod{M_q}$, where $S_{q-1}$ is given by the recursion $S_j = S_{j-1}^2 - 2 \ ; \quad S_0 = 3^2+1/3^2$ .

Conjecture LLTFm. (modified Lucas-Lehmer-Reix Test, for Fermats, based on a cycle) Let $F_n = 2^{2^n}+1$ . Then $F_n$ is prime if and only if $S_{2^n-1} \equiv F_n$ and if there is no integer $0 < i < 2^n - 1$ for which $S_i \equiv S_0 \ \mod{F_n}$, where $S_{2^n-1}$ is given by the recursion $S_j = S_{j-1}^2 - 2 \ ; \quad S_0 = 1/4$.

Conjecture LLTWm. (modified Lucas-Lehmer Test, for Wagstaffs, based on a cycle) Let $N_q = 2^q+1 \ , W_q = N_q/3$ with q odd prime. Then $W_q$ is prime if and only if $S_{q-1} \equiv S_{0} \ \mod{W_q}$ and if there is no integer $0 < i < q - 1$ for which $S_i \equiv S_0 \ \mod{N_q}$, where $S_{q-1}$ is given by the recursion $S_j = S_{j-1}^2 - 2 \ \mod{N_q}; \quad S_0 = 1/4$ .

Publicités

### 6 Réponses to “Mathématiques”

1. free math worksheets Says:

Thanks for sharing großen Artikel.

2. Two new Wagstaff PRPs ! | Tony's Blog Says:

[…] Il n’y a plus qu’à attendre que quelqu’un, enfin !, fournisse une preuve de ma conjecture Vrba-Reix sur le test de primalité des nombres de Wagstaff au moyen d’un test LLT. Un jour, peut-être… Pour info, je donne 200€ à qui fournit la preuve de la réciproque (j’avais déjà fait le plus facile ! "si le nombre est premier, alors il vérifie la propriété"). Voir mes Maths. […]

3. lefeu Says:

bonjour Tony, est-ce que tu travailles toujours sur les nombre de Mersenne, sur les tests de ces nombres ?

4. francois Says:

Nous avons développé une théorie qui pourra peut-être vous aider pour votre conjecture. Vous trouverez cette théorie sur les nombres impairs sur notre site mathscience.tsoftemail.fr. N’hésitez pas à nous contacter si vous avez des questions.

• trex58 Says:

http://mathscience.tsoftemail.fr/index.awp
Plus de 400 pages. Gros travail. Il me faut l’imprimer pour pouvoir le lire tranquillement. Et il me faudra un peu de temps pour comprendre les démonstrations et explications (à supposer que j’en aie les compétences). Mais, pour le moment, j’ai plutôt prévu demain une rando en montagne ! 😉 Et ma fille est en France cette semaine. Donc, cela devra attendre quelques jours.