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 $n$ , en incluant parmi les diviseurs de $n$ les nombres 1 et $n$ . Elle est généralement notée ${\text{d}}$ ou $\tau$ (de l'allemand Teiler : diviseur), ou encore $\sigma _{0}$ , comme cas particulier de fonction somme des puissances k-ièmes des diviseurs.

Définition

Pour tout nombre naturel $n$ on définit :

{\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ù

d|n

indique la divisibilité de

n

par

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 : $\sum _{k=1}^{n}{\text{d}}(k)=\sum _{d=1}^{n}\left\lfloor {\frac {n}{d}}\right\rfloor$ où $\left\lfloor \,.\right\rfloor$ désigne la fonction partie entière^[2]^,^[3]^,^[4] :

Démonstration

$\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 $n$ est
$n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\dots p_{r}^{\alpha _{r}}$ ,

alors^[5] :
${\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 $m$ et $n$ sont premiers entre eux, alors :
${\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.
${\text{d}}(n)$ est le double du nombre de diviseurs de $n$ entre 1 et $\sqrt n$ , auquel il faut retrancher 1 si $n$ est un carré parfait, donc un majorant de $d(n)$ est $2 \sqrt n$ .
La fonction génératrice de $(d(n))$ s'exprime comme série de Lambert :
$\sum _{n=1}^{\infty }{\text{d}}(n)x^{n}=\sum _{n=1}^{\infty }{\frac {x^{n}}{1-x^{n}}}$ (pour $\operatorname {Re} (s)>1$ )
La série de Dirichlet de $(d(n))$ est le carré de la fonction zêta de Riemann^[6] :
$\sum _{n=1}^{\infty }{\frac {{\text{d}}(n)}{n^{s}}}=\zeta ^{2}(s)$ (pour $\operatorname {Re} (s)>1$ )

Comportement asymptotique

Formule de Dirichlet

Représentation en bâtons de

d(n)

; en rouge, de

{\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 $n$ premier, et prend aussi des valeurs arbitrairement grandes (par exemple $N + 1$ pour $n = 2 N$ ) . Mais en moyenne de Cesàro : ${\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}\sim \ln n$ .

Ceci vient de la formule $\sum _{k=1}^{n}{\text{d}}(k)=\sum _{k=1}^{n}\left\lfloor {\frac {n}{k}}\right\rfloor$ , dont on déduit : $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 :

$\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]

{\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 $\beta \leqslant {\tfrac {1}{2}}$ telles que

\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 (\sqrt x)$ remplacé par $O (3 \sqrt 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ù ${\text{dp}}(n)$ est le nombre de diviseurs pairs de $n$ et ${\text{di}}(n)$ celui des diviseurs impairs ; la suite $(-{\text{u}}(n))$ est répertoriée comme suite A048272 de l'OEIS.

On a alors l'identité : $\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 $\sum _{d=1}^{\infty }{\frac {(-1)^{d}}{d}}=-\ln 2$ ,

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

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

Démonstration

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

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

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

$\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

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

Plus petit entier ayant un nombre prescrit de diviseurs

Notons $n_{\min }(m)$ le plus petit $n$ tel que ${\text{d}}(n)=m$ ; la suite $(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

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

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

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

Généralisation

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

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

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

\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).

↑ Pour plus de valeurs, voir la suite A000005 de l'OEIS.
↑ ^{a et b} Pierre Eymard et Jean-Pierre Lafon, Autour du nombre Pi, Hermann, p. 25-29
↑ ^{a et b} Olivier Bordellès, « Le problème des diviseurs de Dirichlet », Quadrature, n^o 71,‎ 2009, p. 21-30 (lire en ligne).
↑ ^{a et b} 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 »)
↑ (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.
↑ Hardy Wright, p. 250, Th. 289.
↑ Hardy Wright, p. 264, Th. 320.
↑ 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
↑ (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..
↑ G. Voronoï, « Sur un problème du calcul des fonctions asymptotiques », J. reine angew. Math., vol. 126,‎ 1903, p. 241-282 (lire en ligne).
↑ (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.
↑ (en) M. N. Huxley, « Exponential Sums and Lattice Points III », Proc. London Math. Soc., vol. 87, n^o 3,‎ 2003, p. 591-609.
↑ (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.
↑ Les deux premières colonnes sont extraites de la suite A005179 de l'OEIS. Pour $p,q$ premiers tels que $p\leq q$ , $n_{\min }(p)=2^{p-1}$ et $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 à $\sum _{n=1}^{\infty }{\frac {{\text{d}}(n)}{2^{n}}}$ .

Arithmétique et théorie des nombres

[1] Pour plus de valeurs, voir la suite A000005 de l'OEIS.

[:0-2] {a et b} Pierre Eymard et Jean-Pierre Lafon, Autour du nombre Pi, Hermann, p. 25-29

[:1-3] {a et b} Olivier Bordellès, « Le problème des diviseurs de Dirichlet », Quadrature, n^o 71,‎ 2009, p. 21-30 (lire en ligne).

[:2-4] {a et b} 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 $p,q$ premiers tels que $p\leq q$ , $n_{\min }(p)=2^{p-1}$ et $n_{\min }(pq)=2^{q-1}3^{p-1}$ .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]