Aller au contenu

Shortlist 2018, N7

Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : Thailand

Concepts : Valuations p-adiques et lemme LTE · Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 68 (page 70 du PDF)

Énoncé

Soit \(n \geq 2018\) un entier, et soient \(a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\) des entiers strictement positifs deux à deux distincts, inférieurs ou égaux à \(5n\). On suppose que la suite

\[\frac{a_1}{b_1},\ \frac{a_2}{b_2},\ \ldots,\ \frac{a_n}{b_n}\]

est une progression arithmétique. Montrer que les termes de la suite sont égaux.

Énoncé original (anglais)

Let \(n \geq 2018\) be an integer, and let \(a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\) be pairwise distinct positive integers not exceeding \(5n\). Suppose that the sequence

\[\frac{a_1}{b_1},\ \frac{a_2}{b_2},\ \ldots,\ \frac{a_n}{b_n}\]

forms an arithmetic progression. Prove that the terms of the sequence are equal.

Indices : les idées clés
  • Écrire la raison sous forme irréductible \(\Delta = \frac{c}{d}\) et montrer que beaucoup trop de dénominateurs \(b_i\) devraient être divisibles par \(d\).
  • Valuations \(p\)-adiques : un indice \(i\) est « \(p\)-mauvais » si \(v_p(b_i) < v_p(d)\) ; les indices \(p\)-mauvais sont tous congrus modulo \(p\).
  • Fractions irréductibles et divisibilité : la différence de deux termes, \(\frac{(i-j)c}{d}\), a un dénominateur divisible par \(p^{\alpha}\) dès que \(p \nmid i - j\).
  • Comptage par blocs de 30 : \(d\) n'a que \(2, 3, 5\) comme facteurs premiers, donc dans tout bloc de \(30\) indices consécutifs, au moins \((2-1)(3-1)(5-1) = 8\) dénominateurs sont multiples de \(d\).
  • Majorer la raison : la plupart des termes sont dans \((0, 10]\), donc \(|\Delta|\) est petit et \(d\) est grand ; d'où des dénominateurs trop grands.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2018 (une solution et deux remarques).

Solution

Supposons que (1), la suite \(\frac{a_1}{b_1}, \ldots, \frac{a_n}{b_n}\), soit une progression arithmétique de raison non nulle. Écrivons la raison \(\Delta = \frac{c}{d}\), avec \(d > 0\) et \(c, d\) premiers entre eux.

On va montrer que trop de dénominateurs \(b_i\) devraient être divisibles par \(d\). Pour cela, pour tout \(1 \leq i \leq n\) et tout diviseur premier \(p\) de \(d\), on dit que l'indice \(i\) est \(p\)-mauvais si \(v_p(b_i) < v_p(d)\), où \(v_p(x)\) est l'exposant de \(p\) dans la décomposition de \(x\) (valuation \(p\)-adique).

Affirmation 1. Pour tout premier \(p\), les indices \(p\)-mauvais sont tous congrus entre eux modulo \(p\). Autrement dit, ils sont contenus dans une progression arithmétique de raison \(p\).

Preuve. Soit \(\alpha = v_p(d)\). Par l'absurde, supposons que \(i\) et \(j\) soient \(p\)-mauvais (aucun des deux \(b_i\), \(b_j\) n'est divisible par \(p^{\alpha}\)) avec \(i \not\equiv j \pmod p\). Alors le plus petit dénominateur commun de \(\frac{a_i}{b_i}\) et \(\frac{a_j}{b_j}\) n'est pas divisible par \(p^{\alpha}\). C'est impossible, car dans leur différence \((i - j)\Delta = \frac{(i - j)c}{d}\), le numérateur est premier avec \(p\) alors que \(p^{\alpha}\) divise le dénominateur \(d\). \(\square\)

Affirmation 2. \(d\) n'a aucun diviseur premier supérieur à \(5\).

Preuve. Supposons que \(p \geq 7\) soit un diviseur premier de \(d\). Parmi les indices \(1, 2, \ldots, n\), au plus \(\left\lceil \frac{n}{p} \right\rceil < \frac{n}{p} + 1\) sont \(p\)-mauvais, donc \(p\) divise au moins \(\frac{p-1}{p}n - 1\) des nombres \(b_1, \ldots, b_n\). Comme ces dénominateurs sont distincts,

\[5n \geq \max\{b_i : p \mid b_i\} \geq \left(\frac{p-1}{p}n - 1\right)p = (p - 1)(n - 1) - 1 \geq 6(n - 1) - 1 > 5n,\]

contradiction. \(\square\)

Affirmation 3. Pour tout \(0 \leq k \leq n - 30\), parmi les dénominateurs \(b_{k+1}, b_{k+2}, \ldots, b_{k+30}\), au moins \(\varphi(30) = 8\) sont divisibles par \(d\).

Preuve. D'après l'affirmation 1, les indices \(2\)-mauvais, \(3\)-mauvais et \(5\)-mauvais sont couverts par trois progressions arithmétiques de raisons \(2\), \(3\) et \(5\). Par un simple argument d'inclusion-exclusion, \((2 - 1)(3 - 1)(5 - 1) = 8\) indices du bloc ne sont pas couverts ; d'après l'affirmation 2, \(d \mid b_i\) pour chaque indice \(i\) non couvert. \(\square\)

Affirmation 4. \(|\Delta| < \frac{20}{n-2}\) et \(d > \frac{n-2}{20}\).

Preuve. Retirons de la suite (1) toutes les fractions avec \(b_i < \frac{n}{2}\). Il en reste au moins \(\frac{n}{2}\) (les \(b_i\) sont distincts), et elles ne dépassent pas \(\frac{5n}{n/2} = 10\). On a donc au moins \(\frac{n}{2}\) termes de la progression arithmétique (1) dans l'intervalle \((0, 10]\), d'où \(|\Delta| < \frac{10}{n/2 - 1} = \frac{20}{n - 2}\). La seconde inégalité découle de \(\frac{1}{d} \leq \frac{|c|}{d} = |\Delta|\). \(\square\)

Conclusion. D'après l'affirmation 3 (appliquée à \(\left\lfloor \frac{n}{30} \right\rfloor\) blocs disjoints), \(d \mid b_i\) pour au moins \(8\left\lfloor \frac{n}{30} \right\rfloor\) indices \(i\). D'après l'affirmation 4, \(d > \frac{n-2}{20}\). Comme ces \(b_i\) sont des multiples distincts de \(d\),

\[5n \geq \max\{b_i : d \mid b_i\} \geq \left(\left\lfloor \frac{n}{30} \right\rfloor \cdot 8\right) \cdot d > \left(\frac{n}{30} - 1\right) \cdot 8 \cdot \frac{n - 2}{20} > 5n,\]

la dernière inégalité étant vraie pour \(n \geq 2018\). C'est une contradiction : la raison est nulle et tous les termes sont égaux. \(\blacksquare\)

Remarques

Remarque 1. Il est possible que tous les termes de (1) soient égaux : par exemple, avec \(a_i = 2i - 1\) et \(b_i = 4i - 2\), on a \(\frac{a_i}{b_i} = \frac{1}{2}\).

Remarque 2. La borne \(5n\) de l'énoncé est loin d'être optimale : la solution ci-dessus peut être adaptée pour \(9n\), et pour \(n\) grand, la borne \(5n\) peut être remplacée par \(n^{3/2 - \varepsilon}\).

Problèmes voisins

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

  • 2015 N3 ★★☆☆☆ : Si tous les \((m + k)/(n + k)\) sont entiers, leur produit moins \(1\) a un facteur premier impair.
  • 2009 N3 ★★★☆☆ : Une fonction non constante telle que \(a - b\) divise \(f(a) - f(b)\) a une infinité de diviseurs premiers parmi ses valeurs.
  • 2024 N7 ★★★★★ : Une équation fonctionnelle vraie exactement pour les couples premiers entre eux : quelles valeurs peut prendre \(f(n)\) ?
  • 2014 N8 ★★★★★ : Pour tous \(a\), \(b\), une puissance \(p^k\) d'un premier impair rend égale à \(1\) une somme de distances aux entiers.