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é¶
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\)