math_equations_300pxLes mathématiciens adorent les nombres premiers ! Non seulement ils sont à la base de problèmes simples mais encore non-résolus, comme la conjecture de Goldbach dont je parlais ici (tout nombre pair serait la somme de deux nombres premiers), mais les nombres premiers s’avèrent également très utiles dans la vie réelle, comme avec l’algorithme de cryptage RSA qui sert à protéger un grand nombre de nos secrets informatiques ou bancaires (sujet d’un autre billet).

Pour ces raisons, les mathématiciens adoreraient disposer d’une machine à fabriquer des nombres premiers, ou tout du moins d’une formule qui permette d’en construire à volonté.

Des formules à fabriquer des nombres premiers

Imaginons que vous vouliez en construire une telle formule. En observant que les plus petits nombres impairs sont premiers (3,5,7), on pourrait proposer de regarder tous les nombres de la forme \(2 n+1\). Évidemment, ça marche pour n=1,2 ou 3, mais pour n=4 on obtient 9 qui n’est pas premier, ça marche à nouveau avec n=5,6,8 et ensuite de moins en moins !

220px-MarinMersenneUne formule beaucoup plus efficace a été suggérée par Euler, il s’agit de

\(n^2-n+41\).

Il se trouve que pour toute valeur de n entre 0 et 40, cette formule donne un nombre premier ! Mais ensuite, ça ne marche presque plus. Or pour la cryptographie notamment, on aimerait pouvoir fabriquer des grands nombres premiers.

Au XVIIeme siècle, le moine français Marin Mersenne a proposé une autre formule à fabriquer des nombres premiers : prendre \(2^p-1\) quand \(p\) est déjà lui même un nombre premier. On note ce nombre \(M_p\) en hommage à Mersenne.

Pour les premières valeurs de p (2,3,5,7), ça marche nickel puisqu’on obtient 3,7,31 et 127 qui sont tous premiers. Mais pour p=11, ça ne colle pas car \(2^{11}-1=2047\), lequel se décompose en 23×89. Puis ça marche à nouveau pour p=13,17,19. Ensuite ça marche beaucoup moins bien.

Pour une raison totalement inconnue, Mersenne avait conjecturé que sa formule devait donner des nombres premiers pour p=31, 67, 127 et 257. Personne ne sait pourquoi il avait proposé ceux-là en particulier, d’autant que les nombres de Mersenne correspondants possèdent un très grand nombre de chiffres, et qu’il lui était clairement impossible de faire la vérification à la main.

Le nombre de Mersenne M67

Beaucoup de mathématiciens se sont ensuite acharnés à démontrer que ces nombres de Mersenne étaient effectivement premiers … ou pas. L’une des démonstrations les plus fameuses a concerné le nombre M67, et fut l’occasion d’une conférence mythique à l’American Mathematical Society en 1903. Un dénommé Franck Cole avait annoncé un exposé portant le titre ambitieux « On the factorization of large numbers ».

Au moment de son exposé, Franck Cole s’est levé, s’est dirigé au tableau sans dire un mot, et a pris la craie pour calculer à la main le nombre M67, qui vaut

\(2^{67}-1 = 147\ 573\ 952\ 589\ 676\ 412\ 927 \)

Sur l’autre moitié du tableau, il a ensuite posé la multiplication 761 838 257 287 x 193 707 721. Puis toujours en silence, il a patiemment effectué à la main le calcul, pour obtenir le résultat…147 573 952 589 676 412 927 !

Sans avoir prononcé un seul mot, il est retourné s’asseoir sous les ovations du public. M67 n’était donc pas premier ! Cole a par la suite déclaré que cette « démonstration » lui avait demandé 3 ans de travail tous les dimanches !

La recherche sur les nombres de Mersenne est encore très active, puisque c’est par ce moyen que les records de plus grands nombres premiers sont battus depuis pas mal d’années. En ce moment le tenant du titre est \(2^{57\ 885\ 161} -1\). Je suis gentil, je ne vous l’écrit pas pour ne pas vous affoler, il faudrait 17 millions de chiffres !


Pour aller plus loin : les formules à fabriquer des nombres premiers

On manque cruellement aujourd’hui d’une formule efficace pour fabriquer des nombres premiers. On peut en fait démontrer que tout expression polynomiale (du genre \(n^2-n+41\)) finit nécessairement par échouer. Aucune expression de ce type ne peut donner pour tout n un nombre premier.

Il existe une formule amusante qui donne systématiquement des nombres premiers, il s’agit de l’expression

\(E[A^{3^n}]\)

où \(E[.]\) désigne la fonction « partie entière », et A est une constante réelle, appelée constante de Mills. Le problème est que cette formule est impraticable car il faudrait connaître avec une précision infinie la constante A, ce qui n’est pas le cas ! On sait juste qu’elle existe, et on arrive à calculer sa valeur approchée, environ 1.3063778838.

Plus ambitieux serait de trouver une formule qui donne TOUS les nombres premiers sans exception. Évidemment on ne connait pas une telle formule, je ne sais même pas s’il est possible qu’une telle formule existe (en utilisant que les opérations algébriques usuelles). Quelqu’un a une idée ?

Comments

  1. Dommage qu’il manque la définition d’un nombre premier, du coup j’ai rien bité à l’article.

    • Un nombre premier est un nombre qui ne se divise que par lui-même et par 1. Toutefois, le chiffre 1 n’est pas considéré comme premier.

  2. J’ai appliqué la formule que tu as donnée à la fin et je vois maintenant pourquoi tu nous dis qu’il faudrait une précision infinie: déjà à n=3 la réponse que j’ai obtenue était 1360 au lieu de 1361!

    En tout cas merci pour l’excellent article (comme d’habitude d’ailleurs)!

  3. Je ne suis pas un spécialiste en formule. Mais y a t-il quelqu’un qui pourrait expliquer pourquoi le premier des nombre c’est à dire le « UN » ou « 1 » n’est pas comptabilisé comme nombre premier ?
    Car dans ce cas sur les 100 premiers nombres premiers, on en touverait 13×2 donc 26 et sur les 1000 premiers 13² donc 169.

    • C’est par définition, en fait. Un nombre premier n’est divisible que par 1 ET par lui-même (le « et » est important). Le fait est que le nombre 1 n’a qu’un seul diviseur entier positif !

      • En fait ça n’est pas tout à fait ça. La raison pour laquelle le 1 n’est pas premier vient du théorème fondamentale de l’arithmétique : Tout nombre strictement positif s’écrit comme multiplication de nombre premier d’une unique façon (à l’ordre prêt des facteurs).
        En gros 6 = 3*2.
        Aucun autre nombre premier ne peut être ajouté à cette liste.
        Si on considère le 1 comme premier, alors on aura 6 = 3*2 = 3*2*1 = 3*2*1*1 …
        L’unicité est perdu.

  4. bonjour à tous
    vous voulez connaitre le secret de la répartition des nombres premier, les formules qui vont avec, pour les engendrer, rien de plus simple, il y a un site qui donne toutes ses explication
    sites.google.com/site/loqiquedespremiers/

  5. En fait on sait générer en quelques pouillèmes de seconde des nombres premiers assez grands pour toutes les utilisations pratiques, en cryptographie notamment. Par exemple je viens de fabriquer pour vous 13346982990572324928326926758139614080597943244852535646331226431761461452713219353362212640662705553310641829928957612157060927685155337851918051234721459 (1024 bits en biniare) avec http://www.mobilefish.com/services/rsa_key_generation/rsa_key_generation.php.

    Sur http://www.drgoulu.com/2012/04/15/comment-produire-des-nombres-premiers/ j’explique l’histoire des tests de primalité, en particulier le fait que les tests de primalité probabilistes sont tellement extraordinairement fiables qu’ils sont plus surs qu’un tests de primalité déterministe par factorisation.

    Les nombres de Mersenne ne sont pas utiles en pratique, mais intéressants parce que:

    1) il existe un test de primalité déterministe rapide qui ne fonctionne que pour eux
    2) Mersenne n’a trouvé aucun nombre de Mersenne !
    3) leur représentation en binaire est très simple : 2^x-1 est formé de x fois le chiffre « 1 », donc on devrait plutôt les appeler « repunits premiers »

    et pour @Madgel Djahir : les nombres premiers sont tellements spéciaux qu’ils sont premiers dans toutes les bases, ce qui fait que toute tentative de les étudier en utilisant la base 10 est vouée à l’échec, et donc il n’existe pas de « formule pour les engendrer ». Et comme toutes les bases sont des bases 10 (http://www.drgoulu.com/2011/09/25/comment-comptent-les-extraterrestres/ ), le seul espoir est de les étudier indépendamment de toute base. Bonne chance !

    • « les nombres premiers sont tellement spéciaux qu’ils sont premiers dans toutes les bases, ce qui fait que toute tentative de les étudier en utilisant la base 10 est vouée à l’échec, et donc il n’existe pas de « formule pour les engendrer ». »

      Je n’ai pas compris l’argument. Peux-tu détailler ? (Je comprend bien que la notion de nombre premier est indépendante du choix d’une base pour les représenter, c’est la suite que je ne comprend pas. Par exemple, être multiple de 10 est également une propriété indépendante du choix d’une base. Pourtant, en base 10, on les voit assez bien :)).

  6. Pingback: Les nombres de Mersenne | C@fé des Scien...

    • Ah super, je ne connaissais pas cet exemple ! Donc on peut engendrer tous les nombres premiers avec de tels polynomes !
      (pour ceux qui n’iraient pas voir la page wiki, un exemple d’un tel polynome est donné, mais il a 26 variables !)

      (k+2)[1 – (wz+h+j–q)2 – [(gk+2g+k+1)(h+j) + h – z]2– (2n+p+q+z–e)2 – [16(k+1)3(k+2)(n+1)2 + 1 – f2]2– [e3(e+2)(a+1)2 + 1 – o2]2 – [(a2–1)y2 + 1 –x2]2– [16r2y4(a2–1) + 1 – u2]2
      – [((a+u2(u2–a))2–1)(n+4dy)2 + 1 – (x+cu)2]2 –[n+l+v–y]2– [(a2–1)l2 + 1 – m2]2 – [ai+k+1–l–i]2 – [p + l(a–n–1) + b(2an+2a–n2–2n–2) – m]2 – [q+ y(a–p–1) + s(2ap + 2a – p2 – 2p – 2) – x]2
      – [z + pl(a–p) + t(2ap – p2 – 1) – pm]2]

      • « Un » est un nombre premier. il est le « premier » des nombres premiers, comme de 2 est le second nombre premier, ou encore le 89 le 25ème nombre premier, ou encore le 91 le 26ème et aussi le 107 le 29ème. Celui qui comprendra que tous les nombres premiers sont intimement et inséparablement couplés avec leur numéro de placement, comprendra peut-être les secrets de l’existence. Le défi est lancé car rien n’est du au hasard et leur rapport entre eux apporte une richesse merveilleuse d’informations méconnues de toutes les académies les plus renommées.

      • J’ai pas tout de suite capté le piège. Je me suis lancé comme un débutant dans l’écriture d’une fonction Python qui calcule ce polynôme, en me disant qu’il n’y avait plus qu’à essayer des valeurs de a,b,c…z aléatoires pour produire quelques nombres premiers. C’est pas du tout ça.

        En regardant l’équation, on voit qu’il a la forme (k+2) [ 1 – plusieurs expressions au carré] La seule façon d’obtenir un nombre positif avec ça, c’est que toutes ces expressions soient nulles, et dans ce cas k+2 est un nombre premier. Les expressions qui doivent être simultanément nulles, dormant donc un système d’équations diophantiennes / http://fr.wikipedia.org/wiki/%C3%89quation_diophantienne ) sont plus clairement visibles sur l’article anglophone de la wikipédia http://en.wikipedia.org/wiki/Formula_for_primes#Formula_based_on_a_system_of_Diophantine_equations .

        Si j’ai bien compris http://primes.utm.edu/glossary/xpage/MatijasevicPoly.html , on ne connait actuellement aucune solution de ce système, donc aucun ensemble se paramètres a,b,c…z ayant produit le moindre nombre premier par cette formule, qui est pourtant démontrée comme les produisant tous !

    • Il ne faut pas s’emballer : cette formule, c’est quand même un peu l’arnaque. Ok, les valeurs positives de ce polynôme sont exactement les nombres premiers (et chaque nombre premier n’apparaît qu’une fois), sauf qu’en fait on obtient des valeurs négatives pour quasiment tous les choix de variables… et qu’il n’est pas du tout évident de trouver des valeurs des variables qui vont effectivement donner un résultat positif. Ce n’est pas surprenant puisque ce polynôme « code » en quelque sorte un algorithme de dénombrement des nombres premiers.

      J’avais lu une anecdote à ce sujet, dans Quadrature je crois, mais je n’ai pas retrouvé la source ; je raconte de mémoire. Un mathématicien vient de prendre connaissance de cette formule et des résultats correspondants sur le dixième problème de Hilbert, et il en parle à son collègue, un autre spécialiste du domaine :
      – « On a découvert un polynôme qui prend comme valeur positive exactement l’ensemble des nombres premiers. »
      – « C’est extraordinaire ! Ca va nous apprendre énormément de choses sur les nombres premiers ! »
      – « En fait, on peut trouver un tel polynôme pour tout ensemble récursivement énumérable. »
      – « C’est horrible ! Ca ne va rien nous apprendre du tout sur les nombres premiers ! »
      Voilà.

      • désolé, dans mon enthousiasme je n’avais pas vu ton commentaire, mais c’est exactement ça : horrible.

      • C’est effectivement cela. La formule n’est pas pratique (voir même inutile). Pour la source, c’est le mathématicien russe Youri V.Linnik qui est d’ailleurs au cœur de l’anecdote décrite par Groug.

  7. Pingback: Les nombres de Mersenne | Panorama des Math&eac...

  8. La répartition des nombres premiers est résolu, il n’y a plus de secret, c’est une histoire de logique
    PYTHAGORE et Sophie GERMAIN avait entrouvert une partie de la solution à la répartition des nombres premiers
    Pythagore nous avait laissé 4n+1
    Sophie Germain à quand à elle laissé 2p+1
    moi je vous laisse un petit mélange des deux, avec en prime les multiples des nombres premiers:
    4 + 1 = P + 2 = P2 + 4 = P3 + 2 = P4 etc…+4= P +2= P
    4 x + 2 x + 1 = P ou Mp

  9. 1+4+2 ou 1 + 4x + 2y ou 1 + 4x + 2x

    exemple:

    nombre de Mersenne : M7= 2p7 – 1 = 127 =1 + 4x + 2X = 1+ (4 x21) +(2×21)

    nombre de Fermat : f3=2p8 + 1 = 257 =1 + 4x + 2y = 1 +(4×43) + (2×42)

    nombre de fibonacci : f13 = 233=4x +2y+1 = 1 +(4×39) + (2×38)

  10. DROUHET Julien Reply

    Il me semble que c’est possible d’obtenir n’importe quel nombre premier à partie d’une formule. Même si je n’ai pas tout compris dans sa formulation, l’hypothèse de Riemann le suggère, non ? 🙂

    • Non, il n’y a pas de formule donnant « à coup sur » un nombre premier, encore moins les donnant tous. Il existe des formules comme celle de Mersenne qui donnent des nombres ayant une bonne probabilité d’être premiers, mais il faut de toute façon vérifier, Je cause un peu de ça dans http://www.drgoulu.com/2012/04/15/comment-produire-des-nombres-premiers/

      L’hypothèse de Riemann « affirme que les zéros de la fonction zêta contrôlent les oscillations des nombres premiers autour de leur position attendue. » comme le dit la wikipédia ( https://fr.wikipedia.org/wiki/Hypothèse_de_Riemann ) . D’une part la fonction zeta ne donne pas directement les nombres premiers, et d’autre part l’hypothèse de Riemann n’est toujours pas démontrée…

  11. Pingback: La deuxième conjecture de Hardy-Littlewood | Science étonnante

  12. THEORIE DES 4 JUMEAUX

    Tout les nombres premiers, à l’exception de 2 et 3, sont situés, soit à 6n-1, soit 6n+1, pour les désigner sans spécifié le rang +1 ou -1, j’utiliserais la notation 6n+-1.
    Tout les nombres, qui ne sont pas de la forme 6n+-1, sont divisibles soit par 2, soit par 3.
    Les 6n+-1, sont de deux sortes :
    il y a ceux qui sont premiers et ceux, qui ne sont pas premiers, car ils sont le produits de la multiplication de deux 6n+-1:
    Liste des 6n+-1 premiers, inférieurs à 100 :
    5-7-11-13-17-19-23-29-31-37-41-43-47-53-59-61-71-73-79-83-89-97
    Liste des 6n+-1, qui ne sont pas premiers, inférieur à 100:
    25-35-49-55-65-77-85-91-95

    Décomposition des 6n+-1, qui ne sont pas premiers:

    25 = 5 x 5
    35 = 5 x 7
    49 = 7 x 7
    55 = 5 x 11
    65 = 5 x 13
    77 = 7 x 11
    85 = 5 x 17
    91 = 7 x 13
    95 = 5 x 19

    Nous pouvons constater que les 6n+-1 non premiers, sont les produits de la multiplication de deux 6n+-1
    Les uns engendrant les autres, cela fait, qu’il n’y a que des jumeaux, qui peuvent prendre, quatre formes différentes, que j’ai désigné par VFAB:

    V = Les vrai jumeaux : cas ou les deux nombres sont premiers.
    F = Les faux jumeaux : cas ou les deux nombres sont multiples.
    A : Les demi-jumeaux A: le premier nombre, est premier et le second multiple
    B : Les demi-jumeaux B: le premiers nombre, est multiple et le second premiers.

    5-7= V
    11-13=V
    17-19=V
    23-25=A
    29-31=V
    35-37=B
    41-43=V
    47-49=A
    53-55=A
    59-61=V
    65-67=B
    71-73=V
    77-79=B
    83-85=A
    89-91=A
    95-97=B

    Ainsi s’expliquent les écarts variables, séparant les couples de vrais jumeaux, nous ne savons pas encore calculer les 6n+-1 premiers, par-contre nous savons comment calculer les 6n+-1, qui ne sont pas premiers.
    Maintenant comment déterminer les multiples d’un 6n+-1, se situant à 6n+-1, c’est ce que nous allons voir.

    Pour simplifier, je désignerais un nombre premier par la lettre P et les 6n+-1, qui ne sont pas premiers par les lettres Pp,
    Pou déterminer quels sont ses multiples d’un 6n+-1, situés à 6n+-1, il suffit d’appliquer P+(Px4)+(Px2)si ce nombre est premier ou Pp+(Ppx4)+(Ppx2), lorsqu’il s’agit d’un multiple.
    Exemple pour 5:
    5+(5×4)+(5×2)= 5+20+10,
    Cela nous donne cette suite:
    5+20+10+20+10+20+10+20+10……..(n+-1)+20+10…..∞
    les résultats:
    25;35;55;65;85;95;115;125;145;155;175……..∞
    Vous pouvez constater qu’en divisant ces résultats par 5 nous retombons sur les 6n+-1
    25:5=5
    35:5=7
    55:5=11
    65:5=13
    85:5=17
    95:5=19
    115:5=23
    125:5=25
    145:5=29
    155:5=31
    175:5=35

  13. Pour tout k entier naturel 2^2^k + 1 donne toujours un nombre premier.
    2^2^0+1=3, 2^2^1+1=5, 2^2^2+1=17, 2^2^3+1=257, 2^2^4+1=65537, 2^2^5+1=4294967297 , etc …

    • C’est ce que pensait Fermat, mais c’est faux 2^32 + 1 est divisible par 641

  14. « La recherche sur les nombres de Mersenne est encore très active », là il ne faut pas exagérer. Cette histoire de nombres premiers de Mersenne n’intéresse pas grand monde en math depuis un certain nombre de siècles (aucune idée de qui est ce Cole sauf qu’il y a un Cole prize de l’AMS mais à part ça….et je fais de la recherche en théorie des nombres, je viens de ma rappeler de ce qu’est un nombre de Mersenne en lisant cet article, je n’en n’avais plus entendu parler depuis la prépa….). Ce genre de choses intéresse les informaticiens et les cryptographes (qui utilisent des maths mais ne sont pas des mathématiciens) et est utile pour tester la puissance de leurs algorithmes et de leurs machines sous forme de défis en quelques sortes. C’est donc complètement légitime de ce point de vue là même si cette annonce médiatique a été complètement disproportionnée du point de vue même de l’intérêt même de ces gens là aussi.
    Ca intéresse aussi beaucoup les gens qui font de la vulgarisation en math car il n’y a pas besoin de connaître quoi que ce soit en math pour en parler (comme un nombre incalculable d’autres marronniers de la vulgarisation en math, que ce soit le théorème de Gödel (dont je n’ai qu’une vague idée de ce que c’est, ça n’intéresse plus grand monde depuis longtemps ce genre de choses), les fractales, les nombres de Fibonacci (qui eux n’ont clairement jamais intéressé personne à part les profs de premier cycle) et ainsi de suite).

    Mais en quelques sortes cela donne une vision erronée de la recherche en mathématique et cette annonce médiatique autour des nombres de Mersenne donne une vision très bizarre de la recherche en math, on s’intéresse tout de même à des choses infiniment plus profondes que savoir si 2^n-1 ou je ne sais quoi est premier.
    Le problème c’est que ça fait tout de même tâche: d’un coté des gens qui s’intéressent à la structure de l’univers (boson de Higgs, ondes gravitationnelles), la structure de la vie (biologie synthétique et ainsi de suite), le réchauffement climatique…et de l’autre des gens qui s’intéresseraient à savoir si les nombres de Mersenne sont premiers ou non…alors que les enjeux de la recherche en math actuelle sont du même ordre que ceux du boson de Higgs et compagnie.

    Mais on n’y peut rien avec ces histoires de marronniers en vulgarisation des maths. Ce blog de vulgarisation ainsi que le chaîne youtube sont vraiment très bons, c’est juste qu’on ne peut pas y échapper.

  15. Pingback: Le dernier des premiers | Automaths

  16. « Pour ces raisons, les mathématiciens adoreraient disposer d’une machine à fabriquer des nombres premiers, ou tout du moins d’une formule qui permette d’en construire à volonté. »
    Les mathématiciens disposent déjà d’une telle machine et en pratique l’algorithme RSA repose justement aussi en partie sur le fait qu’il est possible de générer de très grands nombres premiers très rapidement ( en temps polynômial en fonction de la taille des nombres premiers d’entrée ) grâce aux tests de primalité à la fois probabilistes et déterministes permettant de tester des nombres premiers de très grande taille.

  17. Jean-Louis Bertrand Thirot Reply

    Heu…
    Je voudrais pas dire une bétise…. mais voila, j’ai trouvé une technique qui me permet, pour n’importe quel nombre premier, de calculer la position du prochain.
    Je la teste actuellement. J’en suis au nombre 19211. A ce stade, chaque nombre prend environ 5s. Je n’ai pas idée du temps que ça prendra quand j’en serais a de très grands nombres, mais par contre la technique permet vraiment de trouver toujours le prochain, sans crible et sans teste de primalité, juste en déterminant l’écart avec le suivant….
    Est-ce que c’est vraiment nouveau et intéressant ?

  18. Jean-Marie COUSIN Reply

    Si cela est vrai alors il s’avérerait que les nombres premiers ont une « structure » ce qui serait révolutionnaire. Je suis très curieux de savoir jusqu’où cette technique « fonctionne ».

Reply To Dr. Goulu Cancel Reply

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.