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é¶
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.