Aller au contenu

Shortlist 2008, N3

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2008 (avec solutions), p. 46 (page 47 du PDF)

Énoncé

Soit \(a_0, a_1, a_2, \ldots\) une suite d'entiers strictement positifs telle que le plus grand diviseur commun de deux termes consécutifs quelconques soit strictement supérieur au terme qui les précède ; autrement dit, \(\gcd(a_i, a_{i+1}) > a_{i-1}\). Montrer que \(a_n \geq 2^n\) pour tout \(n \geq 0\).

Énoncé original (anglais)

Let \(a_0, a_1, a_2, \ldots\) be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, \(\gcd(a_i, a_{i+1}) > a_{i-1}\). Prove that \(a_n \geq 2^n\) for all \(n \geq 0\).

Indices : les idées clés
  • Croissance : \(a_{i+1} - a_i \geq \gcd(a_i, a_{i+1}) > a_{i-1}\) ; les cas de base \(n \leq 3\) se vérifient à la main (\(a_3 = 7\) est impossible).
  • Récurrence : avec \(d = \gcd(a_n, a_{n+1}) > a_{n-1}\), le seul cas difficile est \(a_n = 2d\), \(a_{n+1} = 3d\).
  • Descente sur les pgcd : on écrit \(a_n = md'\) avec \(d' = \gcd(a_{n-1}, a_n)\) ; seul \(m = 5\) résiste, et le même raisonnement un cran plus bas clôt tous les cas.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution).

Solution

Comme \(a_i \geq \gcd(a_i, a_{i+1}) > a_{i-1}\), la suite est strictement croissante. En particulier, \(a_0 \geq 1\), \(a_1 \geq 2\). Pour tout \(i \geq 1\), on a aussi \(a_{i+1} - a_i \geq \gcd(a_i, a_{i+1}) > a_{i-1}\), et par conséquent \(a_{i+1} \geq a_i + a_{i-1} + 1\). Donc \(a_2 \geq 4\) et \(a_3 \geq 7\). L'égalité \(a_3 = 7\) forcerait l'égalité dans les estimations précédentes, ce qui mènerait à \(\gcd(a_2, a_3) = \gcd(4, 7) > a_1 = 2\), ce qui est faux. Donc \(a_3 \geq 8\) ; le résultat est vrai pour \(n = 0, 1, 2, 3\). Ce sont les cas de base d'une preuve par récurrence.

Prenons \(n \geq 3\) et supposons \(a_i \geq 2^i\) pour \(i = 0, 1, \ldots, n\). Il faut montrer que \(a_{n+1} \geq 2^{n+1}\). Posons \(\gcd(a_n, a_{n+1}) = d\). On sait que \(d > a_{n-1}\). L'hérédité est immédiate dans les cas suivants :

\[\begin{aligned} &\text{si } a_{n+1} \geq 4d, & &\text{alors } a_{n+1} > 4a_{n-1} \geq 4 \cdot 2^{n-1} = 2^{n+1} ; \\ &\text{si } a_n \geq 3d, & &\text{alors } a_{n+1} \geq a_n + d \geq 4d > 4a_{n-1} \geq 4 \cdot 2^{n-1} = 2^{n+1} ; \\ &\text{si } a_n = d, & &\text{alors } a_{n+1} \geq a_n + d = 2a_n \geq 2 \cdot 2^n = 2^{n+1}. \end{aligned}\]

La seule possibilité restante est \(a_n = 2d\) et \(a_{n+1} = 3d\), ce qu'on suppose dans la suite. Donc \(a_{n+1} = \frac{3}{2}a_n\).

Posons maintenant \(\gcd(a_{n-1}, a_n) = d'\) ; alors \(d' > a_{n-2}\). Écrivons \(a_n = md'\) (\(m\) entier). En se rappelant que \(d' \leq a_{n-1} < d\) et \(a_n = 2d\), on obtient \(m \geq 3\). De plus, \(a_{n-1} < d = \frac{1}{2}md'\), \(a_{n+1} = \frac{3}{2}md'\). On isole de nouveau les cas qui donnent immédiatement l'hérédité :

\[\begin{aligned} &\text{si } m \geq 6, & &\text{alors } a_{n+1} = \tfrac{3}{2}md' \geq 9d' > 9a_{n-2} \geq 9 \cdot 2^{n-2} > 2^{n+1} ; \\ &\text{si } 3 \leq m \leq 4, & &\text{alors } a_{n-1} < \tfrac{1}{2} \cdot 4d', \text{ donc } a_{n-1} = d', \text{ et } a_{n+1} = \tfrac{3}{2}ma_{n-1} \geq \tfrac{3}{2} \cdot 3a_{n-1} \geq \tfrac{9}{2} \cdot 2^{n-1} > 2^{n+1}. \end{aligned}\]

Il reste le cas \(m = 5\), ce qui signifie que \(a_n = 5d'\), \(a_{n+1} = \frac{15}{2}d'\), \(a_{n-1} < d = \frac{5}{2}d'\). La dernière relation implique que \(a_{n-1}\) vaut \(d'\) ou \(2d'\). Dans les deux cas, \(a_{n-1} \mid 2d'\).

Le même schéma se répète encore une fois. Notons \(\gcd(a_{n-2}, a_{n-1}) = d''\) ; alors \(d'' > a_{n-3}\). Comme \(d''\) est un diviseur de \(a_{n-1}\), donc aussi de \(2d'\), on peut écrire \(2d' = m'd''\) (\(m'\) entier). Comme \(d'' \leq a_{n-2} < d'\), on obtient \(m' \geq 3\). De plus, \(a_{n-2} < d' = \frac{1}{2}m'd''\), \(a_{n+1} = \frac{15}{2}d' = \frac{15}{4}m'd''\). Comme précédemment, on considère les cas :

\[\begin{aligned} &\text{si } m' \geq 5, & &\text{alors } a_{n+1} = \tfrac{15}{4}m'd'' \geq \tfrac{75}{4}d'' > \tfrac{75}{4}a_{n-3} \geq \tfrac{75}{4} \cdot 2^{n-3} > 2^{n+1} ; \\ &\text{si } 3 \leq m' \leq 4, & &\text{alors } a_{n-2} < \tfrac{1}{2} \cdot 4d'', \text{ donc } a_{n-2} = d'', \text{ et } a_{n+1} = \tfrac{15}{4}m'a_{n-2} \geq \tfrac{15}{4} \cdot 3a_{n-2} \geq \tfrac{45}{4} \cdot 2^{n-2} > 2^{n+1}. \end{aligned}\]

Les deux cas donnent l'hérédité. Mais il ne reste maintenant aucun cas. La récurrence est complète ; l'inégalité \(a_n \geq 2^n\) est vraie pour tout \(n\). \(\blacksquare\)

Problèmes voisins

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

  • 2023 N1 ★☆☆☆☆ · OIM P1 : Quels entiers composés ont chaque diviseur qui divise la somme des deux diviseurs suivants ?
  • 2024 N4 ★★★☆☆ · OIM P2 : Pour quels \(a, b\) le PGCD de \(a^n + b\) et \(b^n + a\) finit-il par être constant ?
  • 2022 C6 ★★★☆☆ : On fusionne des cailloux pris en quantités égales dans deux tas : combien de tas au minimum ?
  • 2021 N6 ★★★★☆ : Pour quels \(n\) peut-on toujours ordonner \(n\) entiers distincts pour que \(\sum k a_k\) soit divisible par \(n\) ?