L'opération consistant à remplacer un entier par son reste de la division par un modulus n donné, c'est-à-dire la projection Z → Z/nZ et le travail avec des classes de congruence plutôt qu'avec des entiers absolus.

Principe

La congruence modulo n partitionne les entiers en n classes résiduelles ; la réduction modulaire est la projection canonique envoyant un entier a sur sa classe [a]_n et respecte l'addition et la multiplication, de sorte que les calculs descendent au quotient anneau ou, si n est premier, au corps à n éléments.

Démonstration

En pratique on réduit les coefficients de polynômes modulo n pour effectuer des calculs dans (Z/nZ)[x], ou on réduit des valeurs intermédiaires en exponentiation modulaire en remplaçant de grandes puissances par leurs résidus pour maintenir l'arithmétique raisonnable ; par exemple calculer 3^{100} modulo 7 par réductions successives fournit un petit représentant.

Mauvaise application

Réduire des opérandes avant d'effectuer des opérations qui exigent l'inversibilité sans vérifier les conditions de pgcd (par exemple diviser par un nombre non inversible modulo n), ou traiter la réduction modulaire comme sans perte dans des contextes où il faut reconstituer des informations (valeur entière exacte, retenues).

Conséquence

La réduction modulaire rend l'arithmétique finie et calculable, sous-tend le raisonnement par congruence et permet la construction d'anneaux et de corps finis ; une utilisation correcte aboutit à des algorithmes efficaces en cryptographie, théorie du codage et théorie algorithmique des nombres, tout en nécessitant une gestion des inversibilités et des relèvements si besoin.

Inversion

La réversion est le relèvement ou la reconstruction : récupérer un entier ou des données plus riches à partir de leurs résidus (par le théorème des restes chinois ou le relèvement de Hensel) ou travailler dans Z plutôt que Z/nZ ; la réduction jette des informations (inverses multiplicatifs, retenues) que le relèvement cherche à reconstituer.

Limite

S'applique aux entiers et structures entières pour un modulus fixé ; se distingue de la réduction modulo idéaux premiers en théorie des nombres algébriques (qui généralise l'idée), ou des opérations sur d'autres quotients — exclut d'identifier réduction et division ou de confondre représentants de classes résiduelles avec des entiers canoniques.

Tension sémantique

Tension entre considérer la réduction modulaire comme une simplification calculatoire (projection avec perte) et voir les résidus comme des remplaçants pleins des entiers en contextes théoriques : il faut distinguer quand l'information perdue est négligeable et quand elle empêche la récupération ou l'inversibilité.

Synthèse

La réduction modulaire est la projection canonique des entiers sur leurs classes modulo n qui permet l'arithmétique finie : elle préserve les opérations d'anneau, simplifie les calculs en travaillant avec des représentants et impose de veiller à l'inversibilité et au relèvement quand l'information entière exacte ou des propriétés de division sont nécessaires.