# 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 :
| 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$^,$$^,$ :
$\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 :
       ${\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 √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 :
    $\sum _{n=1}^{\infty }{\text{d}}(n)s^{n}=\sum _{n=1}^{\infty }{\frac {s^{n}}{1-s^{n}}}$ (pour $\operatorname {Re} (s)>1$)
* La série de Dirichlet de (d(n)) est le carré de la fonction zêta de Riemann :
    $\sum _{n=1}^{\infty }{\frac {{\text{d}}(n)}{n^{s}}}=\zeta ^{2}(s)$ (pour $\operatorname {Re} (s)>1$)

## Comportement asymptotique
### Formule de Dirichlet

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$.
Un développement plus précis est donné par$^,$$^,$$^,$
    ${\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.
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) ».
Des avancées ont été effectuées par Gueorgui Voronoï (1903, O(√x) remplacé par O($^3$√x log(x)), Johannes van der Corput (1922, β = 33/100), ainsi que Martin Huxley (de) (2003, β = 131/416). À l'opposé, Godfrey Harold Hardy et Edmund Landau ont démontré 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ù ${\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}})$.
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.
$n_{\min }(m)$ : plus petit $n$ ayant $m$ diviseurs. :
| Nombre $m$ de diviseurs | $n_{\min }(m)$ | Factorisation de $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 $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)$.