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 d ou τ (de l'allemand Teiler : diviseur), ou encore σ0, comme cas particulier de fonction somme des puissances k-ièmes des diviseurs.

Définition

Pour tout nombre naturel n on définit :

d ( n ) = card ⁡ ( { d ∈ N  ;  1 ⩽ d ⩽ n   et   d | n } ) = ∑ d | n 1 {\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ù d | n {\displaystyle d|n} indique la divisibilité de n {\displaystyle n} par d {\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 : ∑ k = 1 n d ( k ) = ∑ d = 1 n ⌊ n d ⌋ {\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


∑ k = 1 n d ( k ) = ∑ k = 1 n ∑ d | k 1 = ∑ d = 1 n ∑ 1 ⩽ k ⩽ n d | k 1 = ∑ d = 1 n ⌊ n d ⌋ . {\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 n est
    n = p 1 α 1 p 2 α 2 … p r α r {\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\dots p_{r}^{\alpha _{r}}} ,
    alors[5] :
    d ( n ) = ( α 1 + 1 ) ( α 2 + 1 ) … ( α r + 1 ) {\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 m et n sont premiers entre eux, alors :
    d ( m n ) = d ( m ) d ( n ) {\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.
  • d ( n ) {\displaystyle {\text{d}}(n)} est le double du nombre de diviseurs de n entre 1 et √n, auquel il faut retrancher 1 si 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 :
    ∑ n = 1 ∞ d ( n ) x n = ∑ n = 1 ∞ x n 1 − x n {\displaystyle \sum _{n=1}^{\infty }{\text{d}}(n)x^{n}=\sum _{n=1}^{\infty }{\frac {x^{n}}{1-x^{n}}}} (pour Re ⁡ ( s ) > 1 {\displaystyle \operatorname {Re} (s)>1} )
  • La série de Dirichlet de (d(n)) est le carré de la fonction zêta de Riemann[6] :
    ∑ n = 1 ∞ d ( n ) n s = ζ 2 ( s ) {\displaystyle \sum _{n=1}^{\infty }{\frac {{\text{d}}(n)}{n^{s}}}=\zeta ^{2}(s)} (pour Re ⁡ ( s ) > 1 {\displaystyle \operatorname {Re} (s)>1} )

Comportement asymptotique

Formule de Dirichlet

Représentation en bâtons de d(n) ; en rouge, de ∑ k = 1 n d ( k ) n {\displaystyle {\frac {\sum _{k=1}^{n}d(k)}{n}}}  ; en bleu, de Hn-1 et Hn ; 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 = 2N) . Mais en moyenne de Cesàro : ∑ k = 1 n d ( k ) n ∼ ln ⁡ n {\displaystyle {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}\sim \ln n} .

Ceci vient de la formule ∑ k = 1 n d ( k ) = ∑ k = 1 n ⌊ n k ⌋ {\displaystyle \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 ⩽ ∑ k = 1 n d ( k ) n ⩽ H n {\displaystyle H_{n}-1\leqslant {\frac {\sum _{k=1}^{n}{\text{d}}(k)}{n}}\leqslant H_{n}} où (Hn) est la série harmonique, puis l'encadrement :

ln ⁡ n − 1 ⩽ ∑ k = 1 n d ( k ) n ⩽ ln ⁡ n + 1 {\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]

∑ k = 1 n d ( k ) n = ln ⁡ n + 2 γ − 1 + O ( 1 / n ) {\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 β ⩽ 1 2 {\displaystyle \beta \leqslant {\tfrac {1}{2}}} telles que

∑ 1 ⩽ n ⩽ x d ( n ) = x ln ⁡ x + ( 2 γ − 1 ) x + O ( x β ) {\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 u ( n ) = ∑ d | n ( − 1 ) d = dp ( n ) − di ( n ) {\textstyle {\text{u}}(n)=\sum _{d|n}(-1)^{d}={\text{dp}}(n)-{\text{di}}(n)} où dp ( n ) {\displaystyle {\text{dp}}(n)} est le nombre de diviseurs pairs de n et di ( n ) {\displaystyle {\text{di}}(n)} celui des diviseurs impairs ; la suite ( − u ( n ) ) {\displaystyle (-{\text{u}}(n))} est répertoriée comme suite A048272 de l'OEIS.

On a alors l'identité : ∑ k = 1 n u ( k ) = ∑ d = 1 n ( − 1 ) d ⌊ n d ⌋ {\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 ∑ d = 1 ∞ ( − 1 ) d d = − ln ⁡ 2 {\displaystyle \sum _{d=1}^{\infty }{\frac {(-1)^{d}}{d}}=-\ln 2} ,

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

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

Démonstration


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

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

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

∑ k = 1 n u ( k ) = 2 ( ( n / 2 ) ln ⁡ ( n / 2 ) + ( 2 γ − 1 ) n / 2 ) − ( n ln ⁡ n + ( 2 γ − 1 ) n ) + O ( n ) {\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

∑ k = 1 n u ( k ) = − n ln ⁡ 2 + O ( n ) {\displaystyle \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 ) {\displaystyle n_{\min }(m)} le plus petit n tel que d ( n ) = m {\displaystyle {\text{d}}(n)=m}  ; la suite ( n min ( m ) ) m {\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
n min ( m ) {\displaystyle n_{\min }(m)}  : plus petit n {\displaystyle n} ayant m {\displaystyle m} diviseurs[14].
Nombre m {\displaystyle m} de diviseurs n min ( m ) {\displaystyle n_{\min }(m)} Factorisation de n min ( m ) {\displaystyle n_{\min }(m)}
1 1 1
2 2 2
3 4 22
4 6 2·3
5 16 24
6 12 22·3
7 64 26
8 24 23·3
9 36 22·32
10 48 24·3
11 1 024 210
12 60 22·3·5
13 4 096 212
14 192 26·3
15 144 24·32
16 120 23·3·5
17 65 536 216
18 180 22·32·5
19 262 144 218
20 240 24·3·5
21 576 26·32
22 3 072 210·3
23 4 194 304 222
24 360 23·32·5
25 1 296 24·34
26 12 288 212·3
27 900 22·32·52
28 960 26·3·5
29 268 435 456 228
30 720 24·32·5
31 1 073 741 824 230
32 840 23·3·5·7
33 9 216 210·32
34 196 608 216·3
35 5 184 26·34
36 1 260 22·32·5·7
 

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

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

Généralisation

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

σ k ( n ) = ∑ d ∣ n d k {\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 k = 0 {\displaystyle k=0}  :

σ 0 ( n ) = ∑ d ∣ n d 0 = ∑ d ∣ n 1 = d ( n ) {\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. ↑ a et b Pierre Eymard et Jean-Pierre Lafon, Autour du nombre Pi, Hermann, p. 25-29
  3. ↑ a et b Olivier Bordellès, « Le problème des diviseurs de Dirichlet », Quadrature, no 71,‎ , p. 21-30 (lire en ligne).
  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 (1re éd. 1938) [détail des éditions], 4e é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, , 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.,‎ , 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,‎ , p. 241-282 (lire en ligne).
  11. ↑ (de) J. G. van der Corput, « Verschärfung der Abschätzung beim Teilerproblem », Mathematische Annalen, vol. 87,‎ , 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, no 3,‎ , p. 591-609.
  13. ↑ (en) G. H. Hardy, « On Dirichlet’s divisor problem », Proc. Lond. Math. Soc. (2), vol. 15,‎ , 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 {\displaystyle p,q} premiers tels que p ≤ q {\displaystyle p\leq q} , n min ( p ) = 2 p − 1 {\displaystyle n_{\min }(p)=2^{p-1}} et n min ( p q ) = 2 q − 1 3 p − 1 {\displaystyle n_{\min }(pq)=2^{q-1}3^{p-1}} .

Articles connexes

  • icône décorative Arithmétique et théorie des nombres