Prérequis
Résumé
On dit d'un nombre $a \in \{1, \ldots, p-1\}$ qu'il est résidu quadratique modulo $p$ s'il existe un carré parfait congru à $a$ modulo $p$. Dans ce chapitre, nous donnons une façon de déterminer si un nombre est résidu quadratique modulo $p$ ou non à l'aide du symbole de Legendre. La notion de racine primitive modulo $p$ est également introduite.
Ce chapitre a été
écrit par N. Radu et
mis en ligne le 4 janvier 2015.
1. Racines primitives
Nous avons vu grâce au théorème d'Euler-Fermat que pour tout naturel $n \geq 2$ et tout entier $a$ premier avec $n$, l'ordre multiplicatif de $a$ modulo $n$ divise $\varphi(n)$. Une question que l'on peut se poser est la suivante : étant donné un nombre $n$ fixé, existe-t-il un entier $a$ premier avec $n$ dont l'ordre multiplicatif modulo $n$ soit
égal à $\varphi(n)$ ?
Dans le cas où $n$ est premier, il existe bel et bien des racines primitives modulo $n$, et on connaît même leur nombre exact (où on ne distingue pas deux racines primitives égales modulo $n$). Il s'agit de la proposition suivante. Sa démonstration est abordable mais dépasse légèrement le cadre de ce cours ; nous ne la donnons donc pas.
Proposition
Soit $p$ un nombre premier. Il existe exactement $\varphi(p-1)$ racines primitives modulo $p$.
Par exemple, pour $p = 11$, on a $p-1 = 10$ et $\varphi(p-1) = \varphi(10) = 4$. Le résultat nous apprend donc qu'il doit y avoir exactement $4$ racines primitives modulo $11$. En effectuant le calcul on remarque facilement qu'il s'agit des nombres $2$, $6$, $7$ et $8$.
L'intérêt d'avoir une racine primitive $g$ modulo $p$ est que les puissances successives $1, g, g^2, \ldots, g^{p-2}$ modulo $p$ parcourent alors tous les nombres entre $1$ et $p-1$. Cela découle des propriétés de l'ordre multiplicatif données dans un précédent chapitre.
2. Résidus quadratiques
Puisqu'on travaille modulo $p$ et qu'on exclut les nombres divisibles par $p$, on étudie en fait essentiellement les nombres entre $1$ et $p-1$. On ne distinguera plus dans la suite deux nombres égaux modulo $p$.
Le premier résultat suivant nous indique qu'il existe autant de résidus quadratiques que de non-résidus quadratiques modulo $p$ fixé et donne une certaine caractérisation de ceux-ci. Rappelons que par le théorème de Fermat, si $a$ n'est pas divisible par $p$ alors $a^{p-1} \equiv 1 \pmod p$. On a donc
$$(a^{\frac{p-1}{2}}-1) (a^{\frac{p-1}{2}}+1) \equiv 0 \pmod p$$ ce qui signifie que $a^{\frac{p-1}{2}} \equiv \pm 1 \pmod p$ (on utilise ici que $p$ est premier, cette affirmation n'est pas vraie lorsque $p$ est composé).
Proposition
Soit $p$ un nombre premier impair. Il existe exactement $\frac{p-1}{2}$ résidus quadratiques modulo $p$ et $\frac{p-1}{2}$ non-résidus quadratiques modulo $p$. Pour un entier $a$ non divisible par $p$, on a par ailleurs
$$a^\frac{p-1}{2} \equiv \begin{cases}
1 & \pmod p \quad\text{ si $a$ est un résidu quadratique modulo $p$,}\\
-1 & \pmod p \quad\text{ si $a$ est un non-résidu quadratique modulo $p$.}
\end{cases}$$
Démonstration
Considérons $g$ une racine primitive modulo $p$. Les puissances successives $1, g, g^2, \ldots, g^{p-2}$ prennent donc toutes les valeurs entre $1$ et $p-1$. Clairement, les nombres $1, g^2, g^4, \ldots, g^{p-3}$ sont des résidus quadratiques modulo $p$ (et sont au nombre de $\frac{p-1}{2}$). Montrons à présent que les puissances impaires $g, g^3, g^5, \ldots, g^{p-2}$ sont des non-résidus quadratiques. Supposons par l'absurde que $g^{2m+1} \equiv x^2 \pmod p$ pour certains $m$ et $x$. Comme $g$ est une racine primitive modulo $p$, on peut écrire $x$ comme $g^\ell$. On a alors $g^{2m+1} \equiv x^2 \equiv g^{2\ell} \pmod p$ d'où $g^{2m+1-2\ell} \equiv 1 \pmod p$. Vu que $o_p(g) = p-1$, cela implique que $p-1$ divise $2m+1-2\ell$, ce qui est impossible comme $p-1$ est pair alors que $2m+1-2\ell$ est impair.
D'autre part, si $a$ est un résidu quadratique modulo $p$, alors $a \equiv x^2 \pmod p$ pour un certain $x$ et donc $a^\frac{p-1}{2} \equiv x^{p-1} \equiv 1 \pmod p$ par Fermat. Au contraire, si $a$ est un non-résidu quadratique modulo $p$, on a montré que $a \equiv g^{2m+1} \pmod p$ pour un certain $m$ et on a donc
$$a^\frac{p-1}{2} \equiv g^{(2m+1)\frac{p-1}{2}} \equiv g^{m(p-1)+\frac{p-1}{2}} \equiv g^\frac{p-1}{2} \pmod p.$$ Puisque $o_p(g) = p-1$, on a $g^\frac{p-1}{2} \not \equiv 1 \pmod p$ et donc $g^\frac{p-1}{2} \equiv -1 \pmod p$ puisqu'on peut seulement obtenir $-1$ ou $1$ comme expliqué plus haut.
3. Symbole de Legendre
Le symbole de Legendre est défini comme suit.
Le symbole de Legendre $\left(\frac{a}{p}\right)$ indique donc si $a$ est un résidu quadratique modulo $p$ ou non, et nous consacrons la suite de ce chapitre à trouver comment calculer la valeur de ce symbole en un temps raisonnable. Premièrement, on a bien sûr $\left(\frac{1}{p}\right) = 1$ pour tout $p$ puisque $1 = 1^2$. Au vu du résultat précédent, on sait aussi que
$$\left(\frac{a}{p}\right) = (a^\frac{p-1}{2} \bmod p).$$ Cette formule n'est cependant pas efficace du tout puisqu'élever un nombre à la puissance $\frac{p-1}{2}$ est presque aussi lent que tester toutes les racines carrées possibles pour $a$. On peut cependant en déduire le résultat suivant.
Lemme
Soit $p$ un nombre premier impair et $a$, $b$ des entiers non divisibles par $p$. On a
$$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right).$$
Démonstration
Cela découle directement de $(ab)^\frac{p-1}{2} = a^\frac{p-1}{2} \cdot b^\frac{p-1}{2}$.
Il est aussi possible de savoir facilement en fonction de $p$ si $-1$ est un carré modulo $p$ ou non.
Lemme
Soit $p$ un nombre premier impair. On a
$$\left(\frac{-1}{p}\right) = \begin{cases}
1 & \text{si }\ p \equiv 1 \pmod 4 \\
-1 &\text{si }\ p \equiv 3 \pmod 4
\end{cases}$$
Démonstration
Cela découle simplement du fait que si $p \equiv 1 \pmod 4$ alors $(-1)^\frac{p-1}{2} = 1$, et si $p \equiv 3 \pmod 4$ alors $(-1)^\frac{p-1}{2} = -1$.
Il existe aussi une formule du même type pour savoir si $2$ est un résidu quadratique modulo $p$ ou non. Celle-ci est cependant plus complexe à prouver et nous n'en donnons dès lors que l'énoncé.
Proposition
Soit $p$ un nombre premier impair. On a
$$\left(\frac{2}{p}\right) = \begin{cases}
1 & \text{si }\ p \equiv \pm 1 \pmod 8 \\
-1 &\text{si }\ p \equiv \pm 3 \pmod 8
\end{cases}$$
Par exemple :
- $2$ est un résidu quadratique modulo $7$ puisque $3^2 \equiv 9 \equiv 2 \pmod 7$. Le résultat précédent l'avait prédit puisque $7 \equiv -1 \pmod 8$.
- $2$ est un non-résidu quadratique modulo $5$ puisque les deux résidus quadratiques sont $1 \equiv 1^2 \equiv 4^2 \pmod 5$ et $4 \equiv 2^2 \equiv 3^2 \pmod 5$. Le résultat nous le disait également puisque $5 \equiv -3 \pmod 8$.
Pour un $a$ général, il n'existe pas de formule explicite pour calculer $\left(\frac{a}{p}\right)$ en fonction de $p$. C'est la
loi de réciprocité quadratique qui va nous permettre de tout de même calculer ce symbole.
4. Loi de réciprocité quadratique
La loi de réciprocité quadratique s'énonce comme suit. Elle fut conjecturée par Euler et Legendre et prouvée par Gauss.
Loi de réciprocité quadratique
Pour tous nombres premiers impairs $p$ et $q$ avec $p \neq q$, on a
$$\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}.$$
Nous n'en donnons pas la démonstration.
L'intérêt de cette formule est qu'elle permet de calculer plus facilement tout symbole de Legendre $\left(\frac{a}{p}\right)$. En effet, elle permet de remplacer un symbole $\left(\frac{p}{q}\right)$ par $\left(\frac{q}{p}\right)$, tout en faisant attention à rajouter le signe $(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$. Autrement dit, il faut simplement rajouter un signe $-$ si $p$ et $q$ sont tous les deux égaux à $3$ modulo $4$.
À titre d'exemple, examinons le problème suivant :
Solution
On remarque tout de suite que l'existence d'une solution est équivalente à dire que $78$ est un résidu quadratique modulo $103$. Il s'agit donc dans un premier temps de voir si cela est vrai pour déterminer si une solution existe. On doit dès lors calculer le symbole $\left(\frac{78}{103}\right)$. Avant de pouvoir utiliser la loi de réciprocité quadratique, il faut que le numérateur soit premier. On commence donc par décomposer $78$ en facteurs premiers en utilisant la formule $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)$ précédemment mentionnée :
$$\left(\frac{78}{103}\right) = \left(\frac{2}{103}\right)\left(\frac{3}{103}\right) \left(\frac{13}{103}\right).$$ On sait déjà que $\left(\frac{2}{103}\right) = 1$ car $103 \equiv -1 \pmod 8$ (voir formule dans le cas $a = 2$). On peut à présent utiliser la loi de réciprocité quadratique pour chacun des deux termes. Vu que $3$ et $103$ sont tous les deux égaux à $3$ modulo $4$, inverser ce symbole va faire apparaître un signe $-$. Par contre, $13$ est égal à $1$ modulo $4$ donc ce symbole n'apportera pas de signe $-$. On a ainsi
$$\left(\frac{78}{103}\right) = - \left(\frac{103}{3}\right) \left(\frac{103}{13}\right) = -\left(\frac{1}{3}\right) \left(\frac{12}{13}\right),$$ où on peut remplacer $103$ par sa valeur modulo $3$ dans le premier symbole et par sa valeur modulo $13$ dans le deuxième, comme la valeur d'un symbole ne dépend que de la valeur du numérateur modulo le dénominateur. On a clairement $\left(\frac{1}{3}\right) = 1$, et donc
$$\left(\frac{78}{103}\right) = - \left(\frac{12}{13}\right) = - \left(\frac{-1}{13}\right).$$ Puisque $13 \equiv 1 \pmod 4$, on a $\left(\frac{-1}{13}\right) = 1$ et on a donc prouvé que
$$\left(\frac{78}{103}\right) = -1,$$ ce qui signifie que $78$ est un non-résidu quadratique modulo $103$ et qu'il n'y a aucun couple $(x,y)$ satisfaisant l'énoncé.
Il est possible grâce à cette loi et à la valeur de $\left(\frac{2}{p}\right)$ suivant $p$ de calculer tous les symboles de Legendre. En effet, à chaque fois que l'on est en présence d'un symbole $\left(\frac{a}{p}\right)$, on peut décomposer $a$ en ses facteurs premiers, trouver la valeur des symboles apparaissant avec un numérateur égal à $2$, et retourner les autres symboles en utilisant la loi de réciprocité quadratique. En remplaçant le numérateur obtenu par sa valeur modulo le dénominateur et en répétant l'opération, les nombres en jeu deviennent de plus en plus petits et on finit par pouvoir tout calculer.