Aller au contenu

Shortlist 2017, N8

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

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Résidus quadratiques · Partie entière et majorations

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 88 (page 90 du PDF)

Énoncé

Soit \(p\) un nombre premier impair, et notons \(\mathbb{Z}_{>0}\) l'ensemble des entiers strictement positifs. On suppose qu'une fonction \(f : \mathbb{Z}_{>0} \times \mathbb{Z}_{>0} \to \{0, 1\}\) vérifie les propriétés suivantes :

  • \(f(1, 1) = 0\) ;
  • \(f(a, b) + f(b, a) = 1\) pour tout couple \((a, b)\) d'entiers strictement positifs premiers entre eux qui ne sont pas tous deux égaux à \(1\) ;
  • \(f(a + b, b) = f(a, b)\) pour tout couple \((a, b)\) d'entiers strictement positifs premiers entre eux.

Montrer que

\[\sum_{n=1}^{p-1} f(n^2, p) \geq \sqrt{2p} - 2.\]
Énoncé original (anglais)

Let \(p\) be an odd prime number and \(\mathbb{Z}_{>0}\) be the set of positive integers. Suppose that a function \(f : \mathbb{Z}_{>0} \times \mathbb{Z}_{>0} \to \{0, 1\}\) satisfies the following properties:

  • \(f(1, 1) = 0\);
  • \(f(a, b) + f(b, a) = 1\) for any pair of relatively prime positive integers \((a, b)\) not both equal to \(1\);
  • \(f(a + b, b) = f(a, b)\) for any pair of relatively prime positive integers \((a, b)\).

Prove that

\[\sum_{n=1}^{p-1} f(n^2, p) \geq \sqrt{2p} - 2.\]
Indices : les idées clés
  • Deviner puis prouver le lemme clé : si \(ua + vb = 1\) avec \(-b/2 < u \leq b/2\), alors \(f(a, b) = 1 \iff u > 0\), c'est-à-dire ssi l'inverse de \(a\) modulo \(b\) est au plus \(b/2\).
  • Divisibilité, PGCD et algorithme d'Euclide : relation de Bézout, récurrence calquée sur l'algorithme d'Euclide (solution 1) ou fractions continues (solution 2).
  • Résidus quadratiques : la somme vaut deux fois le nombre de résidus quadratiques non nuls inférieurs à \(p/2\) ; les remarques utilisent le symbole de Legendre.
  • Partie entière et majorations : les carrés parfaits de \([1, p/2)\) sont au nombre de \(\lfloor \sqrt{p/2} \rfloor > \sqrt{p/2} - 1\).
Solutions

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

Solution 1

Notons \(\mathbb{A}\) l'ensemble des couples d'entiers strictement positifs premiers entre eux. Pour tout \((a, b) \in \mathbb{A}\), il existe un couple \((u, v) \in \mathbb{Z}^2\) tel que \(ua + vb = 1\) (Bézout). De plus, si \((u_0, v_0)\) est un tel couple, tous les autres sont de la forme \((u, v) = (u_0 + kb, v_0 - ka)\) avec \(k \in \mathbb{Z}\). Il existe donc un unique tel couple avec \(-b/2 < u \leq b/2\) ; on le note \((u, v) = g(a, b)\).

Lemme. Soient \((a, b) \in \mathbb{A}\) et \((u, v) = g(a, b)\). Alors \(f(a, b) = 1 \iff u > 0\).

Preuve. Par récurrence sur \(a + b\). Cas de base : \(a + b = 2\). Alors \(a = b = 1\), \(g(1, 1) = (0, 1)\) et \(f(1, 1) = 0\) : le lemme est vrai.

Supposons \(a + b > 2\) ; alors \(a \neq b\), puisque \(a\) et \(b\) sont premiers entre eux. Deux cas sont possibles.

Cas 1 : \(a > b\). On a \(g(a - b, b) = (u, v + u)\), puisque \(u(a - b) + (v + u)b = 1\) et \(u \in (-b/2, b/2]\). Donc \(f(a, b) = 1 \iff f(a - b, b) = 1 \iff u > 0\) par hypothèse de récurrence.

Cas 2 : \(a < b\) (et alors, clairement, \(b \geq 2\)). Estimons \(v\). Comme \(vb = 1 - ua\), on a

\[1 + \frac{ab}{2} > vb \geq 1 - \frac{ab}{2}, \qquad \text{donc} \qquad \frac{1 + a}{2} \geq \frac{1}{b} + \frac{a}{2} > v \geq \frac{1}{b} - \frac{a}{2} > -\frac{a}{2}.\]

Ainsi \(1 + a > 2v > -a\), donc \(a \geq 2v > -a\), d'où \(a/2 \geq v > -a/2\), et donc \(g(b, a) = (v, u)\).

Or \(f(a, b) = 1 \iff f(b, a) = 0 \iff f(b - a, a) = 0\). D'après le cas 1, \(g(b - a, a) = (v, u + v)\), et par hypothèse de récurrence \(f(b - a, a) = 0 \iff v \leq 0\). Enfin, comme \(b > a \geq 1\) et \(ua + vb = 1\), on a \(v \leq 0 \iff u > 0\), ce qui conclut. \(\square\)

Conclusion. Le lemme montre que, pour tout \((a, b) \in \mathbb{A}\), \(f(a, b) = 1\) si et seulement si l'inverse de \(a\) modulo \(b\), pris dans \(\{1, 2, \ldots, b-1\}\), est au plus \(b/2\). Ainsi, pour \(p\) premier impair et \(n \not\equiv 0 \pmod p\), \(f(n^2, p) = 1\) si et seulement si l'inverse de \(n^2\) modulo \(p\) est inférieur à \(p/2\). Comme

\[\{n^2 \bmod p : 1 \leq n \leq p-1\} = \{n^{-2} \bmod p : 1 \leq n \leq p-1\}\]

en comptant les multiplicités (deux pour chaque résidu quadratique, dans chaque ensemble), la somme cherchée vaut deux fois le nombre de résidus quadratiques inférieurs à \(p/2\) :

\[\sum_{n=1}^{p-1} f(n^2, p) = 2\left|\left\{k : 1 \leq k \leq \frac{p-1}{2} \text{ et } k^2 \bmod p < \frac{p}{2}\right\}\right|. \tag{1}\]

Le nombre de carrés parfaits dans l'intervalle \([1, p/2)\) est \(\left\lfloor \sqrt{p/2} \right\rfloor > \sqrt{p/2} - 1\) (partie entière) ; on en conclut

\[\sum_{n=1}^{p-1} f(n^2, p) > 2\left(\sqrt{\frac{p}{2}} - 1\right) = \sqrt{2p} - 2. \qquad \blacksquare\]

Solution 2

On donne une autre preuve du lemme, en calculant explicitement \(g(a, b) = (u, v)\) à l'aide des fractions continues. La fonction \(f\) est entièrement déterminée sur \(\mathbb{A}\) par l'affirmation suivante.

Affirmation. Écrivons \(a/b\) en fraction continue : soient \(a_0\) un entier et \(a_1, \ldots, a_k\) des entiers strictement positifs, avec \(a_k \geq 2\) (précision ajoutée : si \(k \geq 1\)), tels que

\[\frac{a}{b} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_k}}}} = [a_0; a_1, a_2, \ldots, a_k].\]

Alors \(f(a, b) = 0 \iff k\) est pair.

Preuve. Par récurrence sur \(b\). Si \(b = 1\), alors \(a/b = [a]\) et \(k = 0\) ; pour \(a \geq 1\), une récurrence immédiate montre que \(f(a, 1) = f(1, 1) = 0\).

Soit maintenant \(b > 1\). Effectuons la division euclidienne \(a = qb + r\), \(0 \leq r < b\) ; on a \(r \neq 0\) car \(\operatorname{pgcd}(a, b) = 1\). Donc

\[f(a, b) = f(r, b) = 1 - f(b, r), \qquad \frac{a}{b} = [q; a_1, \ldots, a_k], \qquad \frac{b}{r} = [a_1; a_2, \ldots, a_k].\]

Les nombres de termes des fractions continues de \(a/b\) et de \(b/r\) diffèrent de un. Comme \(r < b\), l'hypothèse de récurrence donne \(f(b, r) = 0 \iff k - 1\) est pair, donc

\[f(a, b) = 0 \iff f(b, r) = 1 \iff k - 1 \text{ est impair} \iff k \text{ est pair}. \qquad \square\]

On utilise maintenant des propriétés classiques des fractions continues. Soient \(p_i\) et \(q_i\) des entiers strictement positifs premiers entre eux tels que \([a_0; a_1, \ldots, a_i] = p_i / q_i\) (avec les notations de l'affirmation) ; en particulier \(a/b = [a_0; a_1, \ldots, a_k] = p_k / q_k\). Supposons \(k > 0\) et posons \(q_{-1} = 0\) si nécessaire. Alors

  • \(q_k = a_k q_{k-1} + q_{k-2}\) ;
  • \(a q_{k-1} - b p_{k-1} = p_k q_{k-1} - q_k p_{k-1} = (-1)^{k-1}\).

Pour \(k > 0\), on a \(a_k \geq 2\), donc

\[b = q_k = a_k q_{k-1} + q_{k-2} \geq a_k q_{k-1} \geq 2q_{k-1} \implies q_{k-1} \leq \frac{b}{2},\]

avec inégalité stricte pour \(k > 1\), et

\[(-1)^{k-1} q_{k-1}\, a + (-1)^k p_{k-1}\, b = 1.\]

Terminons la preuve du lemme. Il est immédiat pour \(k = 0\). Si \(k = 1\), alors \((-1)^{k-1} = 1\), donc \(-b/2 < 0 \leq (-1)^{k-1} q_{k-1} \leq b/2\). Si \(k > 1\), on a \(q_{k-1} < b/2\), donc \(-b/2 < (-1)^{k-1} q_{k-1} < b/2\). Ainsi, pour tout \(k > 0\), \(g(a, b) = \left((-1)^{k-1} q_{k-1}, (-1)^k p_{k-1}\right)\), et donc

\[f(a, b) = 1 \iff k \text{ est impair} \iff u = (-1)^{k-1} q_{k-1} > 0.\]

On conclut ensuite comme dans la solution 1. \(\blacksquare\)

Remarques

Remarque 1. On peut aussi établir le lemme en observant que \(f\) est déterminée de façon unique sur \(\mathbb{A}\) : on définit \(f_1(a, b) = 1\) si \(u > 0\) dans \(g(a, b) = (u, v)\) et \(f_1(a, b) = 0\) sinon, et on vérifie que \(f_1\) satisfait toutes les conditions de l'énoncé. La principale difficulté du problème semble être de conjecturer le lemme.

Remarque 2 (le cas \(p \equiv 1 \pmod 4\) est plus facile). En général, pour \(1 \leq a \leq p - 1\),

\[f(a, p) = 1 - f(p, a) = 1 - f(p - a, a) = f(a, p - a) = f(a + (p - a), p - a) = f(p, p - a) = 1 - f(p - a, p).\]

Si \(p \equiv 1 \pmod 4\), \(a\) est un résidu quadratique modulo \(p\) si et seulement si \(p - a\) en est un. En notant \(r_k\) (\(1 \leq r_k \leq p - 1\)) le reste de la division de \(k^2\) par \(p\), on obtient

\[\sum_{n=1}^{p-1} f(n^2, p) = \sum_{n=1}^{p-1} f(r_n, p) = \frac{1}{2} \sum_{n=1}^{p-1} \left(f(r_n, p) + f(p - r_n, p)\right) = \frac{p-1}{2}.\]

Remarque 3 (une borne en \((p-1)/16\)). En affinant la fin de la solution 1, on peut montrer que

\[\sum_{n=1}^{p-1} f(n^2, p) \geq \frac{p-1}{16}.\]

En comptant les carrés parfaits dans les intervalles \([kp, (k + \frac12)p)\), on trouve

\[\sum_{n=1}^{p-1} f(n^2, p) = \sum_{k=0}^{p-1} \left(\left\lfloor \sqrt{\left(k + \tfrac{1}{2}\right)p} \right\rfloor - \left\lfloor \sqrt{kp} \right\rfloor\right). \tag{2}\]

Chaque terme de (2) est positif ou nul. Si un terme est nul, c'est-à-dire si \(\left\lfloor \sqrt{(k + \frac12)p} \right\rfloor = \left\lfloor \sqrt{kp} \right\rfloor =: q\), alors \(kp\) et \(kp + p/2\) sont tous deux dans \([q^2, (q+1)^2)\), donc \(\frac{p}{2} < (q+1)^2 - q^2\), d'où \(q \geq \frac{p-1}{4}\). Comme \(q \leq \sqrt{kp}\), si le \(k\)-ième terme est nul, alors

\[k \geq \frac{q^2}{p} \geq \frac{(p-1)^2}{16p} > \frac{p-2}{16} \implies k \geq \frac{p-1}{16}.\]

Donc au moins les \(\left\lceil \frac{p-1}{16} \right\rceil\) premiers termes (de \(k = 0\) à \(k = \left\lceil \frac{p-1}{16} \right\rceil - 1\)) sont strictement positifs, d'où le résultat.

Remarque 4 (une borne en \((p-3)/4\) avec le symbole de Legendre). On peut encore améliorer la borne :

\[\sum_{n=1}^{p-1} f(n^2, p) \geq \frac{p-3}{4}.\]

On utilise le symbole de Legendre : \(\left(\frac{a}{p}\right) = 0\) si \(p \mid a\), \(1\) si \(a\) est un résidu quadratique non nul modulo \(p\), et \(-1\) sinon. L'affirmation suivante dit qu'il n'y a pas trop de résidus (ou de non-résidus) consécutifs :

\[\sum_{n=1}^{p-1} \left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right) = -1.\]

Preuve. \(\left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right) = \left(\frac{n(n+1)}{p}\right)\), et \(n(n+1) \equiv n^2(1 + n^{-1}) \pmod p\), donc ce symbole vaut \(\left(\frac{1 + n^{-1}}{p}\right)\). Comme \(\{1 + n^{-1} \bmod p : 1 \leq n \leq p-1\} = \{0, 2, 3, \ldots, p-1\}\) modulo \(p\), la somme vaut \(\sum_{n=1}^{p-1} \left(\frac{n}{p}\right) - 1 = -1\), car \(\sum_{n=1}^{p} \left(\frac{n}{p}\right) = 0\).

D'après (1), \(\sum_{n=1}^{p-1} f(n^2, p) = 2|S|\) avec \(S = \left\{r : 1 \leq r \leq \frac{p-1}{2},\ \left(\frac{r}{p}\right) = 1\right\}\). Soient de même \(S'\) (les \(r \leq \frac{p-1}{2}\) non-résidus), \(T\) (les \(r \geq \frac{p+1}{2}\) résidus) et \(T'\) (les \(r \geq \frac{p+1}{2}\) non-résidus), avec \(r \leq p - 1\). Comme il y a exactement \(\frac{p-1}{2}\) résidus non nuls, \(|S| + |T| = \frac{p-1}{2}\) ; de plus \(|T| + |T'| = \frac{p-1}{2}\), donc \(|S| = |T'| =: t\).

Si \(\left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right) = -1\), exactement l'un de \(n\) et \(n + 1\) est un résidu, donc \(n \in S \cup (S - 1)\) pour \(1 \leq n \leq \frac{p-3}{2}\) : il y a au plus \(|S| + |S - 1| = 2t\) tels \(n\). De même, exactement l'un des deux est un non-résidu, et pour \(\frac{p+1}{2} \leq n \leq p - 2\) il y a au plus \(|T'| + |T' - 1| = 2t\) tels \(n\). En tenant compte du terme du milieu (\(n = \frac{p-1}{2}\)), qui peut valoir \(-1\), le nombre de \(n \in [1, p-2]\) avec un produit égal à \(-1\) est au plus \(4t + 1\), donc le nombre de \(n\) avec un produit égal à \(1\) est au moins \((p - 2) - (4t + 1) = p - 4t - 3\). Ainsi (précision ajoutée : le terme \(n = p - 1\) est nul)

\[-1 = \sum_{n=1}^{p-1} \left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right) \geq p - 4t - 3 - (4t + 1) = p - 8t - 4,\]

d'où \(8t \geq p - 3\) et

\[\sum_{n=1}^{p-1} f(n^2, p) = 2t \geq \frac{p-3}{4}.\]

Remarque 5 (la borne optimale \((p-1)/2\)). On peut même montrer que

\[\sum_{n=1}^{p-1} f(n^2, p) \geq \frac{p-1}{2}.\]

Le cas \(p \equiv 1 \pmod 4\) est celui d'égalité (remarque 2). Si \(p \equiv 3 \pmod 4\), une formule de Dirichlet (liée au nombre de classes) montre que les résidus quadratiques non nuls sont strictement plus nombreux dans \(\left[1, \frac{p-1}{2}\right]\) que dans \(\left[\frac{p+1}{2}, p-1\right]\), c'est-à-dire \(|S| > \frac{p-1}{4}\), d'où le résultat par (1). On ne connaît pas de preuve élémentaire de ce théorème ; une preuve par l'analyse complexe figure par exemple au chapitre 7 de Quadratic Residues and Non-Residues: Selected Topics de Steve Wright (arXiv:1408.0235).

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2024 A6 ★★★★☆ : Chaque terme est la moyenne arithmétique ou géométrique de ses voisins : le choix entre les deux finit par être périodique.
  • 2021 N6 ★★★★☆ : Pour quels \(n\) peut-on toujours ordonner \(n\) entiers distincts pour que \(\sum k a_k\) soit divisible par \(n\) ?
  • 2025 N8 ★★★★★ : Seul un nombre fini de premiers \(p\) ont \(p - 8\) carré et tous les \(p - k^2\) (\(k\) impair, \(k < \sqrt{p}\)) avec au plus deux facteurs premiers.
  • 2015 N8 ★★★★★ : Trouver les fonctions croissantes de \(\mathbb{Z}\) qui ne font pas augmenter le nombre de très grands facteurs premiers des différences.