Shortlist 2015, N8¶
Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : Brazil
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler · Principe des tiroirs
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 79 (page 80 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
For every positive integer \(n\) with prime factorization \(n = \prod_{i=1}^{k} p_i^{\alpha_i}\), define
That is, \(\mho(n)\) is the number of prime factors of \(n\) greater than \(10^{100}\), counted with multiplicity.
Find all strictly increasing functions \(f : \mathbb{Z} \to \mathbb{Z}\) such that
for all integers \(a\) and \(b\) with \(a > b\).
Indices : les idées clés
- Partie « grande » et partie « petite » : on écrit \(k = L(k)\,S(k)\), où \(L(k)\) regroupe les facteurs premiers \(> 10^{100}\) et \(S(k)\) les autres ; la condition force \(L\big(f(a) - f(b)\big) = L(a - b)\).
- Divisibilité et PPCM (étape 1) : par récurrence forte sur le grand nombre \(k_0\), si \(k_0 \mid f(x) - f(y)\) avec \(0 < x - y < k_0\), alors \(\operatorname{lcm}(k_0, L(x-y))\) divise \(f(x) - f(y)\), ce qui contredit l'hypothèse.
- Congruences : systèmes complets de résidus modulo \(k_0\) ; à la fin, un entier divisible par un grand nombre \(|n - x|\) plus grand que lui est nul.
- Principe des tiroirs (étape 2) : la majoration \(f(t) < ct\) ne laisse qu'un nombre fini de valeurs pour \(f(t)/t\) sur les grands premiers \(t\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2015 (une solution et trois remarques).
Réponse. \(f(x) = ax + b\), où \(b\) est un entier quelconque et \(a\) un entier positif tel que \(\mho(a) = 0\).
Solution¶
Une vérification directe montre que ces fonctions conviennent. Montrons la réciproque.
Soit \(f\) une fonction vérifiant la condition. La fonction \(g(x) = f(x) - f(0)\) la vérifie aussi ; on suppose donc désormais \(f(0) = 0\), et alors \(f(n) > 0\) pour tout \(n > 0\). Il s'agit de montrer qu'il existe un entier positif \(a\) avec \(\mho(a) = 0\) tel que \(f(n) = an\) pour tout \(n \in \mathbb{Z}\).
Notations. Soit \(N = 10^{100}\). Un premier \(p\) est grand si \(p > N\), petit sinon ; soit \(\mathcal{S}\) l'ensemble des petits premiers. Un entier positif est grand (resp. petit) si tous ses facteurs premiers le sont (ainsi \(1\) est le seul nombre à la fois grand et petit). Pour un entier positif \(k\), on note \(L(k)\) son plus grand diviseur grand et \(S(k)\) son plus grand diviseur petit ; ainsi \(k = L(k)\,S(k)\).
Étape 1. Pour tout grand \(k\) : \(k \mid f(a) - f(b) \iff k \mid a - b\). Autrement dit, \(L\big(f(a) - f(b)\big) = L(a - b)\) pour tous \(a > b\).
On raisonne par récurrence sur \(k\). Le cas \(k = 1\) est trivial. Soit \(k_0\) un grand nombre, et supposons l'énoncé vrai pour tous les grands \(k < k_0\).
Affirmation 1. Si \(0 < x - y < k_0\), alors \(k_0\) ne divise pas \(f(x) - f(y)\).
Preuve. Supposons au contraire \(k_0 \mid f(x) - f(y)\). Soit \(\ell = L(x - y)\) ; alors \(\ell \leq x - y < k_0\). Par hypothèse de récurrence, \(\ell \mid f(x) - f(y)\), donc \(\operatorname{lcm}(k_0, \ell) \mid f(x) - f(y)\). Or \(\operatorname{lcm}(k_0, \ell)\) est grand et \(\operatorname{lcm}(k_0, \ell) \geq k_0 > \ell\). Donc
ce qui est impossible. \(\square\)
Terminons l'hérédité. D'après l'affirmation 1, pour tout entier \(a\), chacune des suites
forme un système complet de résidus modulo \(k_0\). Donc \(f(a) \equiv f(a + k_0) \pmod{k_0}\), et \(f(a) \equiv f(b) \pmod{k_0}\) dès que \(a \equiv b \pmod{k_0}\). Enfin, si \(a \not\equiv b \pmod{k_0}\), il existe \(b'\) avec \(b' \equiv b \pmod{k_0}\) et \(|a - b'| < k_0\) ; alors \(f(b) \equiv f(b') \not\equiv f(a) \pmod{k_0}\). L'hérédité est prouvée.
Étape 2. Il existe un petit entier \(a\) tel que \(f(n) = an\) pour une infinité d'entiers \(n\).
Affirmation 2. Il existe une constante \(c\) telle que \(f(t) < ct\) pour tout entier \(t > N\).
Preuve. Soit \(d\) le produit de tous les petits premiers, et \(\alpha\) un entier positif tel que \(2^\alpha > f(N)\). Alors, pour tout \(p \in \mathcal{S}\), les nombres \(f(0), f(1), \ldots, f(N)\) sont distincts modulo \(p^\alpha\). Posons \(P = d^\alpha\) et \(c = P + f(N)\).
Soit \(t > N\). Par le choix de \(\alpha\), pour tout \(p \in \mathcal{S}\), il existe au plus un entier \(0 \leq i \leq N\) avec \(p^\alpha \mid f(t) - f(i)\). Comme \(|\mathcal{S}| < N\), on peut choisir \(0 \leq j \leq N\) tel que \(p^\alpha \nmid f(t) - f(j)\) pour tout \(p \in \mathcal{S}\). Donc \(S\big(f(t) - f(j)\big) < P\). D'autre part, l'étape 1 donne \(L\big(f(t) - f(j)\big) = L(t - j) \leq t - j\). Comme \(0 \leq j \leq N\),
Soit \(\mathcal{T}\) l'ensemble des grands premiers. Pour \(t \in \mathcal{T}\), l'étape 1 donne \(L\big(f(t)\big) = t\), donc \(f(t)/t\) est un entier. L'affirmation 2 ne laisse qu'un nombre fini de valeurs possibles pour ce quotient ; par le principe des tiroirs, il existe un sous-ensemble infini \(\mathcal{T}' \subseteq \mathcal{T}\) et un entier positif \(a\) tels que \(f(t) = at\) pour tout \(t \in \mathcal{T}'\). Comme \(L(t) = L\big(f(t)\big) = L(a)L(t)\) pour \(t \in \mathcal{T}'\), on a \(L(a) = 1\) : \(a\) est petit.
Étape 3. \(f(x) = ax\) pour tout \(x \in \mathbb{Z}\). Soit \(R_i = \{ x \in \mathbb{Z} : x \equiv i \pmod{N!} \}\).
Affirmation 3. S'il existe une infinité de \(n \in R_r\) tels que \(f(n) = an\), alors \(f(x) = ax\) pour tout \(x \in R_{r+1}\).
Preuve. Soit \(x \in R_{r+1}\). On choisit \(n \in R_r\) avec \(f(n) = an\) et \(|n - x| > |f(x) - ax|\). Comme \(n - x \equiv r - (r+1) = -1 \pmod{N!}\), le nombre \(|n - x|\) n'a aucun petit facteur premier : il est grand. Par l'étape 1, \(f(x) \equiv f(n) = an \equiv ax \pmod{n - x}\), donc \(n - x \mid f(x) - ax\). Vu le choix de \(n\), cela donne \(f(x) = ax\). \(\square\)
Pour conclure, l'ensemble \(\mathcal{T}'\) de l'étape 2 contient une infinité d'éléments d'une même classe \(R_i\). En appliquant l'affirmation 3 de proche en proche, on obtient \(f(x) = ax\) pour tout \(x \in R_{i+1}, R_{i+2}, \ldots, R_{i+N!} = R_i\), c'est-à-dire pour tout \(x\). En revenant à \(f\) quelconque, \(f(x) = ax + f(0)\) avec \(a\) petit, c'est-à-dire \(\mho(a) = 0\). \(\blacksquare\)
Remarques¶
Remarque 1. Comme le signale le proposeur, on peut aussi considérer la variante où la condition est remplacée par \(L\big(f(a) - f(b)\big) = L(a - b)\) pour tous \(a > b\) ; l'étape 1 devient alors inutile.
Remarque 2 (variantes de l'étape 2). L'étape 2 est l'étape principale. Voici deux approches qui utilisent des énoncés plus faibles que l'affirmation 2.
Approche 1. Soit encore \(d\) le produit des petits premiers ; on étudie les valeurs \(f(d^i)\), \(i \geq 0\). Par l'étape 1, \(L\big(f(d^i) - f(d^k)\big) = L(d^i - d^k) = d^{i-k} - 1\) pour \(i > k \geq 0\). Comme au début de la preuve de l'affirmation 2, on choisit \(\alpha \geq 0\) tel que les nombres \(f(d^i)\), \(i = 0, 1, \ldots, N\), soient distincts modulo \(p^\alpha\) pour tout \(p \in \mathcal{S}\). Alors, pour tout \(i > N\), il existe \(k = k(i) \leq N\) tel que \(S\big(f(d^i) - f(d^k)\big) < P = d^\alpha\). Il n'y a qu'un nombre fini de possibilités pour \(k(i)\) et pour \(S\big(f(d^i) - f(d^k)\big)\) ; il existe donc un ensemble infini \(I\) d'exposants \(i > N\) pour lesquels \(k(i) = k_0\) et \(S\big(f(d^i) - f(d^{k_0})\big) = s_0\) sont fixes. Pour ces \(i\),
donc \(f\) est affine sur l'ensemble infini \(\{d^i : i \in I\}\) (avec des coefficients rationnels). On utilise enfin \(f(d^i) \equiv f(1) \pmod{d^i - 1}\) pour montrer que \(f(d^i)/d^i\) est un entier petit et fixe pour \(i \in I\).
Approche 2. On part du lemme suivant : il existe une constante \(c > 0\) telle que, pour tout \(k > 3N\),
Preuve. Soit \(\Pi = \prod_{i=1}^{3N} \big(f(k) - f(i)\big)\). Pour chaque \(p \in \mathcal{S}\), au plus un élément de \(\mathcal{H} = \{ f(k) - f(i) : 1 \leq i \leq 3N \}\) est divisible par une puissance de \(p\) supérieure à \(f(3N)\) ; on dit que ces éléments sont mauvais. Pour \(h \in \mathcal{H}\) non mauvais, \(S(h) \leq f(3N)^N\), et les mauvais éléments ne dépassent pas \(f(k)\) ; il y a moins de \(N\) éléments mauvais. Donc
Le lemme en découle, puisque \(L(\Pi)S(\Pi) = \Pi \geq \mu \big(f(k)\big)^{3N}\) pour une constante absolue \(\mu\). \(\square\)
On en déduit une version faible de l'affirmation 2 : il existe \(C > 0\) tel que \(f(k) \leq Ck^{3/2}\) pour \(k > 3N\). En effet, par l'étape 1,
donc \(f(k) \leq c^{-1/(2N)} k^{3/2}\). Pour finir l'étape 2, on pose \(a = f(1)\) et on choisit \(n_0\) tel que \(|f(n) - an| < \frac{n(n-1)}{2}\) pour tout \(n \geq n_0\). Soit \(n \geq n_0\) avec \(n \equiv 2 \pmod{N!}\). Alors \(L\big(f(n) - f(0)\big) = L(n) = n/2\) et \(L\big(f(n) - f(1)\big) = L(n - 1) = n - 1\), d'où \(f(n) \equiv f(0) = 0 \equiv an \pmod{n/2}\) et \(f(n) \equiv f(1) = a \equiv an \pmod{n - 1}\). Ainsi \(\frac{n(n-1)}{2} \mid f(n) - an\), et l'estimation donne \(f(n) = an\).
Remarque 3 (variante de l'étape 3). Pour l'étape 3, il suffit d'avoir \(f(n) = an\) sur un ensemble infini ; si cet ensemble est bien structuré, on peut conclure plus simplement. Par exemple, sachant (approche 2) que \(f(n) = an\) pour tout \(n \geq n_0\) avec \(n \equiv 2 \pmod{N!}\) : soit \(x\) un entier et \(p\) un grand premier supérieur à \(|f(x) - ax|\). Par le théorème des restes chinois, il existe \(n > \max(x, n_0)\) avec \(n \equiv 2 \pmod{N!}\) et \(n \equiv x \pmod p\). Par l'étape 1, \(f(x) \equiv f(n) = an \equiv ax \pmod p\), ce qui impose \(f(x) = ax\).