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)

Pas encore relu

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

Énoncé

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 quatre 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}.\]