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