La détermination algorithmique du symbole de Legendre (a|p) pour un entier a modulo un nombre premier impair p, donnant 1 si a est un résidu quadratique modulo p (avec a ≠ 0 mod p), −1 si a est un non‑résidu, et 0 si a ≡ 0 mod p.

Principe

S’appuyer sur la multiplicativité et le critère d’Euler : (a|p) ≡ a^{(p−1)/2} (mod p), puis utiliser la réciprocité quadratique et la réduction modulo p pour ramener l’évaluation à des résidus plus petits et des cas connus.

Démonstration

Exemple : p = 7, a = 3. Calculer 3^{(7−1)/2}=3^3=27≡6≡−1 (mod 7), donc (3|7)=−1 ; 3 est un non‑résidu quadratique modulo 7.

Mauvaise application

Appliquer la formule du symbole de Legendre à des modules composites (prendre la valeur du symbole de Jacobi pour une décision), ou présumer que (a|p)=1 donne directement une racine carrée sans vérifier p ou les inverses multiplicatifs.

Conséquence

Une évaluation correcte détermine la solvabilité de x^2≡a (mod p), facilite la résolution des congruences quadratiques et alimente les calculs de réciprocité et les sommes de caractères en théorie des nombres algébrique et analytique.

Inversion

Remplacer le symbole de Legendre par le symbole de Jacobi (mod un composé) inverse la décision : une valeur de Jacobi égale à 1 ne garantit plus la résiduosité quadratique, mettant en évidence la différence entre module premier et composite.

Limite

S’applique uniquement aux entiers a et aux modules premiers impairs p (p>2) ; exclut le module 2 et les modules composites sauf réinterprétation explicite en symbole de Jacobi ; suppose les calculs dans Z/pZ et des représentants canoniques.

Tension sémantique

Tension entre le test algébrique compact (critère d’Euler) et le symbole de Jacobi plus général mais moins déterminant : l’un donne une réponse exacte pour les premiers, l’autre est similaire en coût mais plus faible sémantiquement pour les composés.

Synthèse

L’évaluation du symbole de Legendre est une procédure algorithmo‑algébrique qui, grâce au critère d’Euler, à la multiplicativité et à la réciprocité, ramène la question de la résiduosité quadratique modulo un premier impair à des calculs finis de puissances et de signes, avec portée et limites explicites.