Shortlist 2009, N4¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : North Korea
Concepts : Descente infinie et Vieta jumping · Congruences, théorèmes de Fermat et d'Euler · Équations diophantiennes : factorisation et encadrement
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 73 (page 75 du PDF)
Énoncé¶
Find all positive integers \(n\) such that there exists a sequence of positive integers \(a_1, a_2, \ldots, a_n\) satisfying
for every \(k\) with \(2 \leq k \leq n - 1\).
Indices : les idées clés
- Parité modulo \(4\) : pour \(n = 5\), les relations \(a_{k}^2 + 1 = (a_{k-1} + 1)(a_{k+1} + 1)\) forcent \(a_2\), \(a_3\) pairs, donc \((x + 1) \mid y^2 + 1\) et \((y + 1) \mid x^2 + 1\) pour \(x\), \(y\) pairs.
- Équation de Markov : on obtient \(k(x + 1)(y + 1) = x^2 + y^2\), sans solution en entiers pairs par saut de Vieta.
- Exemple pour \(n = 4\) : \(4, 33, 217, 1384\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (deux solutions et deux remarques).
Solution 1¶
Réponse : \(n = 1, 2, 3, 4\).
Une telle suite existe pour \(n = 1, 2, 3, 4\) et pour aucun autre \(n\). Comme l'existence d'une telle suite pour un certain \(n\) implique son existence pour tout \(n\) plus petit, il suffit de prouver que \(n = 5\) est impossible et que \(n = 4\) est possible.
Supposons d'abord que, pour \(n = 5\), il existe une suite d'entiers strictement positifs \(a_1, a_2, \ldots, a_5\) vérifiant les conditions
Supposons \(a_1\) impair ; alors \(a_2\) doit être impair aussi, et comme alors \(a_2^2 + 1 \equiv 2 \pmod 4\), \(a_3\) doit être pair. Mais c'est une contradiction, puisque le nombre pair \(a_2 + 1\) ne peut pas diviser le nombre impair \(a_3^2 + 1\). Donc \(a_1\) est pair.
Si \(a_2\) est impair, \(a_3^2 + 1\) est pair (comme multiple de \(a_2 + 1\)), donc \(a_3\) est impair aussi. De même, \(a_4\) doit être impair. Mais alors \(a_3^2 + 1\) est un produit de deux nombres pairs \((a_2 + 1)(a_4 + 1)\), donc divisible par \(4\), ce qui est une contradiction puisque pour \(a_3\) impair on a \(a_3^2 + 1 \equiv 2 \pmod 4\).
Donc \(a_2\) est pair. De plus, \(a_3 + 1\) divise le nombre impair \(a_2^2 + 1\), donc \(a_3\) est pair. De même, \(a_4\) et \(a_5\) sont pairs aussi.
Posons maintenant \(x = a_2\) et \(y = a_3\). La condition donne \((x + 1) \mid (y^2 + 1)\) et \((y + 1) \mid (x^2 + 1)\). Montrons qu'il n'existe aucun couple d'entiers pairs strictement positifs \((x, y)\) vérifiant ces deux conditions, ce qui contredira l'hypothèse.
Supposons qu'il existe un couple \((x_0, y_0)\) d'entiers pairs strictement positifs vérifiant les deux conditions \((x_0 + 1) \mid (y_0^2 + 1)\) et \((y_0 + 1) \mid (x_0^2 + 1)\). On a alors \((x_0 + 1) \mid (y_0^2 + 1 + x_0^2 - 1)\), c'est-à-dire \((x_0 + 1) \mid (x_0^2 + y_0^2)\), et de même \((y_0 + 1) \mid (x_0^2 + y_0^2)\). Tout diviseur commun \(d\) de \(x_0 + 1\) et \(y_0 + 1\) doit donc aussi diviser le nombre \((x_0^2 + 1) + (y_0^2 + 1) - (x_0^2 + y_0^2) = 2\). Mais comme \(x_0 + 1\) et \(y_0 + 1\) sont tous deux impairs, on doit avoir \(d = 1\). Donc \(x_0 + 1\) et \(y_0 + 1\) sont premiers entre eux, et il existe par conséquent un entier \(k > 0\) tel que l'équation
ait la solution \((x_0, y_0)\). Montrons que cette dernière équation n'a aucune solution \((x, y)\) en entiers pairs strictement positifs.
Supposons qu'il y ait une solution. Prenons la solution \((x_1, y_1)\) de plus petite somme \(x_1 + y_1\), et supposons \(x_1 \geq y_1\). Alors \(x_1\) est solution de l'équation du second degré
Soit \(x_2\) la seconde solution, qui, d'après les relations de Viète, vérifie \(x_1 + x_2 = k(y_1 + 1)\) et \(x_1x_2 = y_1^2 - k(y_1 + 1)\). Si \(x_2 = 0\), la seconde équation implique \(y_1^2 = k(y_1 + 1)\), ce qui est impossible, car \(y_1 + 1 > 1\) ne peut pas diviser le nombre \(y_1^2\), qui lui est premier. Donc \(x_2 \neq 0\).
On obtient aussi \((x_1 + 1)(x_2 + 1) = x_1x_2 + x_1 + x_2 + 1 = y_1^2 + 1\), qui est impair, donc \(x_2\) doit être pair et strictement positif. De plus, \(x_2 + 1 = \frac{y_1^2 + 1}{x_1 + 1} \leq \frac{y_1^2 + 1}{y_1 + 1} \leq y_1 \leq x_1\). Cela signifie que le couple \((x', y')\) avec \(x' = y_1\) et \(y' = x_2\) est une autre solution de \(k(x + 1)(y + 1) = x^2 + y^2\) en entiers pairs strictement positifs, avec \(x' + y' < x_1 + y_1\), ce qui est une contradiction.
On doit donc avoir \(n \leq 4\).
Pour \(n = 4\), un exemple de suite possible est \(a_1 = 4\), \(a_2 = 33\), \(a_3 = 217\) et \(a_4 = 1384\). \(\blacksquare\)
Solution 2¶
On vérifie facilement que, pour \(n = 4\), la suite \(a_1 = 4\), \(a_2 = 33\), \(a_3 = 217\) et \(a_4 = 1384\) convient.
Supposons maintenant qu'il existe une suite avec \(n \geq 5\). On a en particulier
Supposons aussi, sans perte de généralité, que parmi tous ces quintuplets \((a_1, a_2, a_3, a_4, a_5)\) on en ait choisi un avec \(a_1\) minimal.
On montre rapidement le fait suivant :
Si trois entiers strictement positifs \(x\), \(y\), \(z\) vérifient \(y^2 + 1 = (x + 1)(z + 1)\) et si \(y\) est pair, alors \(x\) et \(z\) sont pairs aussi, et l'on a \(x < y < z\) ou \(z < y < x\). \(\quad (1)\)
En effet, la première partie est évidente, et de \(x < y\) on conclut
et de même dans l'autre cas.
Si \(a_3\) était impair, alors \((a_2 + 1)(a_4 + 1) = a_3^2 + 1 \equiv 2 \pmod 4\) impliquerait que l'un de \(a_2\) ou \(a_4\) est pair, ce qui contredit (1). Donc \(a_3\), et par conséquent aussi \(a_1\), \(a_2\), \(a_4\) et \(a_5\), sont pairs. D'après (1), on a \(a_1 < a_2 < a_3 < a_4 < a_5\) ou \(a_1 > a_2 > a_3 > a_4 > a_5\) ; mais, vu la minimalité de \(a_1\), c'est la première série d'inégalités qui doit être vraie.
Considérons l'identité
Tout diviseur commun des deux nombres impairs \(a_2 + 1\) et \(a_3 + 1\) doit aussi diviser \((a_2 + 1)(a_4 + 1) - (a_3 + 1)(a_3 - 1) = 2\), donc ces nombres sont premiers entre eux. La dernière identité montre donc que \(a_1 + a_3\) doit être un multiple de \(a_2 + 1\), c'est-à-dire qu'il existe un entier \(k\) tel que
Posons maintenant \(a_0 = k(a_1 + 1) - a_2\). C'est un entier, et l'on a
Donc \(a_0 \geq 0\). Si \(a_0 > 0\), d'après (1) on aurait \(a_0 < a_1 < a_2\), et le quintuplet \((a_0, a_1, a_2, a_3, a_4)\) contredirait la minimalité de \(a_1\).
Donc \(a_0 = 0\), ce qui implique \(a_2 = a_1^2\). Mais aussi \(a_2 = k(a_1 + 1)\), ce qui contredit finalement le fait que \(a_1 + 1 > 1\) est premier avec \(a_1^2\) et ne peut donc pas diviser ce nombre.
Donc \(n \geq 5\) est impossible. \(\blacksquare\)
Remarques¶
Remarque 1. Trouver l'exemple pour \(n = 4\) n'est pas immédiat et demande un calcul fastidieux, mais on peut le ramener à la vérification de quelques cas. Les équations \((a_1 + 1)(a_3 + 1) = a_2^2 + 1\) et \((a_2 + 1)(a_4 + 1) = a_3^2 + 1\) impliquent, comme on l'a vu dans la preuve, que \(a_1\) est pair et que \(a_2\), \(a_3\), \(a_4\) sont impairs. Le cas \(a_1 = 2\) donne \(a_2^2 \equiv -1 \pmod 3\), ce qui est impossible. Donc \(a_1 = 4\) est la plus petite possibilité. Dans ce cas, \(a_2^2 \equiv -1 \pmod 5\) et \(a_2\) est impair, ce qui implique \(a_2 \equiv 3\) ou \(a_2 \equiv 7 \pmod{10}\). Il faut donc essayer \(a_2 = 7, 13, 17, 23, 27, 33\), et le dernier cas réussit.
Remarque 2. Le choix \(a_0 = k(a_1 + 1) - a_2\) dans la seconde solution paraît plus naturel si l'on remarque que, d'après les calculs précédents, on a \(a_1 = k(a_2 + 1) - a_3\) et \(a_2 = k(a_3 + 1) - a_4\). Autrement, on peut résoudre l'équation (2) en \(a_3\) et utiliser \(a_2^2 + 1 = (a_1 + 1)(a_3 + 1)\) pour obtenir \(a_2^2 - k(a_1 + 1)a_2 + a_1^2 - k(a_1 + 1) = 0\). Alors \(a_0\) est la seconde solution de cette équation du second degré en \(a_2\) (saut de Vieta).