Nombre de diviseurs d'un nombre quelconque
dans Arithmétique
Bonsoir,
Existe-t-il une méthode ou une formule qui donne le nombre de diviseurs d'un nombre quelconque ?
Merci d'avance.
Cora59
Existe-t-il une méthode ou une formule qui donne le nombre de diviseurs d'un nombre quelconque ?
Merci d'avance.
Cora59
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Oui.
Une méthode consiste à factoriser le nombre en produits de facteurs premiers, compter le nombre de diviseurs de chaque puissance de facteurs premiers et d'en faire le produit.
Une autre méthode consiste à construire la liste des diviseurs du nombre et à en déterminer la taille.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Je profite de ce sujet ouvert pour vous demander de l'aide à propos de ces décompositions en facteurs premiers.
Choisissons un entier $N$. On prend $N = 12600$. Sa décomposition en facteurs premiers est la suivante : $2^3\times3^2\times5^2\times7$.
Comme vous le savez, on peut "fabriquer" des diviseurs de N en multipliant les facteurs de sa décomposition entre eux. Par exemple, on aura comme diviseurs de $12600 \ 3, 2^3, 2\times3, 3^2, 2\times3\times5, 2\times3\times3\times5\times7$, etc.
En fait, pour fabriquer un diviseur de $N$, on pioche un ou plusieurs facteurs premiers dans la décomposition totale de $N$ et on les multiplie entre eux (excusez-moi si ma façon d'expliquer est un peu "barbare"). Donc, on prend plusieurs premiers parmi l'ensemble des premiers, ce qui est très similaire à l'outil combinatoire $\binom{n}{k}$ !
Alors, c'est facile d'utiliser cet outil pour dénombrer le nombre de combinaisons de facteurs premiers (et donc le nombre de diviseurs) de $N$ quand sa décomposition n'inclut que des facteurs à multiplicité 1. (On va appeler la fonction qui donne le nombre de diviseurs de $N \ d(n)$.)
Par exemple, $N = 2\times3\times5\times7 = 210$. Le produit qui formera le diviseur que l'on pourra fabriquer comprendra au maximum la somme des exposants de la décomposition de $N$ (qu'on nommera $s_n$) facteurs. Ici, $s_n = 1+1+1+1 = 4$.
On a donc, $d(N) = \binom{4}{0} + \binom{4}{1} + \binom{4}{2} + \binom{4}{3} + \binom{4}{4} = \sum_{0}^4 \binom{4}{k} = 2^4 = 16$.
Mais voilà, les choses se corsent lorsque l'on a des facteurs à multiplicité multiple. Par exemple, pour $N = 12600 = 2^3\times3^2\times5^2\times7$. On ne peut plus appliquer la formule du $\binom{n}{k}$, car si l'on fait cela, on va compter différemment le premier 2*le premier 3 et le second 2*le premier 3 alors que le résultat revient au même.
J'ai trouvé plusieurs formules pour calculer $d(n)$ dans ces cas-là.
Avant tout, on doit poser quelques jalons.
Soit $P_m$ l'ensemble contenant les facteurs de la décomposition ayant un exposant supérieur ou égal à $m$. Par exemple, dans $2^3\times3^2\times5^2\times7$, $P_1 = \{2,3,5,7\}, P_2 = \{2,3,5\}, P_3 = \{2\}$. En fait, un facteur $p_1^n$ sera présent (sous la forme $p_1$) dans tous les sous-ensembles $P_m$ avec $m \leq n$. Autrement dit, il sera présent dans $P_n$, P_(n-1), P_(n-2),… jusqu'à $P_1$.
Soit $D_n$ le nombre de diviseurs fabriqués à partir d'un produit de $n$ facteurs.
Voici mes formules (je ne vous détaille pas comment je les ai trouvées mais je peux toujours l'expliquer sur demande) :
$D_0 = 1$ (et sera toujours égal à 1).
$D_1 = card(P_1)$.
$D_2 = card(P_2) + \binom{card(P_1)}{2}$.
$D_3 = card(P_3) + card(P_2)(card(P_1 - 1) + \binom{card(P_1)}{3}$.
$D_4 = card(P_4) + card(P_3)(card(P_1 - 1) + \binom{card(P_2)}{2} + card(P_2)\binom{card(P_1) - 1}{2} + \binom{card(P_1}{4}$.
$D_5 = card(P_5) + card(P_4)(card(P_1 - 1) + card(P_3)(card(P_2)-1) + card(P_3)\binom{card(P_1)-1}{2} + \binom{card(P_2)}{2}(card(P_1)-2)$
$+\ card(P_2)\binom{card(P_1)-1}{3} + \binom{card(P_1)}{5}$.
J'ai trouvé les formules pour $D_6$ et $D_7$ mais elles sont longues et difficiles à gérer.
Essayons ces formules avec $N = 2^3\times3^2\times5^2\times7$.
Ici,
• $P_1 = \{2,3,5,7\}$ ;
• $P_2 = \{2,3,5\}$ ;
• $P_3 = \{2\}$ ;
• $P_4 = \emptyset$.
$s = 3+2+2+1 = 8$.
On teste les formules :
• $D_0 = 1$ ;
• $D_1 = 4$ ;
• $D_2 = 3 + 6 = 9$ ;
• $D_3 = 1 + 3(4-1) + 4 = 1 + 9 + 4 = 14$ ;
• $D_4 = 0 + 1(4-1) + 3 + 3\times3 + 1 = 3 + 3 + 9 + 1 = 16$.
Par symétrie des $D_n$, on a $D_n$ = D_(s-n) (avec $s$ la somme de tous les exposants des facteurs de la décomposition. Ici, $s = 8$, on aura donc des produits d'une longueur de 8 facteurs max). Dans notre exemple, $D_2$ = D_(8-2) = $D_6$. Ou encore, $D_1$ = D_(8-1) = $D_7$.
Ainsi, on peut poser :
• $D_5 = 14$.
• $D_6 = 9$.
• $D_7 = 4$.
• $D_8 = 1$.
À partir de cela, on additionne tout pour trouver $d(N) = 1+4+9+14+16+14+9+4+1 = 72$. On vérifie si ce résultat est exact en faisant le produit de l'exposant de chaque facteur augmenté de 1 $= (3+1)(2+1)(2+1)(1+1) = 4\times3\times3\times2 = 72$. C'est donc juste.
Il est relativement facile de trouver les formules pour chaque $D_n$, mais ces formules deviennent vite très longues et très encombrantes. Donc, je voulais vous demander s'il était possible d'utiliser directement une formule universelle pour trouver le nombre de diviseurs de $N$ à partir de sa décomposition, et en utilisant les $\binom{n}{k}$, sans retomber sur l'astuce du produit des exposants augmentés de 1.
Merci par avance et bonne soirée !
Le nombre de diviseurs de $n$ est égal à $\displaystyle \sum_{k=1}^{n}N_n(k)$
Avec $N_n(k)=1$ si $k$ divise $n$ , $0$ autrement.
Tu écris (par exemple) $(2+1)(4+1)(2+1)(1+1)(2+1)(1+1)$ sous la forme $(1+1)^2(2+1)^3(4+1)$ et tu développes chaque puissance avec le binôme de Newton pour faire apparaître tes binomiaux.
Ca me parait bien compliqué...
Bref c'est du cours, on l'apprend et on continue.
Merci pour vos réponses.
Je sais qu'une méthode avec les coefficients binomiaux serait très difficile à appliquer et très encombrante (car il ne semble pas y avoir de formule qui donne directement le résultat avec), mais bien évidemment je ne songeais pas à l'utiliser couramment, c'était juste par simple curiosité.
Bonne fin de journée,
La formule qui donne le nombre de diviseurs permet de retrouver un résultat bien connu.
Soit $p_1,...,p_n$ des nombres premiers et $a$ un entier.
Calculons le nombre de diviseurs de $A=p_1^a...p_n^a$ de deux façons différentes.
1) Selon la formule donnée ci-dessus c'est $(a+1)^n$.
2) Choisissons $k$ nombres parmi $p_1,...,p_n$, ($k$ entre $0$ et $n$), il y a $\binom{n}{k}$ façons.
Pour former un diviseur de $A$ il faut encore choisir les exposants entre $1$ et $a$ : $a^k$ façons.
Concluons :$\displaystyle \sum _{k=0} ^n \binom{n}{k} a^k=(a+1)^n$
$$d(n)=1+\sum_{k=1}^{n-1}\left[\frac{n}{k}\right]-\left[\frac{n-1}{k}\right]$$
On pose N=p1a1.....pkak
On pose aussi M=(1+p1+p12+p13+...+p1a1)......(1+pk+pk2+pk3+...+pkak)
Lorsque on développe M, on remarque que tous les diviseurs de N sont présents, et une seule fois, cela vous permet d'en déduire.
Cordialement