Aller au contenu

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)

Énoncé

Pour tout entier \(n\) strictement positif de décomposition en facteurs premiers \(n = \prod_{i=1}^{k} p_i^{\alpha_i}\), on pose

\[\mho(n) = \sum_{i \,:\, p_i > 10^{100}} \alpha_i.\]

Autrement dit, \(\mho(n)\) est le nombre de facteurs premiers de \(n\) strictement supérieurs à \(10^{100}\), comptés avec multiplicité.

Trouver toutes les fonctions strictement croissantes \(f : \mathbb{Z} \to \mathbb{Z}\) telles que

\[\mho\big(f(a) - f(b)\big) \leq \mho(a - b)\]

pour tous entiers \(a\) et \(b\) avec \(a > b\).

Énoncé original (anglais)

For every positive integer \(n\) with prime factorization \(n = \prod_{i=1}^{k} p_i^{\alpha_i}\), define

\[\mho(n) = \sum_{i \,:\, p_i > 10^{100}} \alpha_i.\]

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

\[\mho\big(f(a) - f(b)\big) \leq \mho(a - b)\]

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

\[\mho\big(f(x) - f(y)\big) \geq \mho\big(\operatorname{lcm}(k_0, \ell)\big) > \mho(\ell) = \mho(x - y),\]

ce qui est impossible. \(\square\)

Terminons l'hérédité. D'après l'affirmation 1, pour tout entier \(a\), chacune des suites

\[f(a), f(a+1), \ldots, f(a + k_0 - 1) \qquad \text{et} \qquad f(a+1), f(a+2), \ldots, f(a + k_0)\]

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\),

\[f(t) = f(j) + L\big(f(t) - f(j)\big) \cdot S\big(f(t) - f(j)\big) < f(N) + (t - j)P \leq \big(P + f(N)\big)t = ct. \qquad \square\]

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\),

\[f(d^i) = f(d^{k_0}) + L\big(f(d^i) - f(d^{k_0})\big) \cdot S\big(f(d^i) - f(d^{k_0})\big) = f(d^{k_0}) + \left(d^{i - k_0} - 1\right)s_0,\]

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\),

\[L\left(\prod_{i=1}^{3N} \big(f(k) - f(i)\big)\right) = \prod_{i=1}^{3N} L\big(f(k) - f(i)\big) \geq c\, \big(f(k)\big)^{2N}.\]

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

\[S(\Pi) = \prod_{h \in \mathcal{H}} S(h) \leq \big(f(3N)\big)^{3N^2} \cdot \big(f(k)\big)^N.\]

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,

\[k^{3N} \geq \prod_{i=1}^{3N} L(k - i) = \prod_{i=1}^{3N} L\big(f(k) - f(i)\big) \geq c\, \big(f(k)\big)^{2N},\]

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\).

Problèmes voisins

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

  • 2024 N4 ★★★☆☆ · OIM P2 : Pour quels \(a, b\) le PGCD de \(a^n + b\) et \(b^n + a\) finit-il par être constant ?
  • 2017 N5 ★★★☆☆ : Pour quels premiers \(p > q\) une fraction de puissances de \(p + q\) et \(p - q\) est-elle entière ?
  • 2011 N3 ★★★☆☆ : Pour \(n\) impair, trouver les fonctions de \(\mathbb{Z}\) telles que \(f(x) - f(y)\) divise toujours \(x^n - y^n\).
  • 2021 N6 ★★★★☆ : Pour quels \(n\) peut-on toujours ordonner \(n\) entiers distincts pour que \(\sum k a_k\) soit divisible par \(n\) ?