Fonction nombre de diviseurs

En théorie des nombres — une branche des mathématiques — la fonction nombre de diviseurs est une fonction arithmétique qui indique le nombre de diviseurs d'un entier naturel non nul ${\displaystyle n}$, en incluant parmi les diviseurs de ${\displaystyle n}$ les nombres 1 et ${\displaystyle n}$. Elle est généralement notée ${\displaystyle {\text{d}}}$ ou ${\displaystyle \tau }$ (de l'allemand Teiler : diviseur), ou encore ${\displaystyle \sigma _{0}}$, comme cas particulier de fonction somme des puissances k-ièmes des diviseurs.

Définition

Pour tout nombre naturel ${\displaystyle n}$ on définit :

${\displaystyle {\text{d}}(n)=\operatorname {card} \left(\{d\in \mathbb {N} {\text{ ; }}1\leqslant d\leqslant n\ {\text{et}}\ d|n\}\right)=\sum _{d|n}1}$ où ${\displaystyle d|n}$ indique la divisibilité de ${\displaystyle n}$ par ${\displaystyle d}$.

Les premières valeurs sont les suivantes[1] :

n	1	2	3	4	5	6	7	8	9	10	11	12
Diviseurs de n	1	1, 2	1, 3	1, 2, 4	1, 5	1, 2, 3, 6	1, 7	1, 2, 4, 8	1, 3, 9	1, 2, 5, 10	1, 11	1, 2, 3, 4, 6, 12
d(n)	1	2	2	3	2	4	2	4	3	4	2	6

Propriétés

• On a l'identité suivante : ${\displaystyle \sum _{k=1}^{n}{\text{d}}(k)=\sum _{d=1}^{n}\left\lfloor {\frac {n}{d}}\right\rfloor }$ où ${\displaystyle \left\lfloor \,.\right\rfloor }$ désigne la fonction partie entière[2],[3],[4] :

Démonstration

${\displaystyle \sum _{k=1}^{n}{\text{d}}(k)=\sum _{k=1}^{n}\sum _{d|k}1=\sum _{d=1}^{n}\sum _{\begin{matrix}1\leqslant k\leqslant n\\d|k\end{matrix}}1=\sum _{d=1}^{n}\left\lfloor {\frac {n}{d}}\right\rfloor .}$

• Si la décomposition en produit de facteurs premiers de ${\displaystyle n}$ est

  ${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\dots p_{r}^{\alpha _{r}}}$,

  alors[5] :

  ${\displaystyle {\text{d}}(n)=(\alpha _{1}+1)(\alpha _{2}+1)\dots (\alpha _{r}+1)}$.

• La fonction nombre de diviseurs est donc multiplicative, c.-à-d. que si ${\displaystyle m}$ et ${\displaystyle n}$ sont premiers entre eux, alors :

  ${\displaystyle {\text{d}}(mn)={\text{d}}(m){\text{d}}(n)}$.

• Un nombre n est premier si et seulement si d(n)=2.
• Un nombre n est un carré parfait si et seulement si d(n) est impair.
• ${\displaystyle {\text{d}}(n)}$ est le double du nombre de diviseurs de n entre 1 et √n, auquel il faut retrancher 1 si ${\displaystyle n}$ est un carré parfait, donc un majorant de d(n) est 2√n.
• La fonction génératrice de (d(n)) s'exprime comme série de Lambert :

  ${\displaystyle \sum _{n=1}^{\infty }{\text{d}}(n)s^{n}=\sum _{n=1}^{\infty }{\frac {s^{n}}{1-s^{n}}}}$ (pour ${\displaystyle \operatorname {Re} (s)>1}$)

• La série de Dirichlet de (d(n)) est le carré de la fonction zêta de Riemann[6] :

  ${\displaystyle \sum _{n=1}^{\infty }{\frac {{\text{d}}(n)}{n^{s}}}=\zeta ^{2}(s)}$ (pour ${\displaystyle \operatorname {Re} (s)>1}$)

Comportement asymptotique

Formule de Dirichlet

Représentation en bâtons de d(n) ; en rouge, de ${\displaystyle {\frac {\sum _{k=1}^{n}d(k)}{n}}}$ ; en bleu, de H_n-1 et H_n ; et en vert, de ln n+2γ-1.

La fonction d est très irrégulière : elle prend la valeur 2 pour ${\displaystyle n}$ premier, et prend aussi des valeurs arbitrairement grandes (par exemple N + 1 pour n = 2^N) . Mais en moyenne de Cesàro : ${\displaystyle {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}\sim \ln n}$.

Ceci vient de la formule ${\displaystyle \sum _{k=1}^{n}{\text{d}}(k)=\sum _{k=1}^{n}\left\lfloor {\frac {n}{k}}\right\rfloor }$ , dont on déduit : ${\displaystyle H_{n}-1\leqslant {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}\leqslant H_{n}}$ où (H_n) est la série harmonique, puis l'encadrement :

${\displaystyle \ln n-1\leqslant {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}\leqslant \ln n+1}$.

Représentation en rouge de d(n) ; en bleu, de l'ordre moyen ln n + 2γ ; et en vert, de 2, correspondant aux nombres premiers.

Un développement plus précis est donné par[2],[7],[8],[4]

${\displaystyle {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}=\ln n+2\gamma -1+O(1/{\sqrt {n}})}$

(où O est un symbole de Landau et γ la constante d'Euler-Mascheroni.)

Il a été démontré par Johann Peter Gustav Lejeune Dirichlet en 1849[9].

On en déduit qu'un ordre moyen pour d(n) est ln n + 2γ.

Problème des diviseurs de Dirichlet

La recherche des valeurs de ${\displaystyle \beta \leqslant {\tfrac {1}{2}}}$ telles que

${\displaystyle \sum _{1\leqslant n\leqslant x}d(n)=x\ln x+(2\gamma -1)x+O(x^{\beta })}$

constitue le « problème des diviseurs de Dirichlet (en) »[3].

Des avancées ont été effectuées par Gueorgui Voronoï (1903, O(√x) remplacé par O(^3√x log(x))[10], Johannes van der Corput (1922, β = 33/100)[11], ainsi que Martin Huxley (de) (2003, β = 131/416)[12]. À l'opposé, Godfrey Harold Hardy et Edmund Landau ont démontré[13] que β est nécessairement supérieur ou égal à 1/4. Les valeurs possibles pour β font toujours l'objet de recherches.

Application à la différence du nombre de diviseurs pairs et du nombre de diviseurs impairs

Posons ${\textstyle {\text{u}}(n)=\sum _{d|n}(-1)^{d}={\text{dp}}(n)-{\text{di}}(n)}$ où ${\displaystyle {\text{dp}}(n)}$ est le nombre de diviseurs pairs de ${\displaystyle n}$ et ${\displaystyle {\text{di}}(n)}$ celui des diviseurs impairs ; la suite ${\displaystyle (-{\text{u}}(n))}$ est répertoriée comme suite A048272 de l'OEIS.

On a alors l'identité : ${\displaystyle \sum _{k=1}^{n}{\text{u}}(k)=\sum _{d=1}^{n}(-1)^{d}\left\lfloor {\frac {n}{d}}\right\rfloor }$ qui, combinée avec la valeur de la série harmonique alternée ${\displaystyle \sum _{d=1}^{\infty }{\frac {(-1)^{d}}{d}}=-\ln 2}$,

donne la convergence au sens de Cesàro de ${\displaystyle ({\text{u}}(n))}$ vers ${\displaystyle -\ln 2}$ .

La formule de Dirichlet permet d'obtenir plus précisément : ${\displaystyle {\frac {\sum _{k=1}^{n}{\text{u}}(k)}{n}}=-\ln 2+O(1/{\sqrt {n}})}$.

Démonstration

Comme ${\displaystyle {\text{d}}(n)={\text{dp}}(n)+{\text{di}}(n)}$, ${\displaystyle {\text{u}}(n)=2{\text{dp}}(n)-{\text{d}}(n)}$, donc ${\displaystyle \sum _{k=1}^{n}{\text{u}}(k)=2\sum _{k=1}^{n}{\text{dp}}(k)-\sum _{k=1}^{n}{\text{d}}(k)}$.

Or ${\displaystyle {\text{dp}}(2k)={\text{d}}(k)}$ et ${\displaystyle {\text{dp}}(2k+1)=0}$ , donc ${\displaystyle \sum _{k=1}^{n}{\text{dp}}(k)=\sum _{1\leqslant k\leqslant n/2}{\text{d}}(k)}$.

Par la formule de Dirichlet : ${\displaystyle \sum _{1\leqslant k\leqslant x}{\text{d}}(k)=x\ln x+(2\gamma -1)x+O({\sqrt {x}})}$, on obtient alors :

${\displaystyle \sum _{k=1}^{n}{\text{u}}(k)=2\left((n/2)\ln(n/2)+(2\gamma -1)n/2\right)-\left(n\ln n+(2\gamma -1)n\right)+O({\sqrt {n}})}$, qui se simplifie en

${\displaystyle \sum _{k=1}^{n}{\text{u}}(k)=-n\ln 2+O({\sqrt {n}})}$.

Plus petit entier ayant un nombre prescrit de diviseurs

Notons ${\displaystyle n_{\min }(m)}$ le plus petit ${\displaystyle n}$ tel que ${\displaystyle {\text{d}}(n)=m}$ ; la suite ${\displaystyle (n_{\min }(m))_{m}}$ est répertoriée comme suite A005179 de l'OEIS.

Le tableau suivant en donne les 36 premiers termes.

Plus petit entier ayant un nombre prescrit de diviseurs

${\displaystyle n_{\min }(m)}$ : plus petit ${\displaystyle n}$ ayant ${\displaystyle m}$ diviseurs[14].

Nombre ${\displaystyle m}$ de diviseurs	${\displaystyle n_{\min }(m)}$	Factorisation de ${\displaystyle n_{\min }(m)}$
1	1	1
2	2	2
3	4	2^2
4	6	2·3
5	16	2^4
6	12	2^2·3
7	64	2^6
8	24	2^3·3
9	36	2^2·3^2
10	48	2^4·3
11	1 024	2^10
12	60	2^2·3·5
13	4 096	2^12
14	192	2^6·3
15	144	2^4·3^2
16	120	2^3·3·5
17	65 536	2^16
18	180	2^2·3^2·5
19	262 144	2^18
20	240	2^4·3·5
21	576	2^6·3^2
22	3 072	2^10·3
23	4 194 304	2^22
24	360	2^3·3^2·5
25	1 296	2^4·3^4
26	12 288	2^12·3
27	900	2^2·3^2·5^2
28	960	2^6·3·5
29	268 435 456	2^28
30	720	2^4·3^2·5
31	1 073 741 824	2^30
32	840	2^3·3·5·7
33	9 216	2^10·3^2
34	196 608	2^16·3
35	5 184	2^6·3^4
36	1 260	2^2·3^2·5·7

 

Nota 1 : Pour p,q premiers tels que ${\displaystyle p\leqslant q}$, ${\displaystyle n_{\min }(p)=2^{p-1}}$ et ${\displaystyle n_{\min }(pq)=2^{q-1}3^{p-1}}$.

Nota 2 : si ${\displaystyle n_{\min }(m)}$ n'a pas de successeur plus petit que lui, alors il est hautement composé.

Généralisation

La fonction ${\displaystyle \sigma _{k}}$ associe à tout naturel non nul la somme des puissances ${\displaystyle k}$-ièmes de ses diviseurs :

${\displaystyle \sigma _{k}(n)=\sum _{d\mid n}d^{k}}$

La fonction nombre de diviseurs est donc le cas particulier de cette fonction obtenu pour ${\displaystyle k=0}$ :

${\displaystyle \sigma _{0}(n)=\sum _{d\mid n}d^{0}=\sum _{d\mid n}1={\text{d}}(n)}$.

Notes et références

(de) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en allemand intitulé « Teileranzahlfunktion » (voir la liste des auteurs).

1. Pour plus de valeurs, voir la suite A000005 de l'OEIS.
2. Pierre Eymard et Jean-Pierre Lafon, Autour du nombre Pi, Hermann, p. 25-29
3. Olivier Bordellès, « Le problème des diviseurs de Dirichlet », Quadrature, n^o 71,‎ 2009, p. 21-30 (lire en ligne).
4. Gérald Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, Dunod, chap. 1.3 (« Sur les ordres moyens, en illustration du principe de l'hyperbole de Dirichlet »)
5. (en) G. H. Hardy et E. M. Wright, An Introduction to the Theory of Numbers (1^re éd. 1938) [détail des éditions], 4^e éd., 1975, p. 239, Th. 273.
6. Hardy Wright, p. 250, Th. 289.
7. Hardy Wright, p. 264, Th. 320.
8. G.H. Hardy et E.M. Wright (trad. François Sauvageot), Introduction à la théorie des nombres, Vuibert Springer, mai 2007, chap. XVIII, section 18.2, théorème 320, p. 339
9. (de) P. G. L. Dirichlet, « Über die Bestimmung der mittleren Werthe in der Zahlentheorie », Abhandl. König. Preuss. Akad. Wiss.,‎ 1849, p. 69-83 ou (de) P. G. L. Dirichlet, Werke, t. II, 49-66 p..
10. G. Voronoï, « Sur un problème du calcul des fonctions asymptotiques », J. reine angew. Math., vol. 126,‎ 1903, p. 241-282 (lire en ligne).
11. (de) J. G. van der Corput, « Verschärfung der Abschätzung beim Teilerproblem », Mathematische Annalen, vol. 87,‎ 1922, p. 39-65. « —, Corrections », vol. 89, 1923, p. 160.
12. (en) M. N. Huxley, « Exponential Sums and Lattice Points III », Proc. London Math. Soc., vol. 87, n^o 3,‎ 2003, p. 591-609.
13. (en) G. H. Hardy, « On Dirichlet’s divisor problem », Proc. Lond. Math. Soc. (2), vol. 15,‎ 1915, p. 1-25. Cf. Hardy Wright, p. 272.
14. Les deux premières colonnes sont extraites de la suite A005179 de l'OEIS. Pour ${\displaystyle p,q}$ premiers tels que ${\displaystyle p\leq q}$, ${\displaystyle n_{\min }(p)=2^{p-1}}$ et ${\displaystyle n_{\min }(pq)=2^{q-1}3^{p-1}}$.

Articles connexes

• Nombre parfait
• Nombre hautement composé
• Suite aliquote, suite où chaque nombre est la somme des diviseurs propres de son prédécesseur.
• Constante d'Erdős-Borwein égale à ${\displaystyle \sum _{n=1}^{\infty }{\frac {{\text{d}}(n)}{2^{n}}}}$.