formule de Legendre

Écrivons les entiers de 1 à 30, puis rayons ceux qui sont divisibles par 2, par 3 ou par 5. Il reste 1 et les nombres premiers supérieurs à √30 : 7, 11, 13, 17, 19, 23 et 29.

La formule de Legendre traduit ce crible en calcul. La fonction de Möbius corrige les doubles et triples suppressions grâce à l’inclusion-exclusion. Le résultat compte les nombres premiers strictement supérieurs à √x et inférieurs ou égaux à x, après retrait de l’entier 1.

Pour un réel x au moins égal à 1, la fonction π associe à x le nombre de nombres premiers inférieurs ou égaux à x. On forme P, le produit de tous les nombres premiers p inférieurs ou égaux à √x. La formule de Legendre exprime alors le nombre de nombres premiers strictement supérieurs à √x et inférieurs ou égaux à x par une somme sur les diviseurs de P.

La fonction de Möbius μ vaut 1 en 1. Elle vaut (−1)^r pour le produit de r nombres premiers distincts, et 0 lorsqu’un carré premier divise son argument. Ici, P est sans facteur carré : chacun de ses diviseurs d est donc lui aussi sans facteur carré. Le terme ⌊x/d⌋ compte les multiples de d qui ne dépassent pas x, tandis que le signe μ(d) applique l’inclusion-exclusion. La somme compte finalement 1 et les nombres premiers de l’intervalle considéré ; le terme −1 retire l’entier 1.

Cette identité exacte est une écriture algébrique du crible d’Ératosthène. Legendre en a déduit que la limite de π(x)/x est nulle lorsque x tend vers l’infini : les nombres premiers deviennent proportionnellement plus rares parmi les entiers.

Soit x un réel au moins égal à 1. Notons P le produit des nombres premiers p tels que p ≤ √x, et d un diviseur positif de P. Avec π pour la fonction de comptage des nombres premiers et μ pour la fonction de Möbius, on a :

Le membre de droite compte par inclusion-exclusion les entiers au plus égaux à x qui ne sont divisibles par aucun nombre premier au plus égal à √x, puis enlève 1. Les entiers restants sont précisément les nombres premiers comptés à gauche.

La formule s’applique à un réel x ≥ 1. Il faut connaître tous les nombres premiers au plus égaux à √x, former leur produit P, puis parcourir les diviseurs positifs de P. La borne est inclusive : si √x est premier, ce nombre premier entre dans P et dans π(√x). Le symbole ⌊x/d⌋ désigne la partie entière de x/d.

Pour une valeur négative de x, √x n’est pas réel et cette formulation ne s’applique pas. Pour compter directement tous les nombres premiers jusqu’à une grande borne, la formule demeure exacte, mais le nombre de diviseurs de P augmente rapidement ; un crible algorithmique évite alors d’énumérer cette somme.

Prenons x = 30. Les nombres premiers qui ne dépassent pas √30 ≈ 5,48 sont 2, 3 et 5. Leur produit est donc P = 2 × 3 × 5 = 30, dont les huit diviseurs sont 1, 2, 3, 5, 6, 10, 15 et 30.

1. On associe à ces diviseurs les valeurs de Möbius 1, −1, −1, −1, 1, 1, 1 et −1.
2. On calcule les parties entières : 30, 15, 10, 6, 5, 3, 2 et 1.
3. On effectue la somme pondérée : 30 − 15 − 10 − 6 + 5 + 3 + 2 − 1 = 8.
4. On retire l’entier 1 : −1 + 8 = 7.

La formule donne donc π(30) − π(√30) = 7. Le contrôle direct retrouve sept nombres premiers au-delà de √30 et jusqu’à 30 : 7, 11, 13, 17, 19, 23 et 29.

La grille du crible conserve aussi l’entier 1. Elle rend ainsi visible pourquoi la somme vaut 8 alors que la différence des deux valeurs de π vaut 7.

Pour une petite borne, on peut écrire les entiers puis barrer les multiples des nombres premiers au plus égaux à √x. La formule fournit exactement le même décompte sous une forme algébrique.

Lorsqu’on veut vérifier un calcul, on compare la somme de Möbius avec la liste des entiers qui n’ont aucun facteur premier parmi ceux de P. Cette liste doit contenir 1 et les nombres premiers strictement supérieurs à √x et inférieurs ou égaux à x.

Pour de grandes bornes, un crible informatique est préférable si le but est seulement d’obtenir π(x). La formule reste surtout utile pour relier le comptage des nombres premiers à l’inclusion-exclusion et à la fonction de Möbius.

La formule de Legendre n’est pas le crible d’Ératosthène lui-même. Le crible barre des multiples dans une liste ; la formule traduit ce geste par une somme de Möbius. Pour x = 30, les deux voies donnent les mêmes sept nombres premiers au-delà de √30.

Elle ne doit pas non plus être confondue avec le théorème des nombres premiers. La formule donne une identité exacte et finie pour chaque x, tandis que le théorème décrit le comportement asymptotique de π(x). Le résultat π(x)/x → 0 mentionné par Legendre est plus faible que cette description asymptotique.

Enfin, π(x) et μ(d) ont des rôles distincts. La première compte des nombres premiers jusqu’à une borne ; la seconde attribue un signe ou zéro selon la factorisation de son argument. Dans la formule, μ organise les corrections d’inclusion-exclusion.

À une borne carrée, il ne faut pas oublier l’inclusivité. Pour x = 25, √x = 5 : le nombre premier 5 appartient à P et est compté dans π(√x), pas dans la différence π(x) − π(√x).

La valeur μ(k) = 0 intervient dans la définition générale de la fonction de Möbius lorsqu’un carré premier divise k. Dans la somme de Legendre, tous les diviseurs d de P sont sans facteur carré ; aucun terme effectivement parcouru n’a donc une valeur de Möbius nulle.

La somme d’inclusion-exclusion ne compte pas immédiatement les seuls nombres premiers : elle conserve aussi 1. Omettre le terme −1 produit une réponse trop grande d’une unité, comme le montre x = 30 avec une somme égale à 8 pour sept nombres premiers recherchés.

Enfin, la limite π(x)/x → 0 signifie que la proportion des nombres premiers tend vers zéro. Elle ne signifie ni qu’il n’existe plus de nombres premiers au-delà d’un seuil, ni que π(x) finit par diminuer.

Le crible d'Eratosthène montre la procédure concrète dont la formule de Legendre fournit l’écriture algébrique.

La fiche sur le théorème des nombres premiers précise le résultat asymptotique vers lequel cette étape historique conduit.

La définition d’un nombre premier permet de revoir le critère de divisibilité qui fonde le crible et le comptage par π.