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\). Indication : il suffit de calculer \(1^2, 2^2, \ldots, 5^2\) modulo \(11\).
- Montrer que \(x^2 \equiv -1 \pmod 7\) n'a pas de solution, et que \(2\) est un carré modulo \(7\). Indication : les carrés modulo \(7\) sont \(0\), \(1\), \(2\) et \(4\).
- 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. Indication : tester les carrés inférieurs à \(21\), ou remarquer que \(3 \mid 21\) avec \(3 \equiv 3 \pmod 4\).
Parcours suggéré¶
Un choix de problèmes de la shortlist, du plus accessible au plus difficile, où ce concept joue le premier rôle. La liste complète est plus bas.
Étape 1 — Premiers pas (1 ★)
- 2020 N2 ★☆☆☆☆ : Des îles reliées selon une condition de divisibilité modulo \(p\) : pour une infinité de \(p\), le réseau n'est pas connexe.
Étape 2 — Consolidation (2 ★)
- 2007 N2 ★★☆☆☆ : Si \(b\) est une puissance \(n\)-ième modulo tout entier \(k\), alors c'est une vraie puissance \(n\)-ième.
Étape 3 — Approfondissement (3 ★)
- 2008 N6 ★★★☆☆ · OIM P3 : Une infinité d'entiers \(n\) ont \(n^2 + 1\) divisible par un premier plus grand que \(2n + \sqrt{2n}\).
Étape 4 — Défi (4 ★ – 5 ★)
- 2012 N6 ★★★★☆ : Si \(2^n y + 1\) divise \(x^{2^n} - 1\) pour tout \(n\), alors \(x = 1\).
- 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\) ?
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¶
La shortlist compte très peu de problèmes faciles sur ce thème : si le concept est nouveau pour vous, commencez par les exercices d'échauffement ci-dessus.
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 |