Shortlist 2012, N8¶

Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : non indiqué

Concepts : Double comptage · Ordre d'un élément et racines primitives · Résidus quadratiques · Cauchy-Schwarz et lemme de Titu

Solution officielle : Shortlist officielle 2012 (avec solutions), p. 50 (page 50 du PDF)

Pas encore relu

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

Énoncé¶

Prove that for every prime \(p > 100\) and every integer \(r\) there exist two integers \(a\) and \(b\) such that \(p\) divides \(a^2 + b^5 - r\).

Indices : les idées clés

Double comptage (solution 1) : avec \(s_r\) le nombre de couples \((a, b)\) tels que \(a^2 + b^5 \equiv r\), le nombre \(N\) de quadruplets avec \(a^2 + b^5 \equiv c^2 + d^5\) vaut \(\sum_r s_r^2\) et est au plus \(p(p^2 + 4p - 4)\).
Puissances \(10\)-ièmes : si \(s_r = 0\), alors \(s_{tr} = 0\) pour toute puissance \(10\)-ième non nulle \(t\), ce qui donne au moins \(4\) classes vides ; l'inégalité quadratique-arithmétique donne alors \(N \geq \frac{p^4}{p - 4}\), trop grand.
Racine primitive (solution 2) : avec le critère d'Euler pour les non-résidus et des sommes géométriques de racines de l'unité, on obtient deux congruences sur \(r^{2k}\) incompatibles.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2012 (deux solutions et deux remarques).

Solution 1¶

Dans toute la solution, les congruences sont modulo \(p\).

Fixons \(p\), et soit \(P = \{0, 1, \ldots, p - 1\}\) l'ensemble des classes modulo \(p\). Pour tout \(r \in P\), posons \(S_r = \{(a, b) \in P \times P : a^2 + b^5 \equiv r\}\) et \(s_r = \lvert S_r \rvert\). On veut prouver que \(s_r > 0\) pour tout \(r \in P\).

On utilisera le fait bien connu suivant : pour toute classe \(r \in P\) et tout entier \(k \geq 1\), il y a au plus \(k\) valeurs \(x \in P\) telles que \(x^k \equiv r\).

Lemme. Soit \(N\) le nombre de quadruplets \((a, b, c, d) \in P^4\) tels que \(a^2 + b^5 \equiv c^2 + d^5\). Alors

\[N = \sum_{r \in P} s_r^2 \tag{a}\]

et

\[N \leq p(p^2 + 4p - 4). \tag{b}\]

Preuve. (a) Pour chaque classe \(r\), il y a exactement \(s_r\) couples \((a, b)\) tels que \(a^2 + b^5 \equiv r\) et \(s_r\) couples \((c, d)\) tels que \(c^2 + d^5 \equiv r\). Il y a donc \(s_r^2\) quadruplets tels que \(a^2 + b^5 \equiv c^2 + d^5 \equiv r\), et l'on somme sur \(r \in P\).

(b) Choisissons un couple \((b, d)\) quelconque et cherchons les valeurs possibles de \(a\) et \(c\).

Supposons \(b^5 \equiv d^5\), et soit \(k\) le nombre de tels couples \((b, d)\). On peut choisir \(b\) de \(p\) façons. Pour \(b \equiv 0\), seul \(d = 0\) convient ; pour \(b\) non nul, il y a au plus \(5\) valeurs possibles de \(d\). Donc \(k \leq 1 + 5(p - 1) = 5p - 4\). Les valeurs \(a\) et \(c\) doivent vérifier \(a^2 \equiv c^2\), donc \(a \equiv \pm c\), et il y a exactement \(2p - 1\) tels couples \((a, c)\).
Supposons \(b^5 \not\equiv d^5\). Alors \(a\) et \(c\) sont distincts. Comme \((a - c)(a + c) = d^5 - b^5\), la valeur de \(a - c\) détermine \(a + c\), donc \(a\) et \(c\). Il y a donc \(p - 1\) couples \((a, c)\) convenables.

Ainsi, pour chacun des \(k\) couples \((b, d)\) avec \(b^5 \equiv d^5\), il y a \(2p - 1\) couples \((a, c)\), et pour chacun des \(p^2 - k\) autres couples \((b, d)\), il y a \(p - 1\) couples \((a, c)\). Donc

\[N = k(2p - 1) + (p^2 - k)(p - 1) = p^2(p - 1) + kp \leq p^2(p - 1) + (5p - 4)p = p(p^2 + 4p - 4). \qquad \square\]

Pour prouver l'énoncé, supposons \(S_r = \varnothing\) pour un \(r \in P\) ; évidemment \(r \not\equiv 0\). Soit \(T = \{x^{10} : x \in P \setminus \{0\}\}\) l'ensemble des puissances \(10\)-ièmes non nulles modulo \(p\). Chaque classe est la puissance \(10\)-ième d'au plus \(10\) éléments de \(P\), donc \(\lvert T \rvert \geq \frac{p - 1}{10} \geq 4\) puisque \(p > 100\).

Pour tout \(t \in T\), on a \(S_{tr} = \varnothing\). En effet, si \((x, y) \in S_{tr}\) et \(t \equiv z^{10}\), alors

\[(z^{-5}x)^2 + (z^{-2}y)^5 \equiv t^{-1}(x^2 + y^5) \equiv r,\]

donc \((z^{-5}x, z^{-2}y) \in S_r\). Il y a donc au moins \(\frac{p - 1}{10} \geq 4\) ensembles vides parmi \(S_1, \ldots, S_{p-1}\), et au plus \(p - 4\) valeurs non nulles parmi les \(s_r\). Par l'inégalité entre moyennes arithmétique et quadratique,

\[N = \sum_{r \in P \setminus rT} s_r^2 \geq \frac{1}{p - 4}\Bigg(\sum_{r \in P \setminus rT} s_r\Bigg)^2 = \frac{\lvert P \times P \rvert^2}{p - 4} = \frac{p^4}{p - 4} > p(p^2 + 4p - 4),\]

ce qui contredit le lemme. \(\blacksquare\)

Solution 2¶

Si \(5 \nmid p - 1\), toutes les classes modulo \(p\) sont des puissances cinquièmes et l'énoncé est évident. Supposons donc \(p = 10k + 1\) avec \(k \geq 10\). Soit \(g\) une racine primitive modulo \(p\). On utilise les faits suivants :

(F1) Si une classe \(x\) n'est pas un carré, alors \(x^{(p-1)/2} \equiv -1 \pmod p\) (critère d'Euler).
(F2) Pour tout entier \(d\), comme conséquence simple de la formule de sommation des suites géométriques,

\[\sum_{i=0}^{2k-1} g^{5di} \equiv \begin{cases} 2k & \text{si } 2k \mid d, \\ 0 & \text{si } 2k \nmid d \end{cases} \pmod p.\]

Supposons, contrairement à l'énoncé, qu'une classe \(r\) ne puisse pas s'écrire \(a^2 + b^5\) modulo \(p\). Évidemment \(r \not\equiv 0 \pmod p\). Par (F1), \((r - b^5)^{(p-1)/2} = (r - b^5)^{5k} \equiv -1 \pmod p\) pour toute classe \(b\).

Pour \(t = 1, 2, \ldots, k - 1\), considérons les sommes

\[S(t) = \sum_{i=0}^{2k-1} \left(r - g^{5i}\right)^{5k} g^{5ti}.\]

Par l'hypothèse de l'absurde et (F2),

\[S(t) = \sum_{i=0}^{2k-1} \left(r - (g^i)^5\right)^{5k} g^{5ti} \equiv \sum_{i=0}^{2k-1} (-1) g^{5ti} \equiv -\sum_{i=0}^{2k-1} g^{5ti} \equiv 0 \pmod p,\]

puisque \(2k\) ne divise pas \(t\).

D'autre part, par la formule du binôme,

\[S(t) = \sum_{i=0}^{2k-1} \Bigg(\sum_{j=0}^{5k} \binom{5k}{j} r^{5k-j} \left(-g^{5i}\right)^j\Bigg) g^{5ti} = \sum_{j=0}^{5k} (-1)^j \binom{5k}{j} r^{5k-j} \Bigg(\sum_{i=0}^{2k-1} g^{5(j+t)i}\Bigg) \equiv \sum_{j=0}^{5k} (-1)^j \binom{5k}{j} r^{5k-j} \begin{cases} 2k & \text{si } 2k \mid j + t \\ 0 & \text{si } 2k \nmid j + t \end{cases} \pmod p.\]

Comme \(1 \leq j + t < 6k\), le nombre \(2k\) divise \(j + t\) seulement pour \(j = 2k - t\) et \(j = 4k - t\). Donc

\[0 \equiv S(t) \equiv (-1)^t \left(\binom{5k}{2k - t} r^{3k+t} + \binom{5k}{4k - t} r^{k+t}\right) \cdot 2k \pmod p,\]

\[\binom{5k}{2k - t} r^{2k} + \binom{5k}{4k - t} \equiv 0 \pmod p.\]

En écrivant cela pour \(t = 1, 2\) et en éliminant \(r\), on obtient

\[\begin{aligned} 0 &\equiv \binom{5k}{2k - 2}\left(\binom{5k}{2k - 1} r^{2k} + \binom{5k}{4k - 1}\right) - \binom{5k}{2k - 1}\left(\binom{5k}{2k - 2} r^{2k} + \binom{5k}{4k - 2}\right) \\ &= \binom{5k}{2k - 2}\binom{5k}{4k - 1} - \binom{5k}{2k - 1}\binom{5k}{4k - 2} \\ &= \frac{(5k)!^2}{(2k - 1)!\,(3k + 2)!\,(4k - 1)!\,(k + 2)!}\big((2k - 1)(k + 2) - (3k + 2)(4k - 1)\big) \\ &= \frac{-(5k)!^2 \cdot 2k(5k + 1)}{(2k - 1)!\,(3k + 2)!\,(4k - 1)!\,(k + 2)!} \pmod p. \end{aligned}\]

Mais dans cette dernière expression, aucun des nombres n'est divisible par \(p = 10k + 1\), une contradiction. \(\blacksquare\)

Remarques¶

Remarque 1. L'argument de la seconde solution est valable dès que \(k \geq 3\), c'est-à-dire pour tous les nombres premiers \(p = 10k + 1\) sauf \(p = 11\). C'est un cas exceptionnel où l'énoncé est faux : \(r = 7\) ne peut pas s'écrire comme voulu.

Remarque 2. L'énoncé est vrai dans un cadre plus général : pour tout entier \(n \geq 1\) et tout nombre premier \(p\) assez grand, chaque classe modulo \(p\) s'écrit \(a^2 + b^n\). On pourrait utiliser le théorème de Cauchy-Davenport (avec une analyse du cas d'égalité). Des résultats plus généraux sont connus dans la littérature ; par exemple, l'énoncé découle facilement de la borne de Hasse-Weil.