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)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

É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\)