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
É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
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
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
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\) :
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
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
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
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
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
avec inégalité stricte pour \(k > 1\), et
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
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\),
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
Remarque 3 (une borne en \((p-1)/16\)). En affinant la fin de la solution 1, on peut montrer que
En comptant les carrés parfaits dans les intervalles \([kp, (k + \frac12)p)\), on trouve
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
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 :
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 :
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)
d'où \(8t \geq p - 3\) et
Remarque 5 (la borne optimale \((p-1)/2\)). On peut même montrer que
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.