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
Réponses
-
Bonsoir.
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.
-
Bonsoir à vous,
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 ! -
Une formule très certainement:
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. -
Tout ça m'a l'air affreusement compliqué pour déterminer le nombre de diviseurs d'un entier, connaissant sa décomposition en facteurs premiers. Si $n = p_1^{m_1} \dots p_r^{m_r}$ avec les $p_i$ des nombres premiers deux à deux distincts, alors les diviseurs (positifs) de $n$ sont précisément les entiers de la forme $p_1^{k_1} \dots p_r^{k_r}$ avec $k_i \leq m_i$ pour $1 \leq i \leq r$. Ainsi, il y a exactement $(m_1+1) \times \dots \times (m_r+1)$ diviseurs de $n$ ($m_1+1$ choix pour l'exposant de $m_1$, $\dots$, $m_r+1$ choix pour l'exposant de $p_r$).
-
Amatheur01 a écrit:http://www.les-mathematiques.net/phorum/read.php?5,2316916,2316984#msg-2316984
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.
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é... -
Ce n'est pas une « astuce », c'est une fonction multiplicative classique $d(n)$ rappelée par Poirot : https://en.wikipedia.org/wiki/Multiplicative_function.
Bref c'est du cours, on l'apprend et on continue. -
Bonjour,
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, -
Bonjour,
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$ -
Avec la partie entière $[x]$ on a une formule pas très utile mais quand même explicite qui traduit la formule de Fdp
$$d(n)=1+\sum_{k=1}^{n-1}\left[\frac{n}{k}\right]-\left[\frac{n-1}{k}\right]$$ -
Salut
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
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres