Shortlist 2013, N3

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

Concepts : Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Principe extrémal · Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 55 (page 55 du PDF)

Énoncé

Prove that there exist infinitely many positive integers \(n\) such that the largest prime divisor of \(n^4 + n^2 + 1\) is equal to the largest prime divisor of \((n + 1)^4 + (n + 1)^2 + 1\).

Indices : les idées clés

• Factoriser : \(n^4 + n^2 + 1 = (n^2 - n + 1)(n^2 + n + 1) = \big((n-1)^2 + (n-1) + 1\big)(n^2 + n + 1)\) ; avec \(q_n\) le plus grand facteur premier de \(n^2 + n + 1\), on a \(p_n = \max(q_n, q_{n-1})\) et \(p_n = q_{n^2}\).
• PGCD : \(n^2 + n + 1\) et \(n^2 - n + 1\) sont premiers entre eux, donc \(q_n \neq q_{n-1}\).
• Principe extrémal : il suffit qu'il y ait une infinité de « pics » \(q_{n-1} < q_n > q_{n+1}\) ; une croissance indéfinie est exclue par \(q_{(k+1)^2} = \max(q_k, q_{k+1})\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2013 (une solution et une remarque).

Solution

Soit \(p_n\) le plus grand diviseur premier de \(n^4 + n^2 + 1\) et \(q_n\) celui de \(n^2 + n + 1\). Alors \(p_n = q_{n^2}\), et de

\[n^4 + n^2 + 1 = (n^2 + 1)^2 - n^2 = (n^2 - n + 1)(n^2 + n + 1) = \big((n - 1)^2 + (n - 1) + 1\big)(n^2 + n + 1)\]

on déduit \(p_n = \max\{q_n, q_{n-1}\}\) pour \(n \geq 2\). Comme \(n^2 - n + 1\) est impair,

\[\operatorname{pgcd}(n^2 + n + 1, n^2 - n + 1) = \operatorname{pgcd}(2n, n^2 - n + 1) = \operatorname{pgcd}(n, n^2 - n + 1) = 1.\]

Donc \(q_n \neq q_{n-1}\).

Pour prouver le résultat, il suffit de montrer que l'ensemble

\[S = \{n \in \mathbb{Z}_{\geq 2} \mid q_n > q_{n-1} \text{ et } q_n > q_{n+1}\}\]

est infini, puisque pour tout \(n \in S\),

\[p_n = \max\{q_n, q_{n-1}\} = q_n = \max\{q_n, q_{n+1}\} = p_{n+1}.\]

Supposons au contraire \(S\) fini. Comme \(q_2 = 7 < 13 = q_3\) et \(q_3 = 13 > 7 = q_4\), l'ensemble \(S\) n'est pas vide. Comme il est fini, on peut considérer son plus grand élément \(m\).

Il est impossible que \(q_m > q_{m+1} > q_{m+2} > \cdots\), car ce sont tous des entiers strictement positifs ; il existe donc \(k \geq m\) tel que \(q_k < q_{k+1}\) (on rappelle que \(q_k \neq q_{k+1}\)). Ensuite, il est impossible d'avoir \(q_k < q_{k+1} < q_{k+2} < \cdots\), car \(q_{(k+1)^2} = p_{k+1} = \max\{q_k, q_{k+1}\} = q_{k+1}\). Prenons donc le plus petit \(\ell \geq k + 1\) tel que \(q_\ell > q_{\ell+1}\). Par minimalité de \(\ell\), on a \(q_{\ell-1} < q_\ell\), donc \(\ell \in S\). Comme \(\ell \geq k + 1 > k \geq m\), cela contredit la maximalité de \(m\) ; l'ensemble \(S\) est donc bien infini. \(\blacksquare\)

Remarque

Une fois trouvée la factorisation de \(n^4 + n^2 + 1\) et introduit l'ensemble \(S\), le problème consiste surtout à exclure que

\[q_k < q_{k+1} < q_{k+2} < \cdots \tag{1}\]

pour un certain \(k \in \mathbb{Z}_{>0}\). Dans la solution, on le fait en observant que \(q_{(k+1)^2} = \max(q_k, q_{k+1})\). On peut aussi remarquer que (1) implique \(q_{j+2} - q_j \geq 6\) pour \(j \geq k + 1\), puisque tout nombre premier supérieur à \(3\) est congru à \(-1\) ou \(1\) modulo \(6\). Il existe alors un entier \(C \geq 0\) tel que \(q_n \geq 3n - C\) pour tout \(n \geq k\).

Soit alors \(t\) un entier assez grand (par exemple \(t = \max\{k + 1, C + 3\}\)) et \(p = q_{t-1} \geq 2t\). Alors \(p \mid (t - 1)^2 + (t - 1) + 1\) implique \(p \mid (p - t)^2 + (p - t) + 1\), donc \(p\) et \(q_{p-t}\) sont des diviseurs premiers de \((p - t)^2 + (p - t) + 1\). Mais \(p - t > t - 1 \geq k\), donc \(q_{p-t} > q_{t-1} = p\), et \(p \cdot q_{p-t} > p^2 > (p - t)^2 + (p - t) + 1\), une contradiction.