Théorie > Théorie des nombres > Racines primitives et résidus quadratiques

Résidus quadratiques

Définition
Étant donné un nombre premier impair $p$, on dit qu'un entier $a$ non divisible par $p$ est un résidu quadratique modulo $p$ s'il existe $x \in \mathbb{Z}$ tel que $x^2 \equiv a \pmod p$. Dans le cas contraire, on dit que $a$ est un non-résidu quadratique modulo $p$.

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.