Shortlist 2023, N5¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : Netherlands
Concepts : Suites et récurrences · Principe extrémal · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2023 (avec solutions), p. 88 (page 90 du PDF)
Énoncé¶
Soient \(a_1 < a_2 < a_3 < \cdots\) des entiers strictement positifs tels que \(a_{k+1}\) divise \(2(a_1 + a_2 + \cdots + a_k)\) pour tout \(k \geq 1\). On suppose que, pour une infinité de nombres premiers \(p\), il existe \(k\) tel que \(p\) divise \(a_k\). Montrer que, pour tout entier \(n\) strictement positif, il existe \(k\) tel que \(n\) divise \(a_k\).
Énoncé original (anglais)
Let \(a_1 < a_2 < a_3 < \cdots\) be positive integers such that \(a_{k+1}\) divides \(2(a_1 + a_2 + \cdots + a_k)\) for every \(k \geq 1\). Suppose that for infinitely many primes \(p\), there exists \(k\) such that \(p\) divides \(a_k\). Prove that for every positive integer \(n\), there exists \(k\) such that \(n\) divides \(a_k\).
Indices : les idées clés
- Introduire les quotients \(b_k = \frac{2(a_1 + \cdots + a_{k-1})}{a_k}\) : la condition devient une relation entre \(b_k\) et \(b_{k+1}\).
- Suites et récurrences : la relation \(b_{k+1} a_{k+1} = (b_k + 2) a_k\) montre que \((b_k)\) augmente d'au plus \(1\) à chaque pas et n'est pas bornée, donc prend toutes les grandes valeurs.
- Principe extrémal : on prend le plus petit \(k\) tel que \(b_{k+1} \geq n\), ce qui force \(b_k = n - 1\) et \(b_{k+1} = n\).
- Divisibilité, PGCD : \(n\) et \(n+1\) sont premiers entre eux.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2023 (une solution et une remarque).
Solution¶
Pour \(k \geq 2\), posons
qui est un entier strictement positif d'après l'hypothèse.
Affirmation 1. \(b_{k+1} \leq b_k + 1\) pour tout \(k \geq 2\).
Preuve. En soustrayant \(b_k a_k = 2(a_1 + \cdots + a_{k-1})\) de \(b_{k+1} a_{k+1} = 2(a_1 + \cdots + a_k)\), on trouve
Comme \(a_k < a_{k+1}\), il vient \(b_k + 2 > b_{k+1}\), soit \(b_{k+1} \leq b_k + 1\). \(\square\)
Affirmation 2. La suite \((b_k)\) n'est pas bornée.
Preuve. La relation précédente s'écrit
Si la suite \((b_k)\) était bornée par un entier \(B\), alors, de proche en proche, les facteurs premiers des \(a_k\) seraient soit des premiers \(\leq B + 2\), soit des premiers divisant \(a_1\) ou \(a_2\) : il n'y en aurait qu'un nombre fini, ce qui contredit l'hypothèse de l'énoncé. \(\square\)
Conclusion. Soit \(n\) un entier strictement positif. On peut supposer \(n > b_2\) (sinon on remplace \(n\) par un multiple de \(n\) plus grand que \(b_2\)). D'après l'affirmation 2, il existe \(k\) tel que \(b_{k+1} \geq n\) ; prenons le plus petit tel \(k\). Comme \(b_2 < n\), on a \(k \geq 2\), et par minimalité \(b_k \leq n - 1\). L'affirmation 1 donne alors \(n \leq b_{k+1} \leq b_k + 1 \leq n\), donc \(b_k = n - 1\) et \(b_{k+1} = n\). Ainsi
Comme \(n\) et \(n + 1\) sont premiers entre eux, \(n\) divise \(a_k\). \(\blacksquare\)
Remarques¶
Remarque. Pour tout entier \(c \geq 1\), la suite \(a_k = ck\) vérifie les hypothèses. Un autre exemple : \(a_1 = 1\), \(a_2 = 2\) et \(a_k = 3(k-1)\) pour \(k \geq 3\).
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2017 A4 ★★☆☆☆ : Une suite définie par \(a_n = -\max_{i+j=n}(a_i + a_j)\) au-delà d'un certain rang est bornée.
- 2009 A6 ★★★☆☆ · OIM P3 : Si deux sous-suites extraites d'une suite croissante sont arithmétiques, la suite elle-même l'est.
- 2006 A3 ★★★☆☆ : Les couples \((\sum c_j, \sum c_{j-1})\) formés avec une suite de type Fibonacci sont exactement les points entiers d'une bande.
- 2021 N7 ★★★★☆ : Si \(a_{n+2m}\) divise \(a_n + a_{n+m}\), la suite finit par être périodique.