Aller au contenu

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

\[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\).

  1. 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)\).

  2. 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.

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 ?