3 conjectures sur Mersenne-Fermat-Wagstaff . Prime de 100Euros

[inviteb0cf188d]

Bonjour,

J'ai posté sur le forum du projet GIMPS/Mersenne 3 conjectures en manque de preuve.
Elles concernent la preuve de primalité des nombres de Mersenne, Wagstaff et Fermat.

J'ai déjà fourni la première partie (la plus facile...) d'une preuve pour l'une d'entre elles.
Je donne des informations sur l'origine de ces conjectures et certaines propriétés.
Et j'ai fourni du code PARI/gp pour voir les conjectures à l'oeuvre.

Je donnerai 100Euro à la première personne qui fournira une preuve pour l'une de ces 3 conjectures !

Ces conjectures utilisent les propriétés d'un "Digraph under x^2-2 modulo a Mersenne, a Wagstaff or a Fermat prime" (voir Shallit&Vasiga), et elles utilisent des cycles de longueur q-1 (Mersenne et Wagstaff) ou 2^n-1 (Fermat).

L'idée (le rêve ?) finale est d'utiliser des cycles de longueur (q-1)/n (c'est-à-dire avoir des tests n fois plus rapides) pour prouver que de tels nombres ne sont pas premiers, dans le but d'accélérer la recherche de tels grands nombres premiers. À la limite, les propriétés trouvées pourraient aider à fournir de nouveaux tests probabilistes de primalité : "si l'on peut parcourir un cycle de longueur (q-1)/2 pour un nombre de Mersenne , alors il est très peu probable que ce soit un nombre premier".

(Venez voir aussi les 2 nouveaux nombres premiers gigantesques que le projet GIMPS vient de trouver, et que j'ai aidé à vérifier.)

Tony
-----

[invitee75a95d8]

Bonjour,

Je donnerai 100Euro à la première personne qui fournira une preuve pour l'une de ces 3 conjectures !

Hum, pas sûr que ça rentre dans le cadre de la charte... Et puis tu gagnes combien, toi, si quelqu'un trouve pour toi ? Parce que 100€, c'est pas cher payé si tu touches 10 fois plus...

[philname]

J'offre 50€ si quelqu'un me met en équation une partition de mozart !

[philname]

Sans rire, est-ce que l'on peut gagner de l'argent en trouvant une solution mathématique oubien scientifique, voir une idée scientifique brevetable ? Comment celà se passe-t-il ?

[A voir en vidéo sur Futura]

[inviteb0cf188d]

Bonjour,
Hum, pas sûr que ça rentre dans le cadre de la charte...

Et bien, si cela ne rentre pas dans la charte, on enlève la phrase. Pas de problème !

L'idée, bien sûr, est d'attirer les curieux pour diffuser ces conjectures et faire en sorte :
1) que des mathématiciens avec un bien meilleur bagage en Théorie des Nombres que moi s'y frottent ;
2) que cela intéresse des jeunes.
Erdos faisait cela ... (mais moi, je ne suis qu'un amateur !)

Et puis tu gagnes combien, toi, si quelqu'un trouve pour toi ? Parce que 100€, c'est pas cher payé si tu touches 10 fois plus...

Je ne gagne rien.
Si quelqu'un trouve une preuve, elle lui appartient et il lui faudra la publier dans une revue. Et la "gloire" (toute relative, soyons bien clair !) de la preuve lui appartiendra. À moi la "gloire" d'avoir investigué sur le sujet et d'avoir poussé d'autres gens à continuer. À la rigueur, mon nom devrait être associé aux théorèmes qui pourront être trouvés (et celui d'Anton Vrba pour les nombres de Wagstaff et de Fermat).

Pour moi, le maximum de mon (faible) niveau de Maths en Théorie des Nombres est presqu'atteint, et je n'ai que peu d'espoir de faire mieux. Mais, avec un peu de travail et peut-être un "point-de-vue" différent, d'autres pourront nous en apprendre un peu plus sur les propriétés de ces "Digraph".

Si une preuve est fournie pour la conjecture concernant les nombres de Wagstaff, alors ce sera le PREMIER test de primalité pour ce type de nombre. Une VRAIE première mathématique, montrant que le test LLT peut être utilisé pour d'autres nombres que les 2^q-1 (Lucas, Lehmer) , 2^2^n+1 (Lucas, Reix), k*2^n+/-1 (Riesel).
Alors, le créateur du projet GIMPS pourrait intégrer ce test dans son outil Prime95. Si un nombre premier de 100M de chiffres de ce type était trouvé, alors l'inventeur de la preuve serait récompensé, je pense (bon, quelques milliers de dollars, seulement).

Déjà, Robert Silverman (mathématicien qui a travaillé sur le code RSA et qui participe activement au projet GIMPS) est intéressé par la conjecture de preuve de primalité des nombres de Wagstaff.

L'enjeu, c'est que des mathématiciens continuent à travailler sur la preuve de primalité en s'intéressant à ces "Digraph". Chaque type de nombre a une "forme" de Digraph particulière. Ainsi, les nombres de Mersenne génèrent 1 arbre binaire et une multitude de cycles qui suivent des règles précises. Pour les nombres de Wagstaff, il n'y a pas d'arbre, que des cycles.
Je pense donc que l'étude de ces cycles (comme avaient commencé à le faire Shallit et Vasiga) peut amener à des découvertes très importantes (enfin, importantes pour les fadas, comme moi, qui s'intéressent aux nombres premiers !) sur les nombres premiers.

Donc, mon but est d'intéresser des gens sur ces sujets. J'ai posté sur déjà 4 ou 5 forums dans le monde.
On verra bien ...

En tout cas, c'est du sérieux : cela fait bien 10 ans que j'étudie les nombres de Mersenne, le LLT, et leurs propriétés, fouillant le Web à la recherche de nouvelles propriétés, et 5 ans que je contribue au GIMPS.

L'essentiel, c'est de s'amuser !!!!

Tony

[inviteb0cf188d]

Sans rire, est-ce que l'on peut gagner de l'argent en trouvant une solution mathématique

La réponse est NON, bien sûr !
Sauf cas particuliers, comme le donateur de l'EFF qui offre 150k$ au découvreur d'un nombre de 100M de chiffres (5 ans de calcul PAR nombre à vérifier avec un Core2 Duo à 3 GHz, quand même ! Et 15 jours de calcul environ en 2022) ou bien les malheureux 100Euros que je mets en jeu.

ou bien scientifique, voir une idée scientifique brevetable ?

Ca c'est autre chose.
Tony

[inviteb0cf188d]

Ah, et j'oubliais de parler de F33 : le 33ème nombre de Fermat, le plus petit de ce genre dont le statut (premier ou pas) n'est pas connu. 2,5 milliards de chiffres !!!
À mon avis, en 2025, avec l'une des plus grosses machines SMP disponibles à cette époque, il faudra entre 6 et 12 mois de calcul, au moyen du test de Pépin ou au moyen du test LLT, avec Mlucas ou Prime95, pour prouver qu'il est premier, ... ou pas.
Avec un test probabiliste utilisant un cycle (2^n-1)/m (avec m=7, 23 ou 89), on devrait aller bien plus vite pour conjecturer s'il est premier ou non.
Celui qui, le premier, aura pronostiqué son statut, verra son nom dans les livres d'histoire (de Mathématiques, s'entend !!).
Enfin, la vie est trop triste et trop sérieuse si l'on ne fait que des choses utiles !
Tony

[inviteb0cf188d]

J'ai résumé les conjectures dans ce papier.
Et voici un lien vers la version .pdf version du papier de Shallit&Vasiga.
Tony

[Médiat]

J'ai résumé les conjectures dans ce papier.

Bonjour,
Personnellement, je suis gêné par ton papier (et un autre que tu as posté sur le forum du projet GIMPS/Mersenne). Je ne suis pas un spécialiste de la théorie des nombres, il est donc fort probable que je ne comprenne pas certaines notations, mais pour un mathématicien standard, quand tu écris (exemple W₅) que


cela veut dire (pour un mathématicien standard, je répète) qu'il existe un entier k tel que

Ce qui est manifestement faux, en fait :

Une façon plus habituelle de le dire serait d'écrire (je prends le cas 3/2 systématiquement ; est-ce qu'il y a un critère pour choisir 3/2 ou 1/4, ou est-ce que les 2 marchent systématiquement ?) :

W_q étant impair, cela marche à tous les coups

Pour les Mersenne
S₀ doit être solution entière pour un k entier de :


Pour les Fermat

F_q étant impair et plus grand que 3, cela marche à tous les coups

[inviteb0cf188d]

Bonjour,

Je ne suis pas un spécialiste de la théorie des nombres, il est donc fort probable que je ne comprenne pas certaines notations, mais pour un mathématicien standard, quand tu écris (exemple W₅) que

C'est effectivement quelque chose que j'ai mis longtemps à comprendre et à accepter, avant que cela ne devienne naturel.
Alors, avant mon explication, je te suggère de taper : Mod(3/2,11) dans l'interpréteur PARI/gp, qui est un outil français pour faire des Maths. Sa réponse est : Mod(7,11).
Pourquoi ?
Simple : comme 11 est premier, cela signifie que tout nombre x tq possède un inverse pour la multiplication, que l'on note 1/x par facilité de notation : . Et l'inverse pour 2 est 6 : 2*6 = 11+1 . Et 3*6=18=11+7 . CQFD.
Donc, quand on prend un modulo avec un nombre premier, il est tout à fait licite d'utiliser des fractions, à condition de ne pas les transformer en vraie division ! Car on manipule bien ici des nombres entiers, et pas des éléments de Q. C'est juste une notation pratique pour noter l'inverse du nombre. Inverse que l'on peut calculer facilement pour un nombre premier, mais pas par une formule unique et simple en général.
Pour un nombre composite, tout est possible : pour un x donné, on peut avoir : 1) pas d'inverse, 2) un unique inverse, 3) plusieurs inverse. Donc la notation 1/x n'a pas de sens si le nombre pris comme modulo n'est pas premier.
Rassuré ?
Tony

[inviteb0cf188d]

je prends le cas 3/2 systématiquement ; est-ce qu'il y a un critère pour choisir 3/2 ou 1/4, ou est-ce que les 2 marchent systématiquement ?

Pour autant que nos expérimentations l'ont montré, les 2 "racines" (seeds) marchent de la même façon. Ce sont 2 racines fixes de un cyle modulo un nombre de Wagstaff. Il y en a peut-être d'autres ! En effet, pour le LLT pour les nombres de Mersenne, on n'a longtemps connu que 4 et 10 comme racines fixes. Puis a été découverte assez récemment une 3ème racine (dont je n'ai pas la valeur en tête, désolé) et qui, justement, est une fraction.
Tony

[Médiat]

comme 11 est premier

Merci de ta réponse, mais n'est-ce pas un peu gênant de faire comme si M_q était premier pour démontrer qu'il est premier ?

[inviteb0cf188d]

Je me permets d'insister sur l'importance de la 2ème conjecture.
Il y a là vraiment une opportunité de voir son nom apparaître dans les bouquins de Théorie des Nombres ! Sous la forme : Reix-Vrba-<Votre-Nom>.

Si une preuve est fournie pour la conjecture concernant les nombres de Wagstaff, alors ce sera le PREMIER test de primalité pour ce type de nombre. Une VRAIE première mathématique.

Enfin, un peu d'humilité.
N'oublions pas que :
1) Bien que le test dise OUI pour tous les nombres de Wagstaff premiers connus et NON pour tous les nombres de Wagstaff composites essayés (et nous sommes allés très haut !), il est toujours possible qu'il y ait un exception et donc que la conjecture soit fausse.
2) Le théorème d'incomplétude de Gödel est là pour nous rappeler qu'il existe des propositions vraies qui ne PEUVENT PAS être prouvées avec les outils dont nous disposons...
3) Cette découverte ne va pas bouleverser le cours de l'histoire ! Ni même révolutionner le petit monde de la Théorie des Nombres, dont les chercheurs ont des chats autrement plus importants à fouetter. Cela permet simplement de flatter son ego au moyen d'un peu de gloire (et peut-être de beaucoup de travail !).

Tony

[inviteb0cf188d]

Merci de ta réponse, mais n'est-ce pas un peu gênant de faire comme si M_q était premier pour démontrer qu'il est premier ?

Bonne remarque ! Mais cela n'avait pas empêché le thésard américain (au nom d'origine africaine bien compliqué à mémoriser...) qui a découvert le 3ème seed pour les Mersenne de le donner sous la forme d'une fraction, sachant pourtant qu'on peut l'employer pour prouver qu'un nombre est premier ... ou pas !
Enfin, comme tu le montres, il suffit de calculer le seed 3/2 comme (Wq+3)/2, et c'est réglé !!

Pour ceux qui veulent savoir comment sont nées les 3 conjectures (enfin, surtout les 2 dernières), voir ce thread du forum du GIMPS.

Tony

[inviteb0cf188d]

Hourra !!

Voici une première contribution ! qui fournit la partie facile (Enfin... relativement !) des conjectures 2 et 3.
Après une rapide lecture, il me semble qu'il y a des points à éclaircir encore, mais c'est prometteur !

Robert avait déjà fourni une autre preuve de mon théorème sur un test LLT pour les nombres de Fermat.

Lisez les preuves, elles sont intéressantes !!

Il reste donc à prouver les réciproques .........

Mais d'ores et déjà (enfin, s'il n'y a pas de "trou noir" dans la démonstration...), la conjecture 2 peut être utilisée comme test PRP pour les nombres de Wagstaff !!! Si un nombre de Wagstaff ne passe pas le test, alors il ne peut PAS être premier. S'il passe le test, alors il se peut bien qu'il soit premier, mais... on n'en a pas la preuve.

Bon début !

Au boulot !!

Tony

[leg]

Hourra !!

Tony

bonjour Tony

cela serait t'il possible d'avoir tes conjectures en francais car la traduction que j'ai, en anglais est très mauvaise. tu pourrais me l'envoyer par mail ou mp si c'est possible ,avec quelques premiers de Wagstaff que je ne connais pas du tout.
pour les nombres de Fermat si je comprend bien, tu penses (contrairement à l'idée génerale) aussi qu'il en existe d'autre premiers > 65537.

concernant les exposants P, qui donnent des Mq premiers , a t'on fait des constatations en fonction de l'exposant P qu'il soit de la forme de 3k + 1 ou 3k -1 ?
je t'enverrais le tableau avec quelques remarques..

surtout sur la décomposition de 3k, de l'exposant P car il y a peut être quelque chose a voir de ce côté .

3k se décompose toujours avec 3,et 2 et quelque fois 2,3 et 5 puis interviennent les Facteurs P congrus modulo 30 , il faudrait donc voir en fonction de cette décomposition de 3K comment les cycles interviennent ou le début de la racine fixe pour le LLT...

les nombres de Fermat premier > 17, eux sont de la forme 17 modulo 240..mais il faut les voir dans l'ensemble des entiers P[30] pour se rendre compte qu'il y en a probablement d'autres premiers....

moi je me contenterai d'une bonne bouf...

[leg]

je viens de regarder les premiers de Wagstaff il y a peut être quelque chose de curieux : y'en a t'il des premiers, avec un exposant P premier 29[30] soit:
29,59,89...149 . 179...etc ? c'est à dire est ce qu'il y en aurait un, qui passe le test et qui n'est pas premier...?

car aussi curieux que cela parait, pour les nombres de Mersenne il y a justement un autre cas "semblable" lorsque l'on décompose l'exposant P sous la forme 3k+1 pour P = 7.13.19.31 modulo 30, et une fois décomposé 3k avec 2,3 et quelque fois 5, le dernier facteur P[30] restant, n'est jamais un facteur p = 29 [30]..