La méthode consistant à trouver des entiers x qui satisfont des congruences de la forme a x ≡ b (mod n), avec a, b et n entiers donnés et n strictement positif.

Principe

Une congruence a x ≡ b (mod n) est soluble si et seulement si d = pgcd(a,n) divise b ; si c'est le cas on divise par d pour obtenir une congruence équivalente de module n/d et on utilise les inverses modulaires sur le coefficient réduit.

Démonstration

Exemple : résoudre 14 x ≡ 6 (mod 20). pgcd(14,20)=2 divise 6, on divise par 2 : 7 x ≡ 3 (mod 10). L'inverse de 7 modulo 10 est 3, donc x ≡ 3·3 ≡ 9 (mod 10). En revenant au module 20 on obtient les classes x ≡ 9 et x ≡ 19 (mod 20).

Mauvaise application

Tenter d'inverser a modulo n quand pgcd(a,n) ≠ 1, ou négliger le facteur d, conduit à des affirmations erronées d'unicité ou à la perte de solutions.

Conséquence

Une application correcte donne toutes les classes résiduelles de solutions entières et une congruence réduite dont l'ensemble des solutions est paramétré par le module n/d ; elle transforme un test d'existence en construction explicite utile en algorithmique.

Inversion

Au lieu de résoudre x pour une congruence linéaire unique, on peut inverser le problème (caractériser a ou n à partir de classes résiduelles observées) ou remplacer la question par la résolution de congruences non linéaires (p. ex. quadratiques), qui obéissent à des critères différents.

Limite

S'applique seulement aux congruences linéaires à coefficients entiers et au module n>0 ; exclut les congruences non linéaires, les congruences sur des anneaux non entiers et les solutions dans Q sauf si on les ramène à des congruences entières équivalentes.

Tension sémantique

Souvent confondu avec la résolution d'équations linéaires sur l'anneau Z/nZ en tant qu'objet algébrique ; la tension vient de l'opposition entre la solution algorithmique constructive (classes résiduelles explicites) et les énoncés structurels sur les modules sur Z/nZ.

Synthèse

La résolution de congruences linéaires est un processus constructif : tester la divisibilité par pgcd(a,n), réduire le module, et produire soit des inverses modulaires soit une paramétrisation complète des classes résiduelles satisfaisant a x ≡ b (mod n).