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)
Énoncé¶
Montrer que, pour tout nombre premier \(p > 100\) et tout entier \(r\), il existe deux entiers \(a\) et \(b\) tels que \(p\) divise \(a^2 + b^5 - r\).
Énoncé original (anglais)
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
et
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
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
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,
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
Par l'hypothèse de l'absurde et (F2),
puisque \(2k\) ne divise pas \(t\).
D'autre part, par la formule du binôme,
Comme \(1 \leq j + t < 6k\), le nombre \(2k\) divise \(j + t\) seulement pour \(j = 2k - t\) et \(j = 4k - t\). Donc
En écrivant cela pour \(t = 1, 2\) et en éliminant \(r\), on obtient
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.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 C7 ★★★★☆ : Trianguler un \(100\)-gone avec \(2025\) points : combien de paires de triangles adjacents forment au minimum un quadrilatère convexe ?
- 2024 N6 ★★★★☆ : Pour quels \(n\) tout polynôme entier \(P\) admet-il un \(Q\) de degré \(2\) tel que \(Q(k)(P(k) + Q(k))\) ne soit jamais divisible par \(n\) ?
- 2022 C8 ★★★★☆ · OIM P6 : Remplir un tableau \(n \times n\) de \(1\) à \(n^2\) avec le moins possible de chemins croissants partant d'un minimum local.
- 2011 C7 ★★★★★ : Des serviettes \(52 \times 52\) sur une table \(2011 \times 2011\) : combien de cases au plus peuvent porter le même nombre non nul ?