Shortlist 2021, N7¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal · Suites et récurrences
Solution officielle : Shortlist officielle 2021 (avec solutions), p. 78 (page 78 du PDF)
Énoncé¶
Let \(a_1, a_2, a_3, \ldots\) be an infinite sequence of positive integers such that \(a_{n+2m}\) divides \(a_n + a_{n+m}\) for all positive integers \(n\) and \(m\). Prove that this sequence is eventually periodic, i.e. there exist positive integers \(N\) and \(d\) such that \(a_n = a_{n+d}\) for all \(n > N\).
Indices : les idées clés
- Divisibilité : si \(d\) divise deux des trois termes \(a_n\), \(a_{n-m}\), \(a_{n-2m}\) (dont \(a_n\)), il divise le troisième (lemme 1).
- Principe extrémal : on considère un terme \(a_n\) plus grand que tous les précédents pour montrer que la suite est bornée, puis la valeur maximale \(k\).
- Suites : pour chaque diviseur \(d\), les indices \(i\) tels que \(d \mid a_i\) forment une progression arithmétique de raison impaire ; le produit des raisons est une période.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (une solution et une remarque).
Solution¶
Nous utiliserons plusieurs fois l'observation simple suivante.
Lemme 1. Si un entier \(d > 0\) divise \(a_n\) et \(a_{n-m}\) pour certains \(m\) et \(n > 2m\), il divise aussi \(a_{n-2m}\). Si \(d\) divise \(a_n\) et \(a_{n-2m}\), il divise aussi \(a_{n-m}\).
Preuve. Les deux parties sont évidentes puisque \(a_n\) divise \(a_{n-2m} + a_{n-m}\). \(\square\)
Affirmation. La suite \((a_n)\) est bornée.
Preuve. Supposons le contraire. Il existe alors une infinité d'indices \(n\) tels que \(a_n\) soit strictement plus grand que chacun des termes précédents \(a_1, a_2, \ldots, a_{n-1}\) (principe extrémal). Soit \(a_n = k\) un tel terme, avec \(n > 10\). Pour tout \(s < \frac{n}{2}\), le nombre \(a_n = k\) divise \(a_{n-s} + a_{n-2s} < 2k\), donc
En particulier,
c'est-à-dire \(a_{n-1} = a_{n-4}\) et \(a_{n-2} = a_{n-8}\). Il découle du lemme 1 (appliqué de proche en proche) que \(a_{n-1}\) divise \(a_{n-1-3s}\) pour \(3s < n - 1\), et que \(a_{n-2}\) divise \(a_{n-2-6s}\) pour \(6s < n - 2\). Comme l'un au moins des nombres \(a_{n-1}\) et \(a_{n-2}\) vaut au moins \(a_n/2\), ce nombre divise un certain \(a_i\) avec \(i \leq 6\), donc \(a_n \leq 2\max(a_1, \ldots, a_6)\). Mais \(a_n\) peut être arbitrairement grand : contradiction. \(\square\)
Comme \((a_n)\) est bornée, il n'y a qu'un nombre fini de valeurs qui apparaissent un nombre fini de fois dans la suite. Autrement dit, il existe \(N\) tel que, si \(a_i = t\) avec \(i > N\), alors \(a_j = t\) pour une infinité de \(j\).
La suite \((a_{n+N})_{n > 0}\) vérifie clairement la condition de divisibilité, et il suffit de montrer qu'elle est périodique à partir d'un certain rang. Quitte à tronquer la suite, on peut donc supposer que chaque valeur apparaît une infinité de fois. Soit \(k\) la plus grande valeur apparaissant dans la suite.
Lemme 2. Si un entier \(d > 0\) divise \(a_n\) pour un certain \(n\), alors les indices \(i\) tels que \(d\) divise \(a_i\) forment une progression arithmétique de raison impaire.
Preuve. Soient \(i_1 < i_2 < i_3 < \cdots\) tous les indices \(i\) tels que \(d \mid a_i\). Si \(i_s + i_{s+1}\) est pair, le lemme 1 montre que \(d\) divise aussi \(a_{(i_s + i_{s+1})/2}\), ce qui est impossible puisque \(i_s < \frac{i_s + i_{s+1}}{2} < i_{s+1}\). Ainsi \(i_s\) et \(i_{s+1}\) sont toujours de parités différentes, donc \(i_s + i_{s+2}\) est pair. En appliquant de nouveau le lemme 1, \(d\) divise \(a_{(i_s + i_{s+2})/2}\) ; cet indice est strictement entre \(i_s\) et \(i_{s+2}\), donc \(\frac{i_s + i_{s+2}}{2} = i_{s+1}\). La suite \((i_s)\) est donc arithmétique, de raison impaire. \(\square\)
Nous pouvons maintenant conclure. L'ensemble des diviseurs positifs des termes de la suite est fini (la suite est bornée). Pour chacun de ces diviseurs \(s\), notons \(d_s\) la raison de la progression correspondante donnée par le lemme 2 : \(s\) divise \(a_n\) si et seulement s'il divise \(a_{n + t d_s}\), pour tout entier \(t > 0\). Soit \(D\) le produit de tous les \(d_s\). Alors tout \(s\) divisant un terme de la suite divise \(a_n\) si et seulement s'il divise \(a_{n+D}\). Les ensembles de diviseurs de \(a_n\) et de \(a_{n+D}\) coïncident donc, et \(a_{n+D} = a_n\). Ainsi \(D\) est une période de la suite. \(\blacksquare\)
Remarques¶
Remarque (structure de la partie périodique). La solution ne cherche pas la structure exacte de la partie périodique. Un petit complément montre que la période est de l'une des trois formes suivantes, où \(t\) est un entier positif quelconque (et les trois formes conviennent) :
- (i) \(t\) (la suite est stationnaire) ;
- (ii) \(t, 2t, 3t\) ou \(2t, t, 3t\) (période \(3\)) ;
- (iii) \(t, t, \ldots, t, 2t\) (la période peut être n'importe quel nombre impair).
Esquisse. Soit \(k\) la valeur maximale. Les indices \(i\) tels que \(a_i = k\) forment une progression arithmétique (lemme 2) ; si sa raison est \(1\), on est dans le cas (i). Sinon, sa raison \(T\) est impaire, au moins \(3\). Prenons \(n\) avec \(a_n = k\), et posons \(a = a_{n-2}\), \(b = a_{n-1}\) : on a \(a, b < k\), donc \(k = a_n = a + b\). Si \(a = b = k/2\), alors tous les termes \(a_1, \ldots, a_n\) sont divisibles par \(k/2\), donc égaux à \(k\) ou \(k/2\), et, comme les indices où \(a_i = k\) forment une progression de raison impaire, on obtient le cas (iii).
Si \(a \neq b\), on montre d'abord que, pour \(\frac{n}{2} < m < n\), on a \(a_m = a\) si \(m \equiv n - 2 \pmod 3\) et \(a_m = b\) si \(m \equiv n - 1 \pmod 3\). (En effet, \(k\) divise \(a_{n-2} + a_{n-1} = a + b\) et \(a_{n-4} + a_{n-2} = a_{n-4} + a\), d'où \(a_{n-1} = a_{n-4} = b\), \(a_{n-4} + a_{n-8} = k\) et \(a_{n-8} = a_{n-2} = a\) ; l'un de \(a\), \(b\) dépasse \(k/2\). Si \(b > k/2\), le lemme 1 donne \(a_{n-1-3s} = b\) pour \(3s < n - 1\), puis, pour \(6s < n - 4\), \(k\) divise \(a_{n-4-6s} + a_{n-2-3s} = b + a_{n-2-3s}\), donc \(a_{n-2-3s} = k - b = a\). Si \(a > k/2\), les indices \(i\) tels que \(a \mid a_i\) forment une progression de raison impaire divisant \(6\) et supérieure à \(1\), donc égale à \(3\) : \(a_{n-2-3s} = a\), et de même \(a_{n-1-3s} = b\).) En appliquant ceci à deux termes consécutifs \(a_n = a_{n+T} = k\) avec \(n\) grand, on voit que, pour un certain \(i\), \(a_{i+3s} = a\) et \(a_{i+1+3s} = b\) pour tout \(s\) ; quitte à tronquer, \(a_{3s+1} = a\), \(a_{3s+2} = b\), et \(a_n = k\) si et seulement si \(T \mid n\) (donc \(3 \mid T\)).
Si \(a_{3s} = c\), chacun des nombres \(a, b, c\) divise la somme des deux autres ; ils sont donc proportionnels, dans un certain ordre, à l'un des triplets \((1,1,1)\), \((1,1,2)\), \((1,2,3)\). Comme \(c = k = a + b\) pour une infinité de \(s\) et que \(c\) ne peut pas dépasser \(k\), les seules possibilités sont \(\{a, b\} = \{k/3, 2k/3\}\) et \(c \in \{k, k/3\}\). Si \(a_{3s} = k/3\) pour un certain \(s > 1\), on choisit \(s\) tel que \(a_{3s+3} = k\) ; comme \(T\) est impair, divisible par \(3\) et plus grand que \(3\), on a \(T \geq 9\), donc \(a_{3s-3} \neq k\) et \(a_{3s-3} = k/3\). Mais alors \(a_{3s+3} = k\) devrait diviser \(a_{3s} + a_{3s-3} = 2k/3\), impossible. Donc \(a_{3s} = k\) pour tout \(s > 1\) : c'est le cas (ii).