Le symbole de Legendre

On définit $\left(\frac{a}{p}\right)$ pour p premier comme égal à 1 si a est un carré dans ${\mathbb Z}/p{\mathbb Z}$, à -1 sinon. Ce symbole est multiplicatif :

$$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right) \left(\frac{b}{p}\right).$$

Ceci est dû au fait que le produit de deux carrés est un carré, (ceci est toujours vrai dans un groupe cyclique ${\mathbb Z}/n{\mathbb Z}$) et que, si nous sommes dans ${\mathbb Z}/p{\mathbb Z}$, p premier, alors le produit d'un carré par un non carré est un non carré et le produit de deux non carrés est un carré.

On peut aussi énoncer le fait suivant :
g est un générateur du groupe cyclique ${\mathbb G}\Longrightarrow g$ est un non carré. La réciproque est vraie si $\char93 {\mathbb G}-1=2^k$.

La loi de réciprocité pour le symbole de Legendre affirme

$$\left(\frac{p}{q}\right)=(-1)^\frac{(p-1)(q-1)}{4} \left(\frac{q}{p}\right).$$

Ainsi, de même que dans l'algorithme d'Euclide pour le calcul du PGCD ou que dans le test de primalité par descente-remontée (voir §), on est ramené, de proche en proche, à traiter des nombres de plus en plus petits.

L'intérêt d'une stratégie de ``rapetissement progressif du problème'' transparaît dans l'algorithme de calcul du pgcd de (a,b)= :(r,s), dont voici l'algorithme :

DEBUT
tant que $s \not = 0$ faire $(r,s)~:=(s, r \ {\bmod} \ s)$ ;
(* on crunche et squeeze avec allégresse *)
retourner r ;
FIN