Aller au contenu

Shortlist 2014, N7

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

Concepts : Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Congruences, théorèmes de Fermat et d'Euler · Suites et récurrences · Valuations p-adiques et lemme LTE

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 82 (page 83 du PDF)

Énoncé

Let \(c \geq 1\) be an integer. Define a sequence of positive integers by \(a_1 = c\) and

\[a_{n+1} = a_n^3 - 4c \cdot a_n^2 + 5c^2 \cdot a_n + c\]

for all \(n \geq 1\). Prove that for each integer \(n \geq 2\) there exists a prime number \(p\) dividing \(a_n\) but none of the numbers \(a_1, \ldots, a_{n-1}\).

Indices : les idées clés
  • Normaliser : \(x_n = \frac{a_n}{c}\) (avec \(x_0 = 0\)) vérifie \(x_{n+1} = c^2(x_n^3 - 4x_n^2 + 5x_n) + 1\), suite strictement croissante d'entiers premiers avec \(c\).
  • Suite de divisibilité : \(i \equiv j \pmod m\) implique \(x_i \equiv x_j \pmod{x_m}\), et même modulo \(x_m^2\) si \(i, j \geq 2\) (congruences).
  • Diviseur premier nouveau : \(x_n > x_1 \cdots x_{n-2}\) fournit un premier \(p\) de plus grande valuation dans \(x_n\) que dans ce produit ; le plus petit \(k\) avec \(p \mid x_k\) diviserait \(n\), puis \(x_n \equiv x_k \pmod{x_k^2}\) contredit le choix de \(p\).
Solutions

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

Solution

Posons \(x_0 = 0\) et \(x_n = \frac{a_n}{c}\) pour tout entier \(n \geq 1\). On voit facilement que la suite \((x_n)\) ainsi obtenue vérifie la relation de récurrence

\[x_{n+1} = c^2(x_n^3 - 4x_n^2 + 5x_n) + 1 \tag{1}\]

pour tout entier \(n \geq 0\). En particulier, tous ses termes sont des entiers strictement positifs (à partir de \(x_1\)) ; on a \(x_1 = 1\) et \(x_2 = 2c^2 + 1\). Comme

\[x_{n+1} = c^2 x_n (x_n - 2)^2 + c^2 x_n + 1 > x_n \tag{2}\]

pour tout entier \(n \geq 0\), la suite est strictement croissante. Comme \(x_{n+1}\) est premier avec \(c\) par (1) pour tout \(n \geq 0\), il suffit de prouver que, pour tout \(n \geq 2\), il existe un nombre premier \(p\) qui divise \(x_n\) mais aucun des nombres \(x_1, \ldots, x_{n-1}\). Commençons par établir trois résultats préliminaires.

Affirmation 1. Si \(i \equiv j \pmod m\) pour des entiers \(i, j \geq 0\) et \(m \geq 1\), alors \(x_i \equiv x_j \pmod{x_m}\).

Preuve. Il suffit évidemment de montrer que \(x_{i+m} \equiv x_i \pmod{x_m}\) pour tous entiers \(i \geq 0\) et \(m \geq 1\). Pour \(m\) fixé, on procède par récurrence sur \(i\), le cas \(i = 0\) venant de \(x_0 = 0\). Si \(x_{i+m} \equiv x_i \pmod{x_m}\) pour un entier \(i\), la relation (1) donne

\[x_{i+m+1} \equiv c^2(x_{i+m}^3 - 4x_{i+m}^2 + 5x_{i+m}) + 1 \equiv c^2(x_i^3 - 4x_i^2 + 5x_i) + 1 \equiv x_{i+1} \pmod{x_m},\]

ce qui achève la récurrence. \(\square\)

Affirmation 2. Si les entiers \(i, j \geq 2\) et \(m \geq 1\) vérifient \(i \equiv j \pmod m\), alors \(x_i \equiv x_j \pmod{x_m^2}\).

Preuve. Là encore, il suffit de prouver que \(x_{i+m} \equiv x_i \pmod{x_m^2}\) pour tous entiers \(i \geq 2\) et \(m \geq 1\). Comme ci-dessus, on procède pour \(m\) fixé par récurrence sur \(i\). L'hérédité est encore facile avec (1), mais cette fois le cas \(i = 2\) demande un calcul. Posons \(L = 5c^2\). Par (1), \(x_{m+1} \equiv L x_m + 1 \pmod{x_m^2}\), donc

\[\begin{aligned} x_{m+1}^3 - 4x_{m+1}^2 + 5x_{m+1} &\equiv (Lx_m + 1)^3 - 4(Lx_m + 1)^2 + 5(Lx_m + 1) \\ &\equiv (3Lx_m + 1) - 4(2Lx_m + 1) + 5(Lx_m + 1) \equiv 2 \pmod{x_m^2}, \end{aligned}\]

ce qui donne bien \(x_{m+2} \equiv 2c^2 + 1 \equiv x_2 \pmod{x_m^2}\). \(\square\)

Affirmation 3. Pour tout entier \(n \geq 2\), on a \(x_n > x_1 \cdot x_2 \cdots x_{n-2}\).

Preuve. Les cas \(n = 2\) et \(n = 3\) sont clairs. Supposons l'affirmation vraie pour un \(n \geq 3\). On rappelle que \(x_2 \geq 3\) ; par monotonie et (2), \(x_n \geq x_3 \geq x_2(x_2 - 2)^2 + x_2 + 1 \geq 7\). Il s'ensuit que

\[x_{n+1} > x_n^3 - 4x_n^2 + 5x_n > 7x_n^2 - 4x_n^2 > x_n^2 > x_n x_{n-1},\]

ce qui, avec l'hypothèse de récurrence, donne \(x_{n+1} > x_1 \cdot x_2 \cdots x_{n-1}\). \(\square\)

Passons au problème lui-même. Soit \(n \geq 2\) un entier. Par l'affirmation 3, il existe un nombre premier \(p\) qui apparaît avec un exposant plus grand dans la décomposition de \(x_n\) que dans celle de \(x_1 \cdots x_{n-2}\). En particulier \(p \mid x_n\), et il suffit de prouver que \(p\) ne divise aucun des nombres \(x_1, \ldots, x_{n-1}\).

Sinon, soit \(k \in \{1, \ldots, n - 1\}\) minimal tel que \(p\) divise \(x_k\). Comme \(x_{n-1}\) et \(x_n\) sont premiers entre eux par (1) et que \(x_1 = 1\), on a en fait \(2 \leq k \leq n - 2\). Écrivons \(n = qk + r\) avec des entiers \(q \geq 0\) et \(0 \leq r < k\). Par l'affirmation 1, \(x_n \equiv x_r \pmod{x_k}\), donc \(p \mid x_r\). Par minimalité de \(k\), cela impose \(r = 0\), c'est-à-dire \(k \mid n\). L'affirmation 2 donne alors

\[x_n \equiv x_k \pmod{x_k^2}.\]

Soit \(\alpha \geq 1\) maximal tel que \(p^\alpha \mid x_k\). Alors \(x_k^2\) est divisible par \(p^{\alpha+1}\), et, par le choix de \(p\), \(x_n\) aussi. Par la congruence précédente, \(x_k\) est donc un multiple de \(p^{\alpha+1}\), ce qui contredit le choix de \(\alpha\). Cette contradiction achève la solution. \(\blacksquare\)