La décomposition en facteurs premiers et les fonctions arithmétiques
Tout entier supérieur à 1 s'écrit, d'une seule façon, comme un produit de nombres premiers : 360 = 2³ × 3² × 5. C'est le théorème fondamental de l'arithmétique. Une fois cette « carte d'identité » connue, on lit tout : le nombre de diviseurs, leur somme, les nombres parfaits, la fonction de Möbius. Cinq planches pour voir pourquoi l'écriture est unique, ce qu'elle permet de calculer, et pourquoi, à l'inverse, la trouver est si difficile.
Vue d'ensemble
Écrivons n = p₁e₁ × p₂e₂ × … × pkek. Les fonctions arithmétiques les plus utiles se lisent directement sur les exposants :
| Fonction | Ce qu'elle compte | Formule | n = 360 = 2³·3²·5 |
|---|---|---|---|
| τ(n) | le nombre de diviseurs | (e₁ + 1)(e₂ + 1)… | 4 × 3 × 2 = 24 |
| σ(n) | la somme des diviseurs | Π (pe+1 − 1)/(p − 1) | 15 × 13 × 6 = 1 170 |
| φ(n) | les entiers premiers avec n | n Π (1 − 1/p) | 96 |
| μ(n) | la fonction de Möbius | 0 si un carré divise n, sinon (−1)k | 0 |
| ω(n) | le nombre de facteurs premiers distincts | k | 3 |
Une décomposition, et une seule
Si l'on coupe 360 en 8 × 45 ou en 12 × 30, arrive-t-on aux mêmes nombres premiers ?
Oui, et ce n'est pas une évidence. L'existence est facile : tant qu'un nombre n'est pas premier, on le coupe en deux facteurs plus petits, et cela s'arrête forcément. L'unicité repose sur le lemme d'Euclide, conséquence de la relation de Bézout : si un nombre premier divise un produit, il divise l'un des facteurs. Pour s'en convaincre, il suffit de regarder un monde où ce lemme est faux.
Un monde sans unicité : les nombres de Hilbert
Ne gardons que les nombres de la forme 4k + 1 : 1, 5, 9, 13, 17, 21… Le produit de deux d'entre eux est encore de cette forme. Appelons « premier de Hilbert » un tel nombre qui ne se décompose pas en produit de deux autres. Alors 9, 21 et 49 sont premiers de Hilbert, et pourtant 441 = 9 × 49 = 21 × 21. L'unicité est perdue, parce que le lemme d'Euclide n'y est plus vrai : 21 divise 9 × 49 sans diviser ni 9 ni 49.
Les diviseurs, rangés comme une boîte
Combien 360 a-t-il de diviseurs, et que vaut leur somme ?
Un diviseur de 2³ × 3² × 5 s'écrit 2i × 3j × 5k avec 0 ≤ i ≤ 3, 0 ≤ j ≤ 2, 0 ≤ k ≤ 1. Les diviseurs forment donc une « boîte » de 4 × 3 × 2 = 24 points : c'est τ(n) = (e₁ + 1)(e₂ + 1)(e₃ + 1). Leur somme se factorise de la même façon : σ(n) = (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5).
Nombres parfaits, amiables et suites aliquotes
Un nombre peut-il être égal à la somme de ses diviseurs propres ?
La somme des diviseurs propres (tous sauf n lui-même) est s(n) = σ(n) − n. Si s(n) = n, le nombre est parfait : 6 = 1 + 2 + 3. Si s(n) > n, il est abondant ; sinon, déficient. Deux nombres sont amiables si chacun est la somme des diviseurs propres de l'autre, comme 220 et 284, connus depuis Pythagore. En itérant s, on obtient une suite aliquote : elle tombe sur 1 puis 0, entre dans un cycle, ou… nul ne sait.
Fonctions multiplicatives et inversion de Möbius
Pourquoi toutes ces formules sont-elles des produits ?
τ, σ, φ et μ sont multiplicatives : si a et b sont premiers entre eux, f(ab) = f(a)f(b). Il suffit donc de les connaître sur les puissances de nombres premiers. La fonction de Möbius μ joue un rôle à part : Σ μ(d), sur les diviseurs d de n, vaut 1 si n = 1 et 0 sinon. Cette propriété permet d'« inverser » une somme sur les diviseurs : si g(n) = Σ f(d), alors f(n) = Σ μ(d) g(n/d). Par exemple, de l'identité de Gauss n = Σ φ(d), on tire φ(n) = Σ μ(d)·n/d.
Signature : la statistique des facteurs premiers
Multiplier est facile, factoriser est difficile. Mais combien de facteurs un nombre « typique » a-t-il, et quelle taille ont-ils ?
Hardy et Ramanujan (1917) ont montré qu'un nombre n typique a environ ln ln n facteurs premiers distincts, ce qui est très peu : environ 3 pour un nombre d'un million, environ 5 pour un nombre de cent chiffres. Erdős et Kac (1940) ont précisé que ω(n) suit approximativement une loi normale de moyenne et de variance ln ln n. La convergence est extraordinairement lente : on « voit » la cloche, mais décalée.
Un nombre est y-friable si tous ses facteurs premiers sont au plus y. Dickman (1930) a montré que la proportion des nombres jusqu'à x qui sont x1/u-friables tend vers ρ(u), où ρ vérifie uρ′(u) = −ρ(u − 1) : ρ(2) = 1 − ln 2 ≈ 0,307. Ces nombres sont le carburant des meilleurs algorithmes de factorisation (crible quadratique, crible algébrique), qui cherchent des valeurs friables et les combinent.
La division par essais demande jusqu'à √N tentatives. La méthode rho de Pollard (1975) itère x ↦ x² + 1 modulo N : modulo un facteur p inconnu, la suite finit par boucler (elle a la forme de la lettre ρ) au bout d'environ √p étapes, et un PGCD révèle p. Pour un nombre de 19 chiffres produit de deux facteurs de 10 chiffres, il faut quelques dizaines de milliers d'itérations au lieu d'un milliard de divisions.
Une brève histoire
En résumé
Une carte d'identité unique
Tout entier se décompose d'une seule façon en facteurs premiers, grâce au lemme d'Euclide. Ce n'est pas automatique : chez les nombres de Hilbert, l'unicité disparaît.
Tout se lit sur les exposants
Nombre et somme des diviseurs, φ, μ : ces fonctions sont multiplicatives et se calculent par des produits. L'inversion de Möbius passe de l'une à l'autre.
Facile dans un sens
Connaissant la décomposition, tout est simple ; la trouver est difficile. Les nombres ont peu de facteurs, souvent un très grand, et les meilleurs algorithmes exploitent les nombres friables.
Pour aller plus loin
Le record de la factorisation. En 2020, un nombre RSA de 250 chiffres (RSA-250) a été factorisé par le crible algébrique, au prix d'environ 2 700 années de calcul d'un cœur de processeur. Les clés actuelles ont plus de 600 chiffres.
Les ordinateurs quantiques. L'algorithme de Shor (1994) factoriserait en temps polynomial, grâce à la recherche de la période de ax mod N : c'est la raison des travaux actuels sur la cryptographie « post-quantique ».
Liens. PGCD et PPCM (max et min des exposants), relation de Bézout, nombres premiers de Mersenne, Fermat, Euler et les restes chinois, répartition des nombres premiers, théorie algébrique des nombres.