Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs¶
Domaine : Théorie des nombres · Niveau : intermédiaire · Prérequis : Divisibilité, PGCD, Congruences
L'idée¶
Trois fonctions reviennent sans cesse. Pour un entier \(n \geq 1\) :
- \(\tau(n)\) (aussi noté \(d(n)\)) est le nombre de diviseurs positifs de \(n\) ;
- \(\sigma(n)\) est la somme des diviseurs positifs de \(n\) ;
- \(\varphi(n)\) est l'indicatrice d'Euler : le nombre d'entiers \(m\) entre \(1\) et \(n\) premiers avec \(n\).
Toutes les trois se calculent à partir de la décomposition \(n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}\) :
Par exemple, \(12 = 2^2 \times 3\) a \(\tau(12) = 3 \times 2 = 6\) diviseurs, de somme \(\sigma(12) = 7 \times 4 = 28\), et \(\varphi(12) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4\) (ce sont \(1, 5, 7, 11\)).
Pourquoi. Un diviseur de \(n\) s'écrit \(p_1^{\beta_1} \cdots p_k^{\beta_k}\) avec \(0 \leq \beta_i \leq \alpha_i\) : il y a \(\alpha_i + 1\) choix pour chaque exposant, d'où \(\tau\). En développant le produit \(\prod (1 + p_i + \cdots + p_i^{\alpha_i})\), chaque diviseur apparaît exactement une fois, d'où \(\sigma\).
Fonctions multiplicatives¶
Une fonction \(f\) est multiplicative si \(f(1) = 1\) et \(f(mn) = f(m) f(n)\) dès que \(m\) et \(n\) sont premiers entre eux. C'est le cas de \(\tau\), \(\sigma\) et \(\varphi\) (pour \(\varphi\), c'est le théorème des restes chinois). Une fonction multiplicative est entièrement déterminée par ses valeurs sur les puissances de premiers, et l'on a la formule
Une fonction est complètement additive si \(f(ab) = f(a) + f(b)\) pour tous \(a, b\) : c'est le cas de la valuation \(v_p\) et du nombre \(\Omega(n)\) de facteurs premiers comptés avec multiplicité.
Quelques faits à connaître¶
| Fait | Pourquoi |
|---|---|
| \(\tau(n)\) est impair si et seulement si \(n\) est un carré | Les diviseurs vont par paires \(\{d, \frac{n}{d}\}\), sauf \(d = \sqrt{n}\) |
| \(\tau(n) \leq 2\sqrt{n}\) | Dans chaque paire, l'un des deux diviseurs est \(\leq \sqrt{n}\) |
| Le produit des diviseurs de \(n\) vaut \(n^{\tau(n)/2}\) | Même appariement |
| \(\sum_{d \mid n} \varphi(d) = n\) (Gauss) | Classer les entiers de \(1\) à \(n\) selon leur PGCD avec \(n\) |
| \(v_p(n!) = \sum_{j \geq 1} \left\lfloor \frac{n}{p^j} \right\rfloor\) (Legendre) | Voir Partie entière |
Exemple résolu¶
Problème
Trouver tous les entiers \(n \geq 1\) tels que \(n = \tau(n)^2\).
Étape 1 : deviner. \(n = 1\) convient, et \(\tau(9) = 3\) donne \(9 = 3^2\). On va montrer qu'il n'y en a pas d'autre.
Étape 2 : \(n\) est un carré impair. L'égalité montre que \(n\) est un carré, donc \(\tau(n)\) est impair (voir le tableau). Alors \(\sqrt{n} = \tau(n)\) est impair, donc \(n\) aussi.
Étape 3 : comparer facteur par facteur. Écrivons \(n = p_1^{2a_1} \cdots p_k^{2a_k}\), avec des premiers \(p_i \geq 3\) et des \(a_i \geq 1\). L'égalité \(\tau(n) = \sqrt{n}\) s'écrit
Étape 4 : chaque facteur est au plus \(1\). Pour \(p \geq 3\) et \(a \geq 1\), on a \(p^a \geq 3^a \geq 2a + 1\) : la seconde inégalité se montre par récurrence, car \(3^{a+1} = 3 \cdot 3^a \geq 6a + 3 \geq 2a + 3\). L'égalité n'a lieu que pour \(p = 3\) et \(a = 1\).
Conclusion. Un produit de facteurs tous \(\leq 1\) vaut \(1\) seulement si chaque facteur vaut \(1\). Donc soit \(k = 0\) et \(n = 1\), soit \(n = 3^2 = 9\). Les solutions sont \(n = 1\) et \(n = 9\).
Le réflexe : pour une équation reliant \(n\) et \(\tau(n)\) (ou \(\sigma(n)\), \(\varphi(n)\)), écrire la décomposition et comparer premier par premier, en étudiant le rapport \(\frac{f(p^a)}{p^a}\).
Comment le reconnaître¶
- L'énoncé parle du nombre de diviseurs, de leur somme, ou du nombre d'entiers premiers avec \(n\).
- Une équation fait intervenir \(n\) et \(\tau(n)\), \(\sigma(n)\) ou \(\varphi(n)\).
- On somme une quantité sur les diviseurs de \(n\).
- On demande la plus grande puissance de \(p\) qui divise \(n!\) ou un coefficient binomial.
- Une fonction vérifie \(f(ab) = f(a) + f(b)\) ou \(f(ab) = f(a) f(b)\).
Techniques classiques¶
| Situation | Technique |
|---|---|
| Calculer \(\tau\), \(\sigma\) ou \(\varphi\) | Décomposer en facteurs premiers et appliquer les formules |
| Équation entre \(n\) et \(\tau(n)\), \(\sigma(n)\) ou \(\varphi(n)\) | Comparer premier par premier : le rapport \(\frac{f(p^a)}{p^a}\) est souvent \(\leq 1\) (exemple résolu) |
| Propriété de tous les diviseurs | Apparier \(d\) et \(\frac{n}{d}\) |
| Somme \(\sum_{d \mid n} f(d)\) avec \(f\) multiplicative | La factoriser en produit sur les premiers |
| Valuation de \(n!\) ou de \(\binom{n}{k}\) | Formule de Legendre |
| Fonction complètement additive (\(v_p\), \(\Omega\)) | Étudier sa parité ; elle passe au quotient : \(f\left(\frac{a}{d}\right) = f(a) - f(d)\) |
Exercices d'échauffement¶
- Calculer \(\tau(360)\), \(\sigma(360)\) et \(\varphi(360)\).
- Montrer que \(\tau(n)\) est impair si et seulement si \(n\) est un carré parfait.
- Montrer que le produit des diviseurs positifs de \(n\) vaut \(n^{\tau(n)/2}\).
- Montrer que \(\sum_{d \mid n} \varphi(d) = n\). Indication : combien d'entiers \(m \leq n\) vérifient \(\operatorname{pgcd}(m, n) = d\) ?
- Montrer que si \(24\) divise \(n + 1\), alors \(24\) divise \(\sigma(n)\). Indication : apparier \(a\) et \(b = \frac{n}{a}\), et utiliser \(x^2 \equiv 1 \pmod{24}\) pour \(x\) premier avec \(6\).
Fonctions arithmétiques dans la shortlist¶
- 2018 N1 : avec la formule de \(\tau\), on cherche \(s\) qui rende \(\prod \frac{\alpha_i + \gamma_i + 1}{\beta_i + \gamma_i + 1}\) égal à \(1\).
- 2016 N2 : on écrit une formule produit pour \(\tau\) et pour le nombre de diviseurs \(\equiv 1 \pmod 3\).
- 2016 C2, solution 2 : on compare \(\tau(n)\) et \(\sigma(n)\) premier par premier.
- 2020 N6 : on choisit \(n\) pour que \(d(n)\) soit une puissance de \(2\) et que \(\varphi(n)\) n'ait que de petits facteurs premiers.
- 2022 N6 : les fonctions étudiées sont complètement additives, ce qui permet de diviser par un facteur commun.
- 2023 N8, solution 4 : une bijection qui respecte la divisibilité conserve \(\tau\), donc envoie les premiers sur les premiers.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 5 (M. Aassila), p. 181 et 182 (fonctions multiplicatives, avec les exemples de Sierpiński et de Liouville), p. 183 à 186 (fonction de Möbius, indicatrice d'Euler, théorème de Gauss), p. 187 à 189 (formule de Legendre), p. 189 à 194 (exercices), p. 195 (formules de \(\tau\) et \(\sigma\)).
Problèmes de la shortlist¶
12 problèmes · difficulté moyenne : ★★★★★ (3,2) · dont 1 choisi pour l'OIM
Répartition par difficulté : 1 ★ : 3 · 2 ★ : 2 · 3 ★ : 0 · 4 ★ : 3 · 5 ★ : 4
| Problème | Difficulté | Concepts |
|---|---|---|
| 2018 N1 | ★☆☆☆☆ | - |
| 2016 C2 | ★☆☆☆☆ | Principe extrémal · Divisibilité, PGCD et algorithme d'Euclide |
| 2016 N2 | ★☆☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2011 N1 | ★★☆☆☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2006 N3 | ★★☆☆☆ | Partie entière et majorations |
| 2022 N6 | ★★★★☆ | Principe des tiroirs |
| 2020 N6 | ★★★★☆ | AM-GM et moyennes |
| 2008 N5 | ★★★★☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2023 N8 | ★★★★★ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide · Théorème des restes chinois |
| 2014 N8 | ★★★★★ | Valuations p-adiques et lemme LTE · Partie entière et majorations |
| 2013 C7 · OIM P6 | ★★★★★ | Bijections et dénombrement · Récurrence et constructions récursives |
| 2013 N7 | ★★★★★ | Partie entière et majorations · Récurrence et constructions récursives · Bijections et dénombrement |