Résidus quadratiques¶
Domaine : Théorie des nombres · Niveau : avancé · Prérequis : Congruences, Fermat et Euler, Ordre d'un élément
L'idée¶
Soit \(p\) un nombre premier impair. Un entier \(a\) non divisible par \(p\) est un résidu quadratique modulo \(p\) si l'équation \(x^2 \equiv a \pmod p\) a une solution, autrement dit si \(a\) est « un carré modulo \(p\) ». Par exemple, modulo \(7\), les carrés non nuls sont \(1, 2, 4\) : \(3\), \(5\) et \(6\) ne sont pas des carrés.
Exactement la moitié des restes non nuls, soit \(\frac{p-1}{2}\), sont des résidus quadratiques : \(x\) et \(-x\) ont le même carré, et ce sont les seules paires.
On note \(\left(\frac{a}{p}\right)\) le symbole de Legendre : il vaut \(1\) si \(a\) est un résidu quadratique modulo \(p\), \(-1\) sinon (et \(0\) si \(p \mid a\)).
Les outils¶
| Résultat | Énoncé |
|---|---|
| Critère d'Euler | \(\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p\) |
| Multiplicativité | \(\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\) : le produit de deux non-résidus est un résidu |
| \(-1\) | \(-1\) est un carré modulo \(p\) si et seulement si \(p \equiv 1 \pmod 4\) |
| \(2\) | \(2\) est un carré modulo \(p\) si et seulement si \(p \equiv \pm 1 \pmod 8\) |
| Réciprocité quadratique | Pour \(p \neq q\) premiers impairs, \(\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}\) |
La réciprocité dit : \(\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)\), sauf si \(p\) et \(q\) sont tous les deux \(\equiv 3 \pmod 4\), auquel cas les deux symboles sont opposés.
Sommes de deux carrés¶
Le fait sur \(-1\) a une conséquence très utilisée : si un premier \(p \equiv 3 \pmod 4\) divise \(a^2 + b^2\), alors \(p\) divise \(a\) et \(b\). En effet, si \(p \mid b\), alors \(p \mid a^2\), donc \(p \mid a\). Sinon, \(b\) a un inverse \(b^{-1}\) modulo \(p\), et \((a b^{-1})^2 \equiv -1 \pmod p\) ferait de \(-1\) un carré modulo \(p\).
À l'inverse, tout premier \(p \equiv 1 \pmod 4\) est une somme de deux carrés (Fermat), et un entier \(n \geq 1\) est une somme de deux carrés si et seulement si chaque premier \(\equiv 3 \pmod 4\) apparaît avec un exposant pair dans sa décomposition.
Exemple résolu¶
Problème
Montrer qu'il existe une infinité de nombres premiers congrus à \(1\) modulo \(4\).
Étape 1 : les diviseurs premiers de \(x^2 + 1\). Soit \(q\) un premier impair qui divise \(x^2 + 1\). Alors \(x^2 \equiv -1 \pmod q\), et \(q \nmid x\). En élevant à la puissance \(\frac{q-1}{2}\) :
Par le petit théorème de Fermat, le membre de gauche vaut \(1\). Comme \(1 \not\equiv -1\) modulo \(q\) impair, \(\frac{q-1}{2}\) est pair : \(q \equiv 1 \pmod 4\).
Étape 2 : l'argument d'Euclide. Supposons qu'il n'y ait qu'un nombre fini de tels premiers \(p_1, \ldots, p_k\), et posons
\(N\) est impair et \(> 1\), donc il a un diviseur premier impair \(q\). Par l'étape 1, \(q \equiv 1 \pmod 4\), donc \(q\) est l'un des \(p_i\). Mais alors \(q\) divise \(N - (2p_1 \cdots p_k)^2 = 1\), ce qui est absurde.
Le même schéma fonctionne pour d'autres progressions : les diviseurs premiers de \(x^2 - 2\), de \(x^2 + 3\), etc. sont contraints par un symbole de Legendre. C'est une manière élémentaire d'obtenir des cas particuliers du théorème de Dirichlet.
Comment le reconnaître¶
- Une expression \(x^2 + 1\), \(x^2 + y^2\), \(x^2 - 2\), ou plus généralement \(x^2 - a\), et une question sur ses diviseurs premiers.
- On doit montrer qu'un nombre n'est pas un carré modulo \(p\), ou qu'une équation \(x^2 \equiv a\) n'a pas de solution.
- Une question sur les sommes de deux carrés.
- On veut une infinité de premiers d'une certaine forme.
- On compte les carrés modulo \(p\), ou l'on manipule un produit qui doit être (ou ne pas être) un carré.
Techniques classiques¶
| Situation | Technique |
|---|---|
| \(p\) premier divise \(x^2 + 1\) | \(p = 2\) ou \(p \equiv 1 \pmod 4\) |
| \(p \equiv 3 \pmod 4\) divise \(a^2 + b^2\) | \(p\) divise \(a\) et \(b\) ; souvent suivi d'une descente infinie |
| Savoir si \(a\) est un carré modulo \(p\) | Critère d'Euler, ou décomposer \(a\) et utiliser multiplicativité et réciprocité |
| Un produit doit être un carré modulo \(p\) | Faire apparaître un non-résidu : le produit d'un résidu et d'un non-résidu n'est pas un carré |
| Infinité de premiers d'une forme donnée | Argument d'Euclide avec un polynôme du second degré bien choisi |
| Sommes de deux carrés | Premiers \(\equiv 1 \pmod 4\) ; exposants pairs pour les premiers \(\equiv 3 \pmod 4\) |
Exercices d'échauffement¶
- Lister les résidus quadratiques modulo \(11\).
- Montrer que \(x^2 \equiv -1 \pmod 7\) n'a pas de solution, et que \(2\) est un carré modulo \(7\).
- Montrer que l'équation \(x^2 + y^2 = 3z^2\) n'a pas d'autre solution entière que \((0, 0, 0)\). Indication : \(3\) divise \(x^2 + y^2\).
- Pour quels nombres premiers \(p > 3\) le nombre \(3\) est-il un carré modulo \(p\) ? Indication : réciprocité quadratique.
- Écrire \(13\) et \(29\) comme sommes de deux carrés, et montrer que \(21\) n'en est pas une.
Résidus quadratiques dans la shortlist¶
- 2020 N2, solution 2 : si \(3\) n'est pas un résidu quadratique modulo \(p\), une paire d'îles est isolée du reste.
- 2024 N6 : avec \(r\) non-résidu, \(a(X^2 - r)\) ne s'annule jamais modulo \(p\).
- 2017 N8 : la somme étudiée vaut deux fois le nombre de résidus quadratiques non nuls inférieurs à \(\frac{p}{2}\).
- 2022 N8, solution 2 : par réciprocité quadratique, \(\left(\frac{5}{m}\right) = -1\) alors que \(\left(\frac{3}{m}\right) = 1\).
- 2025 N8 : on trouve un petit premier modulo lequel \(2\) est un carré.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 5 (M. Aassila), p. 294 (résidus quadratiques, symbole de Legendre, lemme de Gauss), p. 295 (critère d'Euler et loi de réciprocité quadratique), p. 296 à 302 (exemples), p. 255 à 258 (premiers de la forme \(4k + 3\) et \(3k + 2\)), p. 259 à 261 (sommes de deux carrés, théorème de Fermat et lemme de Thue p. 260), p. 393 (diviseurs premiers de \(a^2 + 1\)).
Problèmes de la shortlist¶
11 problèmes · difficulté moyenne : ★★★★★ (4,0) · dont 1 choisi pour l'OIM
Répartition par difficulté : 1 ★ : 1 · 2 ★ : 1 · 3 ★ : 1 · 4 ★ : 2 · 5 ★ : 6
| Problème | Difficulté | Concepts |
|---|---|---|
| 2020 N2 | ★☆☆☆☆ | Graphes : degrés, chemins, arbres · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2007 N2 | ★★☆☆☆ | Valuations p-adiques et lemme LTE |
| 2008 N6 · OIM P3 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2024 N6 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Principe des tiroirs · Double comptage |
| 2012 N6 | ★★★★☆ | Ordre d'un élément et racines primitives · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Théorème des restes chinois |
| 2025 N8 | ★★★★★ | Équations diophantiennes : factorisation et encadrement · Congruences, théorèmes de Fermat et d'Euler · Divisibilité, PGCD et algorithme d'Euclide |
| 2022 N8 | ★★★★★ | Principe extrémal · Principe des tiroirs · Congruences, théorèmes de Fermat et d'Euler |
| 2017 N8 | ★★★★★ | Divisibilité, PGCD et algorithme d'Euclide · Partie entière et majorations |
| 2012 N8 | ★★★★★ | Double comptage · Ordre d'un élément et racines primitives · Cauchy-Schwarz et lemme de Titu |
| 2011 N8 | ★★★★★ | Ordre d'un élément et racines primitives · Graphes : degrés, chemins, arbres |
| 2009 N7 | ★★★★★ | Suites et récurrences · Valuations p-adiques et lemme LTE |