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 :
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é :
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 :
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\) ?