Shortlist 2020, N5¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : Croatia
Concepts : Principe extrémal · Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 79 (page 81 du PDF)
Énoncé¶
Determine all functions \(f\) defined on the set of all positive integers and taking non-negative integer values, satisfying the three conditions:
(i) \(f(n) \neq 0\) for at least one \(n\);
(ii) \(f(xy) = f(x) + f(y)\) for every positive integers \(x\) and \(y\);
(iii) there are infinitely many positive integers \(n\) such that \(f(k) = f(n - k)\) for all \(k < n\).
Indices : les idées clés
- Décomposition sur les premiers : par (ii), \(f\) est déterminée par ses valeurs sur les nombres premiers, \(f\left(\prod p_i^{\alpha_i}\right) = \sum \alpha_i f(p_i)\).
- Les diviseurs d'un « bon » nombre sont bons (solutions 1 et 2) : on étudie les \(n\) de la condition (iii) et leurs diviseurs.
- Principe extrémal : plus petit premier \(p\) avec \(f(p) \neq 0\) (solution 1), plus petit contre-exemple \(k\) (solution 2), premier maximisant \(f(p)/\ln p\) (solution 4).
- Congruences, Fermat (solution 1) : \(q \mid p^{q-1} - 1\) permet d'annuler \(f(q)\) pour tout premier \(q \neq p\).
- Valuations p-adiques : la réponse s'écrit avec \(\nu_p\), et \(\nu_p(p^m - k) = \nu_p(k)\) pour \(0 < k < p^m\) ; les solutions 2 et 4 raisonnent sur ces exposants.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (quatre solutions).
Réponse. Les fonctions cherchées sont les \(f(n) = c \cdot \nu_p(n)\), où \(p\) est un nombre premier, \(c\) un entier strictement positif, et \(\nu_p(n)\) l'exposant de \(p\) dans la décomposition de \(n\) en facteurs premiers.
Précision ajoutée : le livret écrit « \(c\) entier positif ou nul » ; la condition (i) impose \(c \neq 0\), ce que la vérification de la solution 1 utilise d'ailleurs.
Solution 1¶
Si \(n = p_1 p_2 \cdots p_k\) est un produit de nombres premiers, la condition (ii) donne
en particulier \(f(1) = 0\) (car \(f(1) = f(1) + f(1)\)). Il est clair aussi que \(f(n) = 0\) entraîne \(f(p) = 0\) pour tout premier \(p\) divisant \(n\) (les valeurs sont positives ou nulles).
Appelons bon un entier \(n\) tel que \(f(k) = f(n - k)\) pour \(0 < k < n\). Si \(n\) est bon, chacun de ses diviseurs \(d\) l'est aussi : si \(n = dm\), alors pour \(0 < k < d\),
Ainsi les bons nombres sont des produits de bons nombres premiers.
Le premier \(p\). D'après (i), il existe un premier \(p\) avec \(f(p) \neq 0\) ; par le principe extrémal, prenons \(p\) le plus petit possible. Alors \(f(r) = 0\) pour tout \(r < p\) (tous les diviseurs premiers de \(r\) sont inférieurs à \(p\)).
Tout bon nombre \(n > p\) est divisible par \(p\). En effet, si \(n = pk + r\) est bon, avec \(k > 0\) et \(0 < r < p\), alors
contradiction. Comme tout diviseur d'un bon nombre est bon, un diviseur \(r\) d'un bon nombre non divisible par \(p\) est donc inférieur à \(p\). Ainsi tous les bons nombres sont de la forme \(r \cdot p^k\) avec \(r < p\). La condition (iii) montre que \(k\) peut être arbitrairement grand ; par conséquent toutes les puissances de \(p\) sont bonnes.
Les autres premiers. Si \(q \neq p\) est premier, \(p^{q-1} - 1\) est divisible par \(q\) (petit théorème de Fermat) et \(p^{q-1}\) est bon. Donc
c'est-à-dire \(f(q) = 0\).
Conclusion. On obtient \(f(n) = c \cdot \nu_p(n)\) avec \(c = f(p) \neq 0\). Réciproquement, les conditions (i) et (ii) sont évidentes pour ces fonctions avec \(c \neq 0\) ; la condition (iii) est vérifiée par tous les \(n = p^m\), car \(\nu_p(p^m - k) = \nu_p(k)\) pour \(0 < k < p^m\) (valuations p-adiques). \(\blacksquare\)
Solution 2¶
On reprend la notion de bon nombre de la solution 1, et la notation \(\nu_p(n)\).
Disons qu'un entier \(k\) est gros si \(f(k) > 0\). Soit \(\mathcal{B}\) l'ensemble des premiers gros, et notons \(p_1 < p_2 < \cdots\) ses éléments (cet ensemble peut être fini ou infini). D'après les conditions de l'énoncé,
ainsi les gros nombres sont ceux qui sont divisibles par au moins un premier gros.
Pour un entier \(k \geq 1\), on définit son essence \(e(k)\) comme le plus grand produit \(e\) de premiers gros (non nécessairement distincts) tel que \(e \mid k\) ; autrement dit,
Alors \(k / e(k)\) n'est pas gros, donc \(f(k) = f(e(k)) + f(k / e(k)) = f(e(k))\).
Lemme. Si \(n\) est bon, alors \(e(k) = e(n - k)\) pour tout \(k < n\).
Preuve. Raisonnons par l'absurde et choisissons (principe extrémal) le plus petit \(k\) pour lequel l'affirmation est fausse. Ce \(k\) est gros : sinon \(f(k) = f(n - k) = 0\), d'où \(e(k) = e(n - k) = 1\).
Il y a \(t = k / e(k)\) multiples de \(e(k)\) dans chacun des segments \([1, k]\) et \([n - k, n - 1]\) (deux segments de \(k\) entiers consécutifs). D'autre part, il y en a \(t - 1\) dans \([1, k - 1]\), et donc aussi, par minimalité de \(k\), dans \([n - k + 1, n - 1]\) (car \(e(j) = e(n - j)\) pour \(j < k\), et \(e(k) \mid j\) équivaut à \(e(k) \mid e(j)\)). Cela entraîne que \(n - k\) est un multiple de \(e(k)\). Par conséquent
donc le dernier terme est nul : \(\frac{n - k}{e(k)}\) n'a aucun diviseur premier gros, c'est-à-dire \(e(n - k) = e(k)\). Cela contredit le choix de \(k\). \(\square\)
Retour au problème. Supposons \(|\mathcal{B}| \geq 2\). Prenons un bon nombre \(n > p_1 p_2\) (il en existe par (iii)), et soit \(p_1^\alpha\) la plus grande puissance de \(p_1\) strictement inférieure à \(n\), de sorte que \(n \leq p_1^{\alpha+1} < p_1^\alpha p_2\). D'après le lemme,
donc \(p_1^\alpha \mid n - p_1^\alpha\), puis \(p_1^\alpha \mid n\). De même \(p_2 \mid n\), de sorte que \(n \geq p_1^\alpha p_2\) : contradiction. Donc \(|\mathcal{B}| \leq 1\), et (1) montre que \(f\) est l'une des fonctions de la réponse (avec \(|\mathcal{B}| = 1\) par (i)). \(\blacksquare\)
Solution 3¶
On a \(f\left(\prod p_i^{\alpha_i}\right) = \sum \alpha_i f(p_i)\). Remarquons que
pour tout \(k = 1, 2, \ldots, n - 1\), car la différence (membre de gauche moins membre de droite) vaut exactement
Supposons \(f(p) > 0\). Si \(f(k) = f(n - k)\) pour tout \(k < n\), il y a égalité pour tout \(k\), donc \(f\left(\binom{n-1}{k}\right) = 0\), et \(\binom{n-1}{k}\) n'est pas divisible par \(p\) pour tout \(k = 1, 2, \ldots, n - 2\). Il est bien connu (par exemple par le théorème de Lucas) que cela entraîne \(n = a \cdot p^s\) avec \(a < p\).
S'il existait deux premiers \(p, q\) avec \(f(p) > 0\) et \(f(q) > 0\), il n'existerait qu'un nombre fini d'entiers \(n\) qui s'écrivent à la fois \(a \cdot p^s\) avec \(a < p\) et \(b \cdot q^t\) avec \(b < q\), ce qui contredirait (iii). Il existe donc au plus un tel \(p\) (et au moins un par (i)), et \(f(n) = C \cdot \nu_p(n)\) pour une constante \(C\). \(\blacksquare\)
Solution 4¶
On dit qu'une fonction \(f : \mathbb{N} \to \mathbb{N}_0\) vérifiant (ii) est additive. Une paire \((f, n)\), où \(f\) est additive et \(n \in \mathbb{N}\), est dite bonne si \(f(k) = f(n - k)\) pour tout \(k < n\). Pour \(f\) additive et \(p\) premier, on note
Soit \((f, n)\) une bonne paire telle que \(f(p) > 0\) pour au moins deux premiers \(p < n\). Par le principe extrémal, soit \(p_0\) le premier qui maximise \(g(f, p)\) parmi les premiers \(p < n\), et soit \(a_0\) l'exposant maximal tel que \(p_0^{a_0} < n\). Alors \(f(k) < f(p_0^{a_0})\) pour tout \(k < p_0^{a_0}\). En effet, si \(k = p_1^{a_1} \cdots p_m^{a_m} < p_0^{a_0}\), alors
Le livret écrit \(a_m \ln a_m\) dans le dernier terme de la première ligne ; il faut lire \(a_m \ln p_m\).
Écrivons \(n = b p_0^{a_0} + r\) avec \(0 \leq r < p_0^{a_0}\). Si \(r > 0\), alors \(f(r) = f(b p_0^{a_0}) \geq f(p_0^{a_0})\), ce qui contredit l'inégalité précédente. Donc \(p_0^{a_0} \mid n\), et \(n = p_0^{\nu_{p_0}(n)} n'\) avec \(n' \leq p_0\) (car \(n \leq p_0^{a_0 + 1}\)).
Les fonctions \(f_1(m) := f(p_0)\, \nu_{p_0}(m)\) et \(f_2 := f - f_1\) sont additives (et \(f_2\) est à valeurs positives : \(f(m) \geq f\big(p_0^{\nu_{p_0}(m)}\big) = f_1(m)\), puisque \(p_0^{\nu_{p_0}(m)}\) divise \(m\)). Pour \(k < n\), on a \(\nu_{p_0}(k) = \nu_{p_0}(n - k)\) (valuations p-adiques, grâce à la forme de \(n\)). Donc la paire \((f_2, n)\) est encore bonne. Remarquons que \(f_2(p_0) = 0\).
Choisissons parmi les premiers \(p < n\) le premier \(q_0\) qui maximise \(g(f_2, p)\) (on a \(f_2(q_0) > 0\), car \(f_2 = f\) sur les premiers autres que \(p_0\)). Comme ci-dessus, on montre que \(n = q_0^{\nu_{q_0}(n)} n''\) avec \(n'' < q_0\). Comme \(p_0 \neq q_0\), on obtient une contradiction.
Précision ajoutée : \(q_0\) divise \(n\), donc divise \(n'\), d'où \(q_0 \leq n' \leq p_0\) ; et \(p_0^{a_0}\) divise \(n''\), d'où \(p_0 \leq p_0^{a_0} \leq n'' < q_0\).
Ainsi, pour un bon \(n\) assez grand, il n'y a qu'un seul premier \(p\) avec \(f(p) > 0\), et \(f(n) = f(p) \cdot \nu_p(n)\). \(\blacksquare\)