symbole de Legendre

Élevons au carré les nombres entiers, puis ne gardons que leur reste dans la division par 11. Les restes non nuls obtenus sont 1, 3, 4, 5 et 9. Le nombre 5 figure dans cette liste, car 4² donne 16, dont le reste modulo 11 est 5.

Le symbole de Legendre résume ce constat par une seule valeur : 1 lorsqu’un reste est atteint par un carré, −1 lorsqu’il ne l’est pas, et 0 lorsque le nombre premier choisi divise l’entier testé.

Soit p un nombre premier et a un entier. Le symbole de Legendre, noté $\left(\frac{a}{p}\right)\backslash left(\backslash frac\{a\}\{p\}\backslash right)$, classe a d’après les carrés modulo p. Il ne dépend que du reste de a dans la division par p.

Sa définition comporte trois cas :Dans le deuxième cas, a est appelé résidu quadratique modulo p. Dans le troisième, a est un non-résidu quadratique modulo p.

Pour p impair et lorsque p ne divise pas a, le symbole peut aussi être calculé avec le critère d’Euler : $a^{(p-1)\mathrm{/}2}\equiv \left(\frac{a}{p}\right)(\mathrm{m}\mathrm{o}\mathrm{d}p)a^\{(p-1)/2\}\; \backslash equiv\; \backslash left(\backslash frac\{a\}\{p\}\backslash right)\; \backslash pmod\; p$. Il est multiplicatif en l’entier du numérateur : le symbole d’un produit est le produit des symboles. Cette propriété et la loi de réciprocité quadratique rendent son calcul efficace.

Calculons le symbole de Legendre de 5 modulo 11. Les données sont l’entier a = 5 et le nombre premier p = 11. Il suffit de déterminer si 5 apparaît parmi les carrés modulo 11.

1. Calculons les carrés des entiers de 1 à 5 ; les entiers de 6 à 10 donnent les mêmes restes par paires opposées.
2. On obtient successivement 1, 4, 9, 5 et 3 modulo 11.
3. Le reste 5 apparaît, puisque $4^2=16\equiv 5(\mathrm{m}\mathrm{o}\mathrm{d}11)4^2=16\backslash equiv5\backslash pmod\{11\}$.
4. Comme 11 ne divise pas 5, la valeur n’est pas 0.

Le résultat est donc $\left(\frac{5}{11}\right)=1\backslash left(\backslash frac\{5\}\{11\}\backslash right)=1$. Un contrôle indépendant consiste à appliquer le critère d’Euler : $5^5=3125\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}11)5^5=3125\backslash equiv1\backslash pmod\{11\}$, ce qui confirme le verdict.

Pour savoir si une congruence comme x² ≡ 5 modulo 11 peut avoir une solution, on calcule d’abord le symbole de Legendre. La valeur 1 garantit ici l’existence de racines ; 4 et 7 conviennent. Une valeur −1 écarterait immédiatement toute solution.

Lorsque le nombre premier est petit, dresser la liste des carrés suffit. Pour un grand nombre premier impair, le critère d’Euler ou les règles de multiplicativité et de réciprocité quadratique évitent cette énumération.

Dans un calcul avec un dénominateur composé, on emploie plutôt le symbole de Jacobi. Son calcul ressemble à celui du symbole de Legendre, mais son interprétation demande davantage de prudence.

Le symbole de Legendre ne doit pas être confondu avec le symbole de Jacobi. Le dénominateur du premier est un nombre premier, tandis que celui du second peut être un entier impair composé. Ainsi, une valeur −1 du symbole de Jacobi exclut un carré, mais une valeur 1 ne suffit pas à en garantir un ; cette ambiguïté n’existe pas pour le symbole de Legendre.

La notation ressemble aussi à une fraction, mais elle ne désigne pas le quotient a/p. Par exemple, $\left(\frac{5}{11}\right)=1\backslash left(\backslash frac\{5\}\{11\}\backslash right)=1$ est un verdict arithmétique, et non le nombre rationnel 5/11.

Si p divise a, le symbole vaut 0 : ce cas ne doit pas être rangé parmi les non-résidus, dont le symbole vaut −1. Le test de divisibilité précède donc toute recherche de carré.

Une valeur 1 affirme qu’une racine carrée existe modulo p, mais elle ne donne pas cette racine. Dans l’exemple modulo 11, le symbole annonce l’existence ; il faut encore trouver les deux restes 4 et 7.

Le symbole de Legendre est usuellement défini pour un nombre premier impair. Avec p = 2, la classification en trois cas se réduit : tout entier impair est un carré modulo 2. Les lois usuelles de réciprocité quadratique se formulent donc pour des nombres premiers impairs.

Enfin, remplacer p par un entier composé change la portée du symbole. Il faut alors factoriser le dénominateur ou utiliser le symbole de Jacobi sans lui attribuer automatiquement le même verdict d’existence.

Le symbole de Jacobi étend le calcul à un dénominateur impair composé et montre pourquoi la valeur 1 demande alors une vérification supplémentaire.

La congruence modulo n précise le langage des restes utilisé dans la définition et dans le calcul des carrés.

L’article Adrien-Marie Legendre, à la recherche de solutions entières replace ces outils dans l’étude historique des équations en nombres entiers.