Shortlist 2024, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : France
Concepts : Congruences, théorèmes de Fermat et d'Euler · Résidus quadratiques · Principe des tiroirs · Double comptage
Solution officielle : Shortlist officielle 2024 (avec solutions), section N6 (livret PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(n\) be a positive integer. We say that a polynomial \(P\) with integer coefficients is \(n\)-good if there exists a polynomial \(Q\) of degree \(2\) with integer coefficients such that \(Q(k)\big(P(k) + Q(k)\big)\) is never divisible by \(n\) for any integer \(k\).
Determine all integers \(n\) such that every polynomial with integer coefficients is an \(n\)-good polynomial.
Indices : les idées clés
- Congruences, théorèmes de Fermat et d'Euler : si \(P\) est \(d\)-bon et \(d \mid n\), alors \(P\) est \(n\)-bon ; on se ramène à \(n = 4\) et \(n = p\) premier impair, puis à des fonctions modulo \(p\).
- Résidus quadratiques : avec \(r\) non-résidu, \(Q(X) = a(X^2 - r)\) ne s'annule jamais modulo \(p\) ; un produit qui devrait être un carré ne l'est pas (solution 2).
- Principe des tiroirs : \(p\) entrées pour \(p-1\) valeurs non nulles forcent une coïncidence \(f(x_1) = f(x_2)\) (solutions 1 à 3).
- Double comptage (solution 3) : on compte les couples \((b, c)\) associés à chaque paire \(\{x_1, x_2\}\).
- Méthode probabiliste (solution 4) : un polynôme \(Q\) aléatoire, et l'espérance de \((T-1)(T-3)(T-4)\) qui est négative.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (quatre solutions et cinq remarques).
Réponse : ce sont tous les entiers \(n \geq 3\).
Solution 1¶
Les cas \(n = 1\) et \(n = 2\). Aucun polynôme n'est \(1\)-bon (tout entier est divisible par \(1\)), et le polynôme \(P(X) = 1\) n'est pas \(2\)-bon, car \(Q(X)(Q(X) + 1)\) est toujours pair.
Réduction. Si \(P\) est \(d\)-bon avec un certain \(Q\), alors \(Q(P + Q)\) ne s'annule jamais modulo \(d\), donc a fortiori jamais modulo \(n\) pour tout multiple \(n\) de \(d\) : \(P\) est \(n\)-bon. Comme tout \(n \geq 3\) est divisible par \(4\) ou par un premier impair, il suffit de montrer que tout polynôme est \(n\)-bon pour \(n = 4\) et pour \(n\) premier impair.
Le cas \(n = 4\). On construit \(Q\) tel que \(Q(X)\) ne soit jamais divisible par \(4\) et que \(Q(X) + P(X)\) soit toujours impair ; cela suffit. Toute fonction modulo \(2\) est constante ou affine : il existe \(a, b \in \{0, 1\}\) tels que \(P(X) \equiv aX + b \pmod 2\) pour tout \(X\). Si \(a = 0\), on pose \(Q(X) = 4X^2 + b + 1\) ; si \(a = 1\), on pose \(Q(X) = X^2 + b + 1\) (on utilise \(X^2 + X \equiv 0 \pmod 2\)). Dans tous les cas, \(Q\) convient.
Le cas \(n = p\) premier impair. On va montrer que, pour toute fonction \(f\) définie modulo \(p\), il existe un polynôme \(Q\) de degré \(2\) sans racine modulo \(p\) tel que \(Q(x) \not\equiv f(x) \pmod p\) pour tout \(x\) ; l'énoncé pour \(P\) en découle avec \(f = -P\). Toutes les égalités qui suivent sont modulo \(p\).
Supposons qu'il existe une fonction \(f\) qui ne vérifie pas cela : pour tout \(Q\) de degré \(2\) sans racine, il existe \(x\) tel que \(Q(x) = f(x)\).
On peut supposer que \(f\) ne s'annule pas. En effet, si \(f(u) = 0\), soit \(g\) la fonction égale à \(f\) sauf en \(u\), avec \(g(u) = 1\). Pour tout \(Q\) sans racine, il existe \(x\) avec \(Q(x) = f(x)\), et \(x \neq u\) puisque \(Q(u) \neq 0\) ; donc \(Q(x) = g(x)\). Ainsi \(g\) est aussi un contre-exemple, et on répète l'opération.
\(f\) atteint toutes les valeurs non nulles. Sinon, si \(t \neq 0\) n'est pas atteint, le polynôme \(Q(X) = pX^2 + t\) n'est jamais égal à \(f\) et ne s'annule jamais. Comme il y a \(p\) valeurs de \(x\) et \(p - 1\) résidus non nuls, par le principe des tiroirs il existe \(x_1 \neq x_2\) avec \(f(x_1) = f(x_2)\), et \(f\) est une bijection de l'ensemble des résidus distincts de \(x_2\) sur l'ensemble des résidus non nuls.
On peut supposer \(f(1) = f(-1)\). Pour \(b \neq 0\) et \(c\) quelconques, on peut remplacer \(f(X)\) par \(g(X) = f(bX + c)\) : si un \(Q\) sans racine vérifie \(Q(x) \neq g(x)\) pour tout \(x\), alors \(Q\big((X - c)/b\big)\) (avec l'inverse de \(b\) modulo \(p\)) convient pour \(f\). On choisit \(b = \frac{x_1 - x_2}{2}\) et \(c = \frac{x_1 + x_2}{2}\), de sorte que \(b + c = x_1\) et \(-b + c = x_2\) ; alors \(g(1) = g(-1)\). Le livret écrit les conditions sous la forme \(bx_1 + c = 1\), \(bx_2 + c = -1\), ce qui correspond au changement de variable inverse ; nous l'avons rectifié. On renomme \(g\) en \(f\).
Conclusion. Soit \(r'\) un non-résidu quadratique modulo \(p\). On choisit \(y\) tel que \(f(y) = (1 - r')f(0)\) : il existe car le membre de droite est non nul, et \(y \neq 0\) car \(1 - r' \neq 1\). On pose \(r = \frac{y^2}{r'}\), qui est un non-résidu quadratique.
Considérons \(\varphi(X) = \frac{f(X)}{X^2 - r}\) (le dénominateur ne s'annule pas). Par construction \(\varphi(1) = \varphi(-1)\), et
L'image de \(\varphi\) contient donc au plus \(p - 2\) valeurs, toutes non nulles. On choisit \(a \neq 0\) hors de l'image de \(\varphi\) : \(\frac{f(X)}{X^2 - r}\) ne vaut jamais \(a\). Le polynôme \(Q(X) = a(X^2 - r)\) ne s'annule jamais et n'est jamais égal à \(f(X)\), ce qui contredit l'hypothèse. \(\blacksquare\)
Solution 2¶
On reprend la réduction de la solution 1 : \(f\) est une fonction modulo \(p\) qui atteint toutes les valeurs non nulles, sans racine, avec \(f(1) = f(-1)\). On donne une autre construction d'un \(Q\) de degré \(2\) sans racine tel que \(Q(x) \neq f(x)\) pour tout \(x\).
Soit \(r\) le plus petit non-résidu quadratique modulo \(p\) (de sorte que \(r - 1\) est un carré non nul). Pour \(a\) non nul, posons \(Q_a(X) = a(X^2 - r)\) : ces polynômes ne s'annulent jamais.
Supposons qu'aucun \(Q_a\) ne convienne. Pour chaque \(a\), il existe \(x\) tel que \(a(x^2 - r) = f(x)\), et on peut supposer \(x \neq -1\) (si l'égalité a lieu pour \(x = -1\), elle a aussi lieu pour \(x = 1\)). Or \(a(x^2 - r) = f(x)\) équivaut à \(a = \frac{f(x)}{x^2 - r}\) ; donc \(x \mapsto \frac{f(x)}{x^2 - r}\) est une surjection de \(\{x \neq -1\}\) sur les \(p - 1\) résidus non nuls, donc une bijection. Pour chaque \(a\), il existe un unique \(x_a \neq -1\) tel que \(f(x_a) = a(x_a^2 - r)\).
On a alors
la première égalité venant de ce que \(f\) réalise une bijection de \(\{x \neq -1\}\) sur les résidus non nuls. Les deux produits se simplifient : \(\prod_{x \neq -1}(x^2 - r) = 1\). Mais, en regroupant \(x\) et \(-x\),
C'est une contradiction, car \(-r(1 - r) = r(r - 1)\) n'est pas un résidu quadratique (produit d'un non-résidu et d'un carré non nul), alors que \(1\) en est un. \(\blacksquare\)
Solution 3¶
Comme dans la solution 1, on se ramène au cas d'un premier impair \(p\) et d'une fonction \(f\) modulo \(p\) sans racine, qui atteint toutes les valeurs non nulles ; on ne fait aucune hypothèse sur les \(x_1\), \(x_2\) tels que \(f(x_1) = f(x_2)\).
On considère les polynômes \(Q_{a,b,c}(X) = a\,R(bX + c)\), où \(R(X) = X^2 - r\) pour un non-résidu quadratique \(r\) fixé, \(a\) et \(b\) non nuls et \(c\) quelconque.
Pour \(b\) et \(c\) fixés, il y a exactement \(p\) couples \((a, x)\) tels que \(a\,R(bx + c) = f(x)\), car chaque \(x\) détermine une unique valeur de \(a\). Si un \(a\) n'apparaît dans aucun couple, on a gagné ; sinon, il y a exactement un \(a\) associé à deux valeurs de \(x\), et tous les autres à une seule. Autrement dit, pour chaque \((b, c)\), il existe exactement une paire non ordonnée \(\{x_1, x_2\}\) telle que
Montrons qu'à chaque paire \(\{x_1, x_2\}\) correspond au moins un couple \((b, c)\). Soit \(t = \frac{f(x_1)}{f(x_2)}\). Il existe \(x_1'\), \(x_2'\) tels que \(\frac{R(x_1')}{R(x_2')} = t\), car \(R\) et \(tR\) prennent chacun \(\frac{p+1}{2}\) valeurs non nulles, et ces deux ensembles se rencontrent par le principe des tiroirs (il n'y a que \(p - 1\) valeurs non nulles). On choisit \(b\), \(c\) tels que \(bx_1 + c = x_1'\) et \(bx_2 + c = x_2'\).
Si \((b, c)\) et \(\{x_1, x_2\}\) vérifient la relation, il en est de même de \((-b, -c)\), car \(R(bx + c) = R(-bx - c)\). Comme \(b \neq 0\), chaque paire correspond donc à au moins deux couples \((b, c)\). Mais il y a \(p(p-1)\) couples \((b, c)\) avec \(b \neq 0\), et \(\frac{p(p-1)}{2}\) paires \(\{x_1, x_2\}\) : par double comptage, chaque paire correspond à exactement deux couples, \((b, c)\) et \((-b, -c)\).
Or l'image de \(f\) n'a que \(p - 1\) éléments, donc il existe \(x_1 \neq x_2\) avec \(f(x_1) = f(x_2)\). Tout couple \((b, c)\) tel que \(bx_1 + c = -(bx_2 + c)\) donne \(R(bx_1 + c) = R(bx_2 + c)\), donc la relation pour \(\{x_1, x_2\}\). Un tel \(c\) existe pour tout \(b\) non nul, ce qui fait au moins \(p - 1\) couples, plus que \(2\) dès que \(p \geq 5\) : contradiction.
Enfin, pour \(p = 3\) : pour chaque \(x\), il reste au moins une valeur permise pour \(Q(x)\) (différente de \(0\) et de \(f(x)\)), donc un tel \(Q\) existe par interpolation de Lagrange (quitte à ajouter \(3X^2\) pour qu'il soit de degré \(2\)). \(\blacksquare\)
Solution 4¶
On se ramène encore au cas d'un premier impair \(p\) et d'une fonction \(f\) modulo \(p\) (sans racine, comme dans la solution 1) ; on cherche un \(Q\) de degré \(2\), jamais nul, tel que \(Q(x) = f(x)\) n'ait pas de solution. Le cas \(p = 3\) se traite comme dans la solution 3 ; on suppose \(p \geq 5\).
On prouve l'énoncé plus général suivant : soit \(p \geq 5\) premier et \(A_1, \ldots, A_p\) des parties de \(\mathbb{Z}/p\mathbb{Z}\) de cardinal \(2\). Il existe un polynôme \(Q \in \mathbb{Z}/p\mathbb{Z}[X]\) de degré au plus \(2\) tel que \(Q(i) \notin A_i\) pour tout \(i\). On l'applique avec \(A_i = \{0, f(i)\}\) (en ajoutant \(pX^2\) si nécessaire).
On choisit les coefficients de \(Q\) uniformément au hasard dans \(\mathbb{Z}/p\mathbb{Z}\), et on note \(T\) le nombre d'indices \(i\) tels que \(Q(i) \in A_i\). Pour \(k \leq 3\),
En effet, si \(S \subseteq \mathbb{Z}/p\mathbb{Z}\) est de cardinal \(k\) et \((a_i)_{i \in S}\) est un \(k\)-uplet, la probabilité que \(Q(i) = a_i\) sur \(S\) vaut \(p^{-k}\) (par interpolation de Lagrange pour \(k = 3\), puis en sommant pour \(k < 3\)). L'espérance est donc le nombre de parties \(S\) de cardinal \(k\) multiplié par la probabilité que \(Q(i) \in A_i\) pour tout \(i \in S\), soit \(2^k p^{-k}\).
On a l'identité \((t-1)(t-3)(t-4) = -12 + 12\binom{t}{1} - 10\binom{t}{2} + 6\binom{t}{3}\), donc
Cette quantité est négative pour \(p \geq 5\). Comme \((t-1)(t-3)(t-4) \geq 0\) pour tout entier \(t > 0\), l'événement \(T = 0\) a une probabilité strictement positive : il existe \(Q\) tel que \(Q(i) \notin A_i\) pour tout \(i\). \(\blacksquare\)
Remarques¶
Remarque 1 (solution 1). Il n'est pas nécessaire de passer des polynômes aux fonctions, car toute fonction modulo \(p\) est polynomiale. Par exemple, au lieu de passer de \(f\) à \(g\), on peut remplacer \(P(X)\) par \(P(X) + 1 - (X - u)^{p-1}\), qui ne change (modulo \(p\)) qu'en \(X = u\).
Remarque 2 (solution 2). Par le théorème de Wilson, le produit des résidus non nuls vaut \(-1\) ; ce fait n'est pas nécessaire ici.
Remarque 3 (solution 2). On peut calculer exactement \(\prod_{x \neq -1}(x^2 - r) = \frac{-4r}{1 - r}\). En effet, \(X^{\frac{p-1}{2}} - 1\) a pour racines les \(\frac{p-1}{2}\) résidus quadratiques, donc \(\prod_{s \text{ résidu}}(X - s) = X^{\frac{p-1}{2}} - 1\) et \(\prod_{x \neq 0}(X - x^2) = \big(X^{\frac{p-1}{2}} - 1\big)^2\) ; avec le critère d'Euler \(r^{\frac{p-1}{2}} = -1\), on obtient le résultat. On peut donc remplacer la condition « \(r\) est le plus petit non-résidu » par « \(r\) est un non-résidu différent de \(-\frac{1}{3}\) » (possible pour tout \(p \geq 3\)).
Remarque 4 (cas \(p = 3\)). On peut aussi traiter \(p = 3\) directement : on peut supposer \(f\) sans racine et atteignant \(1\) et \(2\), donc ses valeurs sont \((1, 1, 2)\) ou \((1, 2, 2)\) dans un certain ordre ; quitte à changer de variable, \(f(1) = f(2)\), donc \((f(0), f(1), f(2)) = (1, 2, 2)\) ou \((2, 1, 1)\). Dans le premier cas \(Q(X) = 2X^2 + 2\) convient, dans le second \(Q(X) = X^2 + 1\). C'est en quelque sorte l'approche par interpolation de Lagrange.
Remarque 5 (solution 4). On n'a guère de liberté pour remplacer \(R(T) = (T-1)(T-3)(T-4)\). On peut montrer (en comparant les coefficients des \(\binom{T}{k}\)) que, si \(R\) est de degré au plus \(3\), l'espérance de \(R(T)\) tend vers \(\frac{1}{3}\big(R(4) + 2R(1)\big)\) quand \(p\) tend vers l'infini ; \(R\) doit donc s'annuler en \(1\) et en \(4\). Ainsi \(R(T) = (T-1)(T-4)(T-d)\) avec \(d \geq 3\), et si \(d < 4\), l'argument fonctionne pour tout \(p > \frac{4}{4 - d}\).