Shortlist 2011, N1¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 63 (page 64 du PDF)
Énoncé¶
Pour tout entier \(d > 0\), on note \(f(d)\) le plus petit entier strictement positif ayant exactement \(d\) diviseurs positifs (ainsi, par exemple, \(f(1) = 1\), \(f(5) = 16\) et \(f(6) = 12\)). Montrer que, pour tout entier \(k \geq 0\), le nombre \(f(2^k)\) divise \(f(2^{k+1})\).
Énoncé original (anglais)
For any integer \(d > 0\), let \(f(d)\) be the smallest positive integer that has exactly \(d\) positive divisors (so for example we have \(f(1) = 1\), \(f(5) = 16\), and \(f(6) = 12\)). Prove that for every integer \(k \geq 0\) the number \(f(2^k)\) divides \(f(2^{k+1})\).
Indices : les idées clés
- Nombre de diviseurs : \(d(n) = \prod_p (a(p) + 1)\) est une puissance de \(2\) si et seulement si chaque exposant est de la forme \(a(p) = 2^{b(p)} - 1 = 1 + 2 + \cdots + 2^{b(p)-1}\).
- Briques élémentaires : un tel \(n\) est le produit d'un ensemble \(\mathcal{T}\) de nombres \(p^{2^r}\) (premiers), stable par passage aux diviseurs de cette forme, et \(d(n) = 2^{\lvert \mathcal{T} \rvert}\).
- Choix glouton : \(f(2^k)\) est le produit des \(k\) plus petits éléments de \(\mathcal{S} = \{p^{2^r}\}\), et \(\mathcal{T}_k \subset \mathcal{T}_{k+1}\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2011 (deux solutions).
Solution 1¶
Pour tout entier \(n > 0\), notons \(d(n)\) le nombre de diviseurs positifs de \(n\). Soit \(n = \prod_p p^{a(p)}\) la décomposition en facteurs premiers de \(n\), où \(p\) parcourt les nombres premiers, les entiers \(a(p)\) sont positifs ou nuls et tous nuls sauf un nombre fini. Alors \(d(n) = \prod_p (a(p) + 1)\). Ainsi, \(d(n)\) est une puissance de \(2\) si et seulement si, pour tout nombre premier \(p\), il existe un entier \(b(p) \geq 0\) tel que \(a(p) = 2^{b(p)} - 1 = 1 + 2 + 2^2 + \cdots + 2^{b(p)-1}\). On a alors
Soit \(\mathcal{S}\) l'ensemble de tous les nombres de la forme \(p^{2^r}\) avec \(p\) premier et \(r\) entier positif ou nul. On en déduit que \(d(n)\) est une puissance de \(2\) si et seulement si \(n\) est le produit des éléments d'une partie finie \(\mathcal{T}\) de \(\mathcal{S}\) qui vérifie la condition suivante : pour tous \(t \in \mathcal{T}\) et \(s \in \mathcal{S}\) avec \(s \mid t\), on a \(s \in \mathcal{T}\). De plus, si \(d(n) = 2^k\), l'ensemble \(\mathcal{T}\) correspondant a \(k\) éléments.
Remarquons que l'ensemble \(\mathcal{T}_k\) formé des \(k\) plus petits éléments de \(\mathcal{S}\) vérifie évidemment cette condition. Ainsi, pour \(k\) donné, le plus petit \(n\) tel que \(d(n) = 2^k\) est le produit des éléments de \(\mathcal{T}_k\). Ce \(n\) est \(f(2^k)\). Comme évidemment \(\mathcal{T}_k \subset \mathcal{T}_{k+1}\), il s'ensuit que \(f(2^k) \mid f(2^{k+1})\). \(\blacksquare\)
Solution 2¶
Voici une alternative à la seconde partie de la solution 1. Soit \(k\) un entier positif ou nul. D'après la première partie de la solution 1, \(f(2^k) = \prod_p p^{a(p)}\) avec \(a(p) = 2^{b(p)} - 1\) et \(\sum_p b(p) = k\). Montrons que, pour deux nombres premiers distincts \(p\), \(q\) avec \(b(q) > 0\), on a
Pour le voir, remarquons d'abord que \(\ell\) divise \(f(2^k)\). D'après la première partie de la solution 1, l'entier \(n = f(2^k)m/\ell\) vérifie aussi \(d(n) = 2^k\). Par définition de \(f(2^k)\), cela implique \(n \geq f(2^k)\), donc \(m \geq \ell\). Comme \(p \neq q\), l'inégalité (1) en découle.
Soit \(f(2^{k+1}) = \prod_p p^{r(p)}\) la décomposition en facteurs premiers de \(f(2^{k+1})\), avec \(r(p) = 2^{s(p)} - 1\). Comme \(\sum_p s(p) = k + 1 > k = \sum_p b(p)\), il existe un nombre premier \(p\) tel que \(s(p) > b(p)\). Pour tout nombre premier \(q \neq p\) avec \(b(q) > 0\), on applique deux fois l'inégalité (1) (une fois pour \(f(2^{k+1})\), une fois pour \(f(2^k)\)) et l'on obtient
ce qui implique \(s(q) \geq b(q)\). Il s'ensuit que \(s(q) \geq b(q)\) pour tout nombre premier \(q\), donc \(f(2^k) \mid f(2^{k+1})\). \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2018 N1 ★☆☆☆☆ : Pour quels couples \((n, k)\) un multiplicateur commun \(s\) donne-t-il à \(sn\) et \(sk\) le même nombre de diviseurs ?
- 2016 N2 ★☆☆☆☆ : Quelles valeurs entières peut prendre le rapport entre le nombre de diviseurs de \(10n\) et ceux qui sont congrus à \(1\) modulo \(3\) ?
- 2006 N3 ★★☆☆☆ : La moyenne \(\frac{1}{n}\sum \lfloor n/k \rfloor\) augmente une infinité de fois et diminue une infinité de fois.
- 2008 N5 ★★★★☆ : Trouver les fonctions telles que \(f(x)\) ait exactement \(x\) diviseurs, avec une condition de divisibilité sur \(f(xy)\).