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é

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

\[b_k = \frac{2(a_1 + \cdots + a_{k-1})}{a_k},\]

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

\[b_{k+1} a_{k+1} = b_k a_k + 2a_k = (b_k + 2) a_k.\]

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

\[a_{k+1} = a_k \cdot \frac{b_k + 2}{b_{k+1}}, \quad \text{donc} \quad a_{k+1} \mid a_k (b_k + 2).\]

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

\[a_{k+1} = a_k \cdot \frac{b_k + 2}{b_{k+1}} = a_k \cdot \frac{n+1}{n}.\]

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