Shortlist 2015, N4¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : France
Concepts : Invariants et monovariants · Divisibilité, PGCD et algorithme d'Euclide · Suites et récurrences
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 68 (page 69 du PDF)
Énoncé¶
Suppose that \(a_0, a_1, \ldots\) and \(b_0, b_1, \ldots\) are two sequences of positive integers satisfying \(a_0, b_0 \geq 2\) and
for all \(n \geq 0\). Prove that the sequence \((a_n)\) is eventually periodic; in other words, there exist integers \(N \geq 0\) and \(t > 0\) such that \(a_{n+t} = a_n\) for all \(n \geq N\).
Indices : les idées clés
- Monovariant (solution 1) : avec \(s_n = a_n + b_n\), la quantité \(w_n\) = le plus petit \(m \geq a_n\) ne divisant pas \(s_n\) ne peut que décroître ; ensuite \(\gcd(w, s_n)\) est un invariant.
- PGCD et PPCM : \(\gcd(a_n, b_n) + \operatorname{lcm}(a_n, b_n)\) n'est pas divisible par \(a_n\) quand \(a_n \nmid b_n\).
- Suites récurrentes (solution 2) : une suite définie par \(u_{n+1} = F(u_n)\) à valeurs dans un ensemble fini est ultimement périodique ; on se ramène à un tel ensemble en réduisant \(b_n\) modulo \(M = \operatorname{lcm}(a_1, a_2, \ldots)\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et une remarque).
Solution 1¶
Posons \(s_n = a_n + b_n\). Si \(a_n \mid b_n\), alors \(a_{n+1} = a_n + 1\), \(b_{n+1} = b_n - 1\) et \(s_{n+1} = s_n\). Ainsi \(a_n\) augmente de \(1\) et \(s_n\) ne change pas jusqu'au premier indice où \(a_n \nmid s_n\). Définissons
Affirmation 1. La suite \((w_n)\) est décroissante (au sens large) : c'est un monovariant.
Preuve. Si \(a_n \mid b_n\), alors \(a_{n+1} = a_n + 1\) ; comme \(a_n \mid s_n\), on a \(a_n \notin W_n\). De plus \(s_{n+1} = s_n\), donc \(W_{n+1} = W_n\) et \(w_{n+1} = w_n\).
Sinon, \(a_n \nmid b_n\), donc \(a_n \nmid s_n\), d'où \(a_n \in W_n\) et \(w_n = a_n\). Montrons que \(a_n \in W_{n+1}\), ce qui donnera \(w_{n+1} \leq a_n = w_n\). Il faut \(a_n \geq a_{n+1}\) et \(a_n \nmid s_{n+1}\). La première relation vient de \(\gcd(a_n, b_n) < a_n\). Pour la seconde, dans \(s_{n+1} = \gcd(a_n, b_n) + \operatorname{lcm}(a_n, b_n)\), le second terme est divisible par \(a_n\), mais pas le premier. Donc \(a_n \nmid s_{n+1}\). \(\square\)
Soit \(w = \min_n w_n\) et \(N\) un indice tel que \(w_N = w\). D'après l'affirmation 1, \(w_n = w\) pour tout \(n \geq N\).
Posons \(g_n = \gcd(w, s_n)\). D'après ce qui précède, à partir de n'importe quel indice \(n \geq N\), la suite \(a_n, a_{n+1}, \ldots\) augmente de \(1\) jusqu'à atteindre \(w\), la première valeur qui ne divise pas \(s_n\), puis retombe à \(\gcd(w, s_n) + 1 = g_n + 1\).
Affirmation 2. La suite \((g_n)\) est constante pour \(n \geq N\).
Preuve. Si \(a_n \mid b_n\), alors \(s_{n+1} = s_n\) et \(g_{n+1} = g_n\). Sinon \(a_n = w\), \(\gcd(a_n, b_n) = \gcd(a_n, s_n) = \gcd(w, s_n) = g_n\), et
d'où
Soit \(g = g_N\). On a montré que la suite \((a_n)\) répète, à partir d'un certain rang, le cycle
Elle est donc ultimement périodique. \(\blacksquare\)
Solution 2¶
D'après l'affirmation 1 de la solution 1, \(a_n \leq w_n \leq w_0\) : la suite \((a_n)\) est bornée et ne prend qu'un nombre fini de valeurs.
Soit \(M = \operatorname{lcm}(a_1, a_2, \ldots)\) (bien défini car il n'y a qu'un nombre fini de valeurs), et soit \(r_n\) le reste de la division de \(b_n\) par \(M\). Pour tout \(n\), comme \(a_n \mid M \mid b_n - r_n\), on a \(\gcd(a_n, b_n) = \gcd(a_n, r_n)\), donc
De plus,
Ainsi le couple \((a_n, r_n)\) détermine de façon unique le couple \((a_{n+1}, r_{n+1})\). Comme il n'y a qu'un nombre fini de couples possibles, la suite des couples \((a_n, r_n)\) est ultimement périodique ; en particulier \((a_n)\) l'est. \(\blacksquare\)
Remarques¶
Remarque (les cycles possibles). Avec les notations de la solution 1, il n'y a que quatre possibilités :
donc \((a_n)\) finit par répéter l'un des cycles
En effet, pour \(n \geq N\), le cycle est \((g+1, \ldots, w)\) avec \(g = \gcd(w, s_n)\) ; d'après la preuve de l'affirmation 2, \(g+1, \ldots, w-1\) divisent tous \(s_n\), donc \(L = \operatorname{lcm}(g+1, \ldots, w-1)\) divise \(s_n\) ; de plus \(g \mid w\). Pour \(n \geq N\) avec \(a_n = w\), (1) donne
Comme \(L\) divise \(s_n\) et \(s_{n+1}\), il divise \(T = \frac{w^2 - g^2}{g}\).
Si \(w \geq 6\), alors \(g + 1 \leq \frac{w}{2} + 1 \leq w - 2\), donc \((w-2)(w-1) \mid L \mid T\). On a alors soit \(w^2 - g^2 \geq 2(w-1)(w-2)\), soit \(g = 1\) et \(w^2 - g^2 = (w-1)(w-2)\). Le premier cas donne \((w-1)(w-5) + (g^2 - 1) \leq 0\), faux pour \(w \geq 6\) ; le second s'écrit \(3w = 3\), soit \(w = 1\), impossible aussi. Il reste \(w \leq 5\) avec \(g \mid w\) ; le couple \((4, 1)\) viole \(L \mid T\) (\(6 \nmid 15\)), et les autres sont ceux de (2).
Le tableau suivant montre que les quatre cycles de (3) sont effectivement atteints :
| \((w, g)\) | \((a_n)\) | \((b_n)\) |
|---|---|---|
| \((2, 1)\) | \(a_n = 2\) | \(b_n = 2 \cdot 2^n + 1\) |
| \((3, 1)\) | \((a_{2k}, a_{2k+1}) = (2, 3)\) | \((b_{2k}, b_{2k+1}) = (6 \cdot 3^k + 2,\ 6 \cdot 3^k + 1)\) |
| \((4, 2)\) | \((a_{2k}, a_{2k+1}) = (3, 4)\) | \((b_{2k}, b_{2k+1}) = (12 \cdot 2^k + 3,\ 12 \cdot 2^k + 2)\) |
| \((5, 1)\) | \((a_{4k}, \ldots, a_{4k+3}) = (2, 3, 4, 5)\) | \((b_{4k}, \ldots, b_{4k+3}) = (6 \cdot 5^k + 4, \ldots, 6 \cdot 5^k + 1)\) |