Compter les diviseurs sans les écrire

/ Christian Nguembou Tagne

Combien soixante-douze a-t-il de diviseurs ? On les cherche par paires : un et soixante-douze, deux et trente-six, trois et vingt-quatre, quatre et dix-huit, six et douze, huit et neuf. Douze, si l’on n’en a oublié aucun — et rien, dans cette recherche, ne garantit qu’on n’en a oublié aucun. Pour trois mille cent soixante-huit, la même méthode devient pénible ; pour un nombre de dix chiffres, elle est hors de portée. Il existe pourtant une formule qui donne le compte sans dresser la liste, et qui dit au passage pourquoi la liste a cette longueur. Elle tient en une ligne. Elle ne vaut que parce que la décomposition en facteurs premiers est unique.

Cet article est le quatrième de la série Le peuple des nombres premiers, tirée du chapitre 4 de Mathématiques en terminales scientifiques (Tome 2). Il s’appuie sur le précédent, « Le théorème fondamental de l’arithmétique, et son seul point difficile », paru le 11 octobre, et reprend l’ensemble H qui y faisait échouer l’unicité. Le calcul du PGCD par les exposants complète celui que fournit l’algorithme d’Euclide. Le prochain article de la série, un exercice, paraît le 15 octobre.

1. La place d’un nombre premier dans un entier

Le Tome 2 introduit un outil qui mesure combien de fois un nombre premier entre dans un entier. Pour un nombre premier p et un entier n\geq 1, l’ensemble des r tels que p^{r} divise n contient 0 et est majoré ; il a donc un plus grand élément, noté \nu_{p}(n) et appelé la valuation de n en p. Ainsi \nu_{2}(72)=3, \nu_{3}(72)=2 et \nu_{5}(72)=0, puisque 72=2^{3}\times 3^{2}.

Si n=p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}} est la décomposition de n, la valuation en p_{i} vaut \alpha_{i}, et la valuation en tout autre nombre premier vaut 0. Les valuations ne disent donc rien de plus que la décomposition ; elles le disent pour tous les nombres premiers à la fois, ce qui permet de comparer deux entiers qui n’ont pas les mêmes facteurs.

Proposition 1. Soient m et n des entiers naturels non nuls. Le nombre m divise n si, et seulement si, \nu_{p}(m)\leq\nu_{p}(n) pour tout nombre premier p.

Démonstration. Si m divise n, toute puissance p^{r} qui divise m divise aussi n, par transitivité ; d’où \nu_{p}(m)\leq\nu_{p}(n). Réciproquement, si l’inégalité vaut pour tout p, on écrit

\displaystyle n=\prod_{p}p^{\nu_{p}(n)}=\prod_{p}p^{\nu_{p}(m)}\times\prod_{p}p^{\nu_{p}(n)-\nu_{p}(m)}=m\times\prod_{p}p^{\nu_{p}(n)-\nu_{p}(m)},

où les produits portent sur les nombres premiers qui divisent n, et où tous les exposants du dernier produit sont des entiers naturels. Le nombre m divise donc n. \quad\Box

2. Tous les diviseurs, et chacun une seule fois

La proposition 1 dit exactement à quoi ressemble un diviseur. Un diviseur positif de n=p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}} ne fait intervenir aucun autre nombre premier que p_{1}, …, p_{k}, et chacun avec un exposant au plus égal au sien :

Proposition 2. Les diviseurs positifs de n=p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}} sont exactement les nombres p_{1}^{\beta_{1}}\cdots p_{k}^{\beta_{k}} avec 0\leq\beta_{i}\leq\alpha_{i} pour chaque i.

Pour 72=2^{3}\times 3^{2}, cela donne un tableau : l’exposant de 2 choisit la ligne, celui de 3 la colonne.

\begin{array}{c|ccc} \times & 3^{0} & 3^{1} & 3^{2} \\ \hline 2^{0} & 1 & 3 & 9 \\ 2^{1} & 2 & 6 & 18 \\ 2^{2} & 4 & 12 & 36 \\ 2^{3} & 8 & 24 & 72 \end{array}

Les douze diviseurs trouvés à tâtons dans l’accroche y sont tous. Le tableau garantit en plus ce que la recherche par paires ne garantissait pas : il n’en manque aucun, puisque tout diviseur a sa case, et aucun n’apparaît deux fois.

3. Le compte

Proposition 3. L’entier n=p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}} possède exactement (\alpha_{1}+1)(\alpha_{2}+1)\cdots(\alpha_{k}+1) diviseurs positifs.

Démonstration. Associons à chaque suite d’exposants (\beta_{1},\dots,\beta_{k}), avec 0\leq\beta_{i}\leq\alpha_{i}, le nombre p_{1}^{\beta_{1}}\cdots p_{k}^{\beta_{k}}. D’après la proposition 2, tout diviseur positif de n est atteint. Deux suites différentes donnent deux nombres différents, et c’est ici que tout se joue : deux écritures distinctes d’un même nombre comme produit de puissances de nombres premiers contrediraient l’unicité de la décomposition. On a donc une bijection entre les suites d’exposants et les diviseurs. L’exposant \beta_{i} prend \alpha_{i}+1 valeurs, de 0 à \alpha_{i}, d’où le produit. \quad\Box

Pour 72, on retrouve (3+1)(2+1)=12, le nombre de cases du tableau. L’exemple du Tome 2 va plus loin : 3168=2^{5}\times 3^{2}\times 11 a 6\times 3\times 2=36 diviseurs positifs. Il n’a pas fallu en écrire un seul.

4. Ce que la formule doit à l’unicité

La démonstration n’a eu besoin de l’unicité qu’en un point, l’injectivité. Ce point n’est pas décoratif. L’exemple qui suit ne figure pas dans l’ouvrage. Reprenons l’ensemble H des entiers congrus à 1 modulo 4, où le nombre 441 admet deux décompositions en indécomposables, 9\times 49 et 21\times 21. Ses diviseurs dans H sont 1, 9, 21, 49 et 441 : il y en a cinq.

Appliquée à la première décomposition, la formule donnerait (1+1)(1+1)=4 ; appliquée à la seconde, 2+1=3. Aucune des deux ne tombe juste, et elles ne s’accordent même pas entre elles. La formule du nombre de diviseurs n’est pas une propriété des produits en général. C’est une propriété de \mathbb{N}, héritée du lemme d’Euclide.

5. PGCD et PPCM par les exposants

La proposition 1 donne aussi, presque sans calcul, le plus grand commun diviseur et le plus petit commun multiple de deux entiers.

Proposition 4. Pour des entiers a et b au moins égaux à 2 et pour tout nombre premier p,

\displaystyle \nu_{p}\bigl(\mathrm{pgcd}(a,b)\bigr)=\min\bigl(\nu_{p}(a),\nu_{p}(b)\bigr)\qquad\text{et}\qquad\nu_{p}\bigl(\mathrm{ppcm}(a,b)\bigr)=\max\bigl(\nu_{p}(a),\nu_{p}(b)\bigr).

Un diviseur commun doit avoir, en chaque nombre premier, un exposant au plus égal à celui de a et à celui de b ; le plus grand d’entre eux prend partout le minimum. Un multiple commun doit avoir des exposants au moins égaux aux deux ; le plus petit prend partout le maximum. Avec 360=2^{3}\times 3^{2}\times 5 et 756=2^{2}\times 3^{3}\times 7, on lit

\displaystyle \mathrm{pgcd}(360,756)=2^{2}\times 3^{2}=36\qquad\text{et}\qquad\mathrm{ppcm}(360,756)=2^{3}\times 3^{3}\times 5\times 7=7560.

La formule \mathrm{pgcd}(a,b)\times\mathrm{ppcm}(a,b)=ab devient alors transparente. Pour deux nombres \alpha et \beta, on a toujours \min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta, et il suffit de l’appliquer exposant par exposant : 36\times 7560=272160=360\times 756. Le Tome 2 suit le chemin inverse, et c’est légitime : il part de l’égalité \mathrm{pgcd}\times\mathrm{ppcm}=ab, établie au chapitre précédent, pour en déduire la formule du PPCM.

Une réserve, pour finir. Cette méthode suppose les deux nombres décomposés, et décomposer un grand nombre est difficile, alors que l’algorithme d’Euclide calcule un PGCD sans rien factoriser. La formule par les exposants sert à comprendre ; pour calculer sur de grands nombres, c’est l’algorithme qui convient.

6. Pair ou impair ?

Les diviseurs de 72 allaient par paires : 1 et 72, 2 et 36, jusqu’à 8 et 9. Ceux de 36 commencent de même, 1 et 36, 2 et 18, 3 et 12, 4 et 9, puis vient 6, qui reste seul. La formule donne (2+1)(2+1)=9 : un nombre impair. L’exercice du 15 octobre demande quels entiers sont dans ce cas, et la formule y répond en deux lignes.

Les valuations, les propositions 1 à 4 et l’exemple de 3168 sont ceux de la section Décomposition en produit de facteurs premiers du chapitre 4 de Mathématiques en terminales scientifiques (Tome 2). Le tableau des diviseurs de 72, l’exemple de l’ensemble H et la lecture de \mathrm{pgcd}\times\mathrm{ppcm}=ab par les exposants n’y figurent pas et sont ajoutés ici.

Votre commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.