Un entier r (ou sa classe modulo n) qui n'est congru à aucun carré modulo n ; autrement dit r n'appartient pas à l'image de l'application x ↦ x^2 sur Z/nZ.

Principe

Les non‑résidus sont définis négativement par l'absence de solution : le principe est la classification des classes selon que la congruence quadratique x^2 ≡ r (mod n) admet ou non une solution, séparant résidus et non‑résidus.

Démonstration

Modulo 7 la classe de 3 est un non‑résidu quadratique car aucun x dans {0,…,6} ne satisfait x^2 ≡ 3 (mod 7) ; par contraste 2 et 4 sont des résidus comme le montrent les carrés explicites.

Mauvaise application

Qualifier un nombre de non‑résidu sans préciser le modulo, ou appliquer directement des heuristiques de répartition valables pour des modules premiers aux modules composés où la distribution est plus subtile.

Conséquence

Identifier des non‑résidus désigne des classes où les congruences quadratiques n'ont pas de solution, éclaire les lois de réciprocité et alimente des primitives cryptographiques fondées sur la difficulté de distinguer résidus et non‑résidus dans certains cadres.

Inversion

Le concept inverse est le résidu quadratique ; inverser la classification change la résolubilité des équations quadratiques et l'appartenance à des sous‑groupes multiplicatifs de (Z/nZ)^×.

Limite

Dépend du modulo n : pour un premier impair p environ la moitié des classes non nulles sont des non‑résidus (selon les conventions de comptage) ; pour n composé les diviseurs de zéro et la décomposition via le lemme chinois modifient existence et comptage.

Tension sémantique

Tension entre la tâche algorithmique « tester si un entier est un non‑résidu » et la classification abstraite ; tension aussi entre heuristiques statistiques et critères algébriques exacts fournis par les symboles de Legendre ou Jacobi.

Synthèse

Un non‑résidu quadratique modulo n est une classe de congruence exclue de l'image du carré ; avec les résidus il partitionne les classes selon la résolubilité de x^2 ≡ r et joue un rôle central dans la réciprocité, les algorithmes et la cryptographie.