Produit des diviseurs d’un entier (première partie)

Prenons le nombre 6. Il possède exactement quatre diviseurs positifs: 1, 2, 3 et 6. Le produit de ses diviseurs est donc de 1 x  2 x 3 x 6 = 36.

A présent, tentons de faire l’inverse, c’est-à-dire retrouver le nombre à partir du produit de ses diviseurs. Par exemple, quel est le nombre dont le produit des diviseurs (positifs) est égal à  225 ? Ce dernier nombre n’étant pas très élevé, on peut tâtonner un peu pour trouver la solution. Je vous propose dans cet article une analyse plus systématique de ce problème.

Avant de poursuivre, indiquons que si n est un nombre entier naturel, le symbole \Pi(n) désignera le produit de tous ses diviseurs positifs. On sait d’après le théorème fondamental de l’arithmétique que n peut s’écrire sous la forme n= p_1^{\alpha_1} \dots p_r^{\alpha_r} où les p_i sont des nombres premiers. Pour bien comprendre ce qu’il se passe, nous étudierons d’abord la situation où le nombre n ne possède qu’un seul facteur premier.

Cas d’un nombre avec un seul facteur premier

Il s’agit donc du cas où n=p^\alpha (avec p un entier premier). Quels sont les diviseurs de n dans ce cas ? Ce sont tous les nombres p^i pour i variant de 0 à \alpha. Ainsi, le produit des diviseurs de n est donc

\Pi(n)= p^0 \times ... \times p^\alpha = p^{0+1+ \dots +\alpha}

Rappelons que la somme de tous les entiers de 1 à \alpha vaut \frac{\alpha(\alpha+1)}{2}. On peut donc écrire que

\displaystyle{ \Pi(n)=p^{\frac{\alpha(\alpha +1)}{2} } }

Nous pouvons maintenant répondre à la question posée en préambule: si n est un entier tel que le produit de ses diviseurs vaut 125=5^3, alors, tout d’abord, n ne peut avoir qu’un seul facteur premier, à savoir 5. En effet, tout diviseur premier de n divise \Pi(n) (car \Pi(n) est en particulier un multiple de n), donc divise 125=5^3: le nombre n ne possède qu’un seul diviseur premier, et il est égal à 5 (voir le lemme de Gauss). On peut donc écrire n sous la forme n=5^\alpha, et il s’agit de résoudre l’équation 5^{\frac{\alpha(\alpha +1)}{2}}=5^3, c’est-à-dire \frac{\alpha(\alpha +1)}{2}=3 (par unicité de la décomposition en facteurs premiers). Cette dernière équation montre que \alpha est un diviseur de 6, donc il suffit de tester les différentes valeurs 1, 2, 3 et 6. On constate que seule la valeur \alpha =2 convient, et donc n=5^2=25.

On peut vérifier réciproquement que les diviseurs de 25 sont 1, 5, et 25, et que leur produit 1 x 5 x 25 est bien égal à 125.

Nombres possédant deux facteurs premiers

Étudions le cas où n=p^\alpha q^\beta avec p et q deux nombres premiers. Les diviseurs de n sont les nombres p^i q^j pour i (respectivement j) allant de 0 à \alpha  (respectivement allant de 0 à \beta). Afin de visualiser plus facilement ce que donne le produit de tous ces diviseurs, nous allons les placer dans un tableau.

\begin{array}{cccc} p^0q^0 & p^1q^0 & \dots & p^\alpha q^0 \\ p^0q^1 & p^1q^1 & \dots & p^\alpha q^1 \\ \vdots & \vdots & \dots & \vdots \\ p^0q^\beta & p^1q^\beta & \dots & p^\alpha q^\beta \\ \end{array}

Ce tableau possède \alpha +1 colonnes et \beta +1 lignes. Pour calculer le nombre \Pi(n), il faut effectuer le produit de tous les éléments de ce tableau. Une manière astucieuse de faire cela consiste en premier lieu à faire le produit de chaque ligne, puis le produits de tous ces résultats obtenus.

Le produit de la première ligne vaut

p^0q^0 \times p^1q^0 \times \dots \times p^\alpha q^0 = p^{0+1+2+\dots+\alpha}q^{(\alpha+1) \times 0}=p^{\frac{\alpha(\alpha+1)}{2}}q^{(\alpha+1) \times 0}

Le produit de la i-ème ligne vaut

p^0q^i \times p^1q^i \times \dots \times p^\alpha q^i = p^{\frac{\alpha(\alpha+1)}{2}}q^{(\alpha+1) \times i}

Ainsi, lorsqu’on effectue le produit du produit des lignes, on obtient

\Pi(n)=p^{\frac{\alpha(\alpha+1)}{2}}q^{(\alpha+1) \times 0} \times p^{\frac{\alpha(\alpha+1)}{2}}q^{(\alpha+1) \times 1} \times \dots \times p^{\frac{\alpha(\alpha+1)}{2}}q^{(\alpha+1) \times \beta} = p^{(\beta+1)\frac{\alpha(\alpha+1)}{2}}q^{(\alpha+1) \times (0+1+\dots+\beta)}

La formule du produit des diviseurs est donc:

\Pi(n)= p^{(\beta+1)\frac{\alpha(\alpha+1)}{2}}q^{(\alpha+1)\frac{\beta(\beta+1)}{2}}

Signalons qu’on peut écrire cette formule plus simplement à l’aide de n, en constatant qu’on a \Pi(n)=n^{\frac{(\alpha+1)(\beta+1)}{2}}.

Nombres possédant un nombre quelconque de facteurs premiers


Pour les personnes intéressées par ce qu’il se passe dans le cas général, vous pouvez vous reporter à la deuxième partie de cet article. (attention, cet article est plus difficile à lire et s’adresse essentiellement plutôt à des lecteurs possédant un minimum de bagage mathématique).

 

Source: Cet article m’a été inspiré par cette énigme posée sur le forum du site Prise2tete.fr. Il s’agissait de trouver le nombre dont le produit des diviseurs est 15 407 021 574 586 368. (Je précise qu’au moment où j’écris cet article, les solutions données par les intervenants de ce forum ne sont pas visibles).

Résolvons cette énigme en commençant par constater que 15 407 021 574 586 368 = 2^{30} \times 3^{15}. On pourrait trouver cette factorisation à la main en effectuant des divisions successives par 2 et 3. Pour des raisons de commodités temporelles (dirons-nous), j’ai pour ma part utilisé ce site.

Soit n un entier tel que \Pi(n)= 15 407 021 574 586 368=2^{30} 3^{15}. De la même manière qu’on l’a montré précédemment dans cet article, le nombre n ne peut posséder que deux facteurs premiers, à savoir 2 et 3. Posons n=2^\alpha 3^\beta. Il s’agit de résoudre le système d’équations

\begin{array}{c} (\beta+1)\frac{\alpha(\alpha+1)}{2}=30 \\ (\alpha+1)\frac{\beta(\beta+1)}{2}=15 \end{array}

La deuxième équation montre que \beta et \beta+1 sont des diviseurs de 2×15 = 30. Les diviseurs de 30 étant 1, 2, 3, 4, 5, 6, 10, 15 et 30, l’entier \beta ne peut valoir que 1, 2, 3, 4, ou 5. Il suffit de tester tous ces cas pour voir lesquels peuvent correspondre aussi avec la première équation.

  • Si \beta=1 alors la deuxième équation devient \alpha+1 = 15, donc \alpha =14, ce qui est impossible car la première équation impose que \alpha divise 2 x 30 = 60.
  • Si \beta = 2 alors la deuxième équation devient 3(\alpha+1)=15 donc \alpha =4. La première équation étant alors vérifiée, c’est donc une solution possible.
  • Si \beta = 3 alors la deuxième équation devient 6(\alpha+1)=15 ce qui est impossible, car 6 ne divise pas 15.
  • Si \beta = 4 alors la deuxième équation devient 10(\alpha+1)=15, ce qui n’est pas possible non plus.
  • Si \beta = 5 alors la deuxième équation devient 15(\alpha+1)=15 alors \alpha=0. Mais alors, la première équation n’est pas vérifiée (sinon on aurait 0=30). Ce cas est donc à écarter.

S’il y a une solution, c’est donc n=2^4 3^2=144. Il faut vérifier que le produit des diviseurs de 144 vaut bien 15 407 021 574 586 368. Les diviseurs de 144 sont 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48 ,72, 144. Leur produit vaut bien 15 407 021 574 586 368.

Publicités
Cet article, publié dans Arithmétique, est tagué , , . Ajoutez ce permalien à vos favoris.

Un commentaire pour Produit des diviseurs d’un entier (première partie)

  1. Mathieu Therialt dit :

    merci tres illustratif

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s