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.