Aller au contenu

Shortlist 2008, N5

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 2008 (avec solutions), p. 49 (page 50 du PDF)

Énoncé

Pour tout \(n \in \mathbb{N}\), on note \(d(n)\) le nombre de diviseurs (positifs) de \(n\). Trouver toutes les fonctions \(f : \mathbb{N} \to \mathbb{N}\) ayant les propriétés suivantes :

(i) \(d(f(x)) = x\) pour tout \(x \in \mathbb{N}\) ;

(ii) \(f(xy)\) divise \((x - 1)y^{xy-1}f(x)\) pour tous \(x, y \in \mathbb{N}\).

Énoncé original (anglais)

For every \(n \in \mathbb{N}\) let \(d(n)\) denote the number of (positive) divisors of \(n\). Find all functions \(f : \mathbb{N} \to \mathbb{N}\) with the following properties:

(i) \(d(f(x)) = x\) for all \(x \in \mathbb{N}\);

(ii) \(f(xy)\) divides \((x - 1)y^{xy-1}f(x)\) for all \(x, y \in \mathbb{N}\).

Indices : les idées clés
  • Nombre de diviseurs : \(f\) est injective, et \(d(f(p)) = p\) premier impose \(f(p) = q^{p-1}\) ; des choix \((x, y) = (2, p)\), \((p, 2)\) donnent \(q = p\), et un cas à part donne \(f(2) = 2\).
  • Facteurs premiers : avec \(x = p\) (plus petit premier divisant \(n\)) et \(y = n/p\), tout facteur premier de \(f(n)\) divise \(n\).
  • Comparaison : \(p_i^{b_i} \mid f(p_i^{a_i}) = p_i^{p_i^{a_i} - 1}\) donne \(b_i \leq p_i^{a_i} - 1\), et \(d(f(n)) = n\) force l'égalité.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution).

Réponse : il y a une unique solution, la fonction \(f : \mathbb{N} \to \mathbb{N}\) définie par \(f(1) = 1\) et

\[f(n) = p_1^{p_1^{a_1} - 1}p_2^{p_2^{a_2} - 1} \cdots p_k^{p_k^{a_k} - 1} \qquad \text{où } n = p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k} \text{ est la décomposition en facteurs premiers de } n > 1. \tag{1}\]

Solution

Une vérification directe montre que cette fonction satisfait les conditions.

Réciproquement, soit \(f : \mathbb{N} \to \mathbb{N}\) vérifiant (i) et (ii). En appliquant (i) pour \(x = 1\), on obtient \(d(f(1)) = 1\), donc \(f(1) = 1\). Dans la suite, on montre que (1) est vraie pour tout \(n > 1\). Remarquons que \(f(m) = f(n)\) implique \(m = n\), vu (i). La formule \(d\left(p_1^{b_1} \cdots p_k^{b_k}\right) = (b_1 + 1) \cdots (b_k + 1)\) sera utilisée tout du long.

Soit \(p\) un nombre premier. Comme \(d(f(p)) = p\), la formule ci-dessus donne \(f(p) = q^{p-1}\) pour un nombre premier \(q\) ; en particulier \(f(2) = q^{2-1} = q\) est un nombre premier. Montrons que \(f(p) = p^{p-1}\) pour tout nombre premier \(p\).

Supposons \(p\) impair et \(f(p) = q^{p-1}\) pour un nombre premier \(q\). En appliquant (ii) d'abord avec \(x = 2\), \(y = p\), puis avec \(x = p\), \(y = 2\), on voit que \(f(2p)\) divise à la fois \((2 - 1)p^{2p-1}f(2) = p^{2p-1}f(2)\) et \((p - 1)2^{2p-1}f(p) = (p - 1)2^{2p-1}q^{p-1}\). Si \(q \neq p\), le nombre premier impair \(p\) ne divise pas \((p - 1)2^{2p-1}q^{p-1}\), donc le plus grand diviseur commun de \(p^{2p-1}f(2)\) et \((p - 1)2^{2p-1}q^{p-1}\) est un diviseur de \(f(2)\). Donc \(f(2p)\) divise \(f(2)\), qui est premier. Comme \(f(2p) > 1\), on obtient \(f(2p) = f(2)\), ce qui est impossible. Donc \(q = p\), c'est-à-dire \(f(p) = p^{p-1}\).

Pour \(p = 2\), le même argument avec \(x = 2\), \(y = 3\) et \(x = 3\), \(y = 2\) montre que \(f(6)\) divise à la fois \(3^5f(2)\) et \(2^63^2\). Si le nombre premier \(f(2)\) est impair, alors \(f(6)\) divise \(3^2 = 9\), donc \(f(6) \in \{1, 3, 9\}\). Mais alors \(6 = d(f(6)) \in \{d(1), d(3), d(9)\} = \{1, 2, 3\}\), ce qui est faux. En conclusion, \(f(2) = 2\).

Ensuite, pour tout \(n > 1\), les diviseurs premiers de \(f(n)\) sont parmi ceux de \(n\). En effet, soit \(p\) le plus petit diviseur premier de \(n\). Appliquons (ii) avec \(x = p\) et \(y = n/p\) pour obtenir que \(f(n)\) divise \((p - 1)y^{n-1}f(p) = (p - 1)y^{n-1}p^{p-1}\). Écrivons \(f(n) = \ell P\), où \(\ell\) est premier avec \(n\) et \(P\) est un produit de nombres premiers divisant \(n\). Comme \(\ell\) divise \((p - 1)y^{n-1}p^{p-1}\) et est premier avec \(y^{n-1}p^{p-1}\), il divise \(p - 1\) ; donc \(d(\ell) \leq \ell < p\). Mais (i) donne \(n = d(f(n)) = d(\ell P)\), et \(d(\ell P) = d(\ell)d(P)\) puisque \(\ell\) et \(P\) sont premiers entre eux. Donc \(d(\ell)\) est un diviseur de \(n\) inférieur à \(p\), ce qui signifie que \(\ell = 1\) et prouve l'affirmation.

Maintenant, (1) est immédiat pour les puissances de nombres premiers. Si \(p\) est premier et \(a \geq 1\), alors d'après ce qui précède, le seul facteur premier de \(f(p^a)\) est \(p\) (il existe un facteur premier puisque \(f(p^a) > 1\)). Donc \(f(p^a) = p^b\) pour un certain \(b \geq 1\), et (i) donne \(p^a = d(f(p^a)) = d(p^b) = b + 1\). Donc \(f(p^a) = p^{p^a - 1}\), comme voulu.

Montrons enfin que (1) est vraie pour un \(n > 1\) quelconque de décomposition \(n = p_1^{a_1} \cdots p_k^{a_k}\). On a vu que la décomposition en facteurs premiers de \(f(n)\) est de la forme \(f(n) = p_1^{b_1} \cdots p_k^{b_k}\). Pour \(i = 1, \ldots, k\), posons \(x = p_i^{a_i}\) et \(y = n/x\) dans (ii) pour en déduire que \(f(n)\) divise \(\left(p_i^{a_i} - 1\right)y^{n-1}f\left(p_i^{a_i}\right)\). Donc \(p_i^{b_i}\) divise \(\left(p_i^{a_i} - 1\right)y^{n-1}f\left(p_i^{a_i}\right)\), et comme \(p_i^{b_i}\) est premier avec \(\left(p_i^{a_i} - 1\right)y^{n-1}\), il s'ensuit que \(p_i^{b_i}\) divise \(f\left(p_i^{a_i}\right) = p_i^{p_i^{a_i} - 1}\). Donc \(b_i \leq p_i^{a_i} - 1\) pour tout \(i = 1, \ldots, k\). Combinées avec (i), ces conclusions donnent

\[p_1^{a_1} \cdots p_k^{a_k} = n = d(f(n)) = d\left(p_1^{b_1} \cdots p_k^{b_k}\right) = (b_1 + 1) \cdots (b_k + 1) \leq p_1^{a_1} \cdots p_k^{a_k}.\]

Toutes les inégalités \(b_i \leq p_i^{a_i} - 1\) doivent donc être des égalités, ce qui implique que (1) est vraie. La preuve est complète. \(\blacksquare\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2011 N1 ★★☆☆☆ : Le plus petit entier à \(2^k\) diviseurs divise le plus petit entier à \(2^{k+1}\) diviseurs.
  • 2006 N3 ★★☆☆☆ : La moyenne \(\frac{1}{n}\sum \lfloor n/k \rfloor\) augmente une infinité de fois et diminue une infinité de fois.
  • 2020 N6 ★★★★☆ : Le rapport \(\varphi(d(n)) / d(\varphi(n))\), qui mêle indicatrice d'Euler et nombre de diviseurs, est-il borné ?
  • 2013 N7 ★★★★★ : Le nombre de couples excellents pour une équation avec parties entières de \(a\nu\) et \(b\nu\) est la somme des diviseurs de \(m\).