Shortlist 2011, N2¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Valuations p-adiques et lemme LTE · Principe des tiroirs
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 64 (page 65 du PDF)
Énoncé¶
On considère un polynôme \(P(x) = (x + d_1)(x + d_2) \cdot \ldots \cdot (x + d_9)\), où \(d_1, d_2, \ldots, d_9\) sont neuf entiers distincts. Montrer qu'il existe un entier \(N\) tel que, pour tout entier \(x \geq N\), le nombre \(P(x)\) soit divisible par un nombre premier strictement supérieur à \(20\).
Énoncé original (anglais)
Consider a polynomial \(P(x) = (x + d_1)(x + d_2) \cdot \ldots \cdot (x + d_9)\), where \(d_1, d_2, \ldots, d_9\) are nine distinct integers. Prove that there exists an integer \(N\) such that for all integers \(x \geq N\) the number \(P(x)\) is divisible by a prime number greater than \(20\).
Indices : les idées clés
- Huit premiers, neuf facteurs : il n'y a que huit nombres premiers inférieurs à \(20\), alors que \(P(x)\) a neuf facteurs.
- Tiroirs : si \(x + d_i\) est grand et n'a que de petits facteurs premiers, il a une grande puissance de premier \(f_i > d\) comme diviseur ; deux de ces puissances sont des puissances du même premier.
- Valuations : la plus petite des deux puissances divise alors \(d_i - d_j\), qui est trop petit — contradiction.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2011 (trois solutions et une remarque).
Solution 1¶
L'énoncé est invariant par translation de \(x\) ; on peut donc supposer sans perte de généralité que les nombres \(d_1, d_2, \ldots, d_9\) sont strictement positifs. L'observation clé est qu'il n'y a que huit nombres premiers inférieurs à \(20\), alors que \(P(x)\) a plus de huit facteurs.
Montrons que \(N = d^8\) convient, où \(d = \max\{d_1, d_2, \ldots, d_9\}\). Supposons par l'absurde qu'il existe un entier \(x \geq N\) tel que \(P(x)\) ne soit composé que de nombres premiers inférieurs à \(20\). Alors, pour chaque indice \(i \in \{1, 2, \ldots, 9\}\), le nombre \(x + d_i\) s'écrit comme produit de puissances des \(8\) premiers nombres premiers.
Comme \(x + d_i > x \geq d^8\), il existe une puissance de nombre premier \(f_i > d\) qui divise \(x + d_i\). Par le principe des tiroirs, il existe deux indices distincts \(i\) et \(j\) tels que \(f_i\) et \(f_j\) soient des puissances du même nombre premier. Par symétrie, on peut supposer \(f_i \leq f_j\). Alors les deux nombres \(x + d_i\) et \(x + d_j\) sont divisibles par \(f_i\), donc aussi leur différence \(d_i - d_j\). Mais comme
c'est impossible. Le problème est ainsi résolu. \(\blacksquare\)
Solution 2¶
Pour chaque indice \(i \in \{1, 2, \ldots, 9\}\), le produit
est strictement positif. Montrons que \(N = \max\{D_1 - d_1, D_2 - d_2, \ldots, D_9 - d_9\} + 1\) convient. Supposons qu'il existe un entier \(x \geq N\) tel que tous les nombres premiers divisant \(P(x)\) soient inférieurs à \(20\). Pour chaque indice \(i\), réduisons la fraction \((x + d_i)/D_i\) sous forme irréductible. Comme \(x + d_i > D_i\), le numérateur de la fraction obtenue ne peut pas valoir \(1\) ; il est donc divisible par un nombre premier \(p_i < 20\).
Par le principe des tiroirs, il existe un nombre premier \(p\) et deux indices distincts \(i\) et \(j\) tels que \(p_i = p_j = p\). Soient \(p^{\alpha_i}\) et \(p^{\alpha_j}\) les plus grandes puissances de \(p\) qui divisent \(x + d_i\) et \(x + d_j\) respectivement. Par symétrie, on peut supposer \(\alpha_i \leq \alpha_j\). Mais alors \(p^{\alpha_i}\) divise \(d_i - d_j\), donc aussi \(D_i\), ce qui signifie que toutes les occurrences de \(p\) dans le numérateur de la fraction \((x + d_i)/D_i\) se simplifient, contrairement au choix de \(p = p_i\). Cette contradiction prouve l'affirmation. \(\blacksquare\)
Solution 3¶
Pour un entier \(N\) non nul et un nombre premier \(p\), on note \(v_p(N)\) l'exposant de \(p\) dans la décomposition en facteurs premiers de \(\lvert N \rvert\).
Si l'énoncé était faux, il existerait une suite \((x_n)\) d'entiers strictement positifs tendant vers l'infini telle que, pour tout \(n \in \mathbb{Z}^+\), l'entier \(P(x_n)\) ne soit divisible par aucun nombre premier \(> 20\). Remarquons que les nombres \(-d_1, -d_2, \ldots, -d_9\) n'apparaissent pas dans cette suite.
Il existe clairement un nombre premier \(p_1 < 20\) pour lequel la suite \(v_{p_1}(x_n + d_1)\) n'est pas bornée ; quitte à extraire une sous-suite de \((x_n)\), on peut même supposer que
En répétant cet argument huit fois de plus, on peut de même choisir des nombres premiers \(p_2, \ldots, p_9 < 20\) et supposer que la suite \((x_n)\) a été suffisamment extraite pour que \(v_{p_i}(x_n + d_i) \longrightarrow \infty\) pour \(i = 2, \ldots, 9\) aussi. Par le principe des tiroirs, il existe deux indices distincts \(i\) et \(j\) et un nombre premier \(p < 20\) tels que \(p_i = p_j = p\). En posant \(k = v_p(d_i - d_j)\), il doit exister un \(n\) pour lequel \(v_p(x_n + d_i)\) et \(v_p(x_n + d_j)\) sont tous deux supérieurs à \(k\). Mais alors les nombres \(x_n + d_i\) et \(x_n + d_j\) sont divisibles par \(p^{k+1}\), alors que leur différence \(d_i - d_j\) ne l'est pas — contradiction. \(\blacksquare\)
Remarque¶
Ce problème est censé être relativement facile ; on pourrait donc envisager d'ajouter l'hypothèse que les nombres \(d_1, d_2, \ldots, d_9\) sont strictement positifs. Certaines questions purement techniques ne se poseraient alors pas, tandis que les idées principales nécessaires pour résoudre le problème resteraient les mêmes.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2022 N4 ★★☆☆☆ · OIM P5 : Résoudre \(a^p = b! + p\) avec \(p\) premier.
- 2013 N3 ★★☆☆☆ : Une infinité de \(n\) ont le même plus grand facteur premier pour \(n^4 + n^2 + 1\) et pour \((n + 1)^4 + (n + 1)^2 + 1\).
- 2009 N2 ★★☆☆☆ : Le nombre de facteurs premiers de \((n + a)(n + b)\) est-il toujours pair ? Possible sur \(50\) valeurs, impossible pour tout \(n\) si \(a \neq b\).
- 2014 N7 ★★★★☆ : Dans la suite \(a_{n+1} = a_n^3 - 4c a_n^2 + 5c^2 a_n + c\), chaque terme à partir du deuxième a un facteur premier nouveau.