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 .

* Summary of the 3 Conjectures

* Lifchitz’s paper about the first PRP test for Wagstaffs
* Shallit & Vasiga : Digraph under x^2 or x^2-2 modulo a Mersenne or Fermat prime
* Cycles under x^2-2 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)

* (small) conjecture about the order of 3 modulo a Mersenne prime

* My (DRAFT, not complete and maybe garbage) paper where I try to build a proof for the first conjecture (Mersenne numbers)

* Paulo Ribenboim: « The Little Book of Bigger Primes » Section 2: How to Recognize Whether a Natural Number is a Prime (Free by Springer)

Mersenne prime

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.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s


%d blogueurs aiment cette page :