La théorie des nombres de comparaison modulo. Comparaison modulo un nombre naturel

Si deux entiers une (\style d'affichage a) Et b (style d'affichage b) lorsqu'il est divisé par m (style d'affichage m) donnent des résidus identiques, ils sont appelés comparable(ou également résiduel) numéro de module m (style d'affichage m) . Modèle :/frame Comparabilité des nombres une (\style d'affichage a) Et b (style d'affichage b)écrit sous la forme de la formule ( comparaisons):

Nombre m (style d'affichage m) appelé module comparaisons.

Définition comparabilité Nombres une (\style d'affichage a) Et b (style d'affichage b) module m (style d'affichage m) est équivalent à l’une des déclarations suivantes :

Preuve

En plus des propriétés ci-dessus, les déclarations suivantes sont valables pour les comparaisons :

Preuve

(\displaystyle a\equiv b(\pmod (m)).)

une − b = m t . (\ displaystyle ab = mt.) Parce que m (style d'affichage m) ré (style d'affichage d)

(\displaystyle a\equiv b(\pmod (m)).)

a − b = m t = c ré t = q ré , (q = c t) (\displaystyle a-b=mt=cdt=qd,(q=ct))

Preuve

(\displaystyle a\equiv b(\pmod (m)).)

une ≡ b (mod m je) , je = 1 , 2 , . ..

une − b (\ displaystyle a-b)

Conséquence:

Pour que les chiffres étaient comparables en module Et , dont la décomposition canonique en facteurs premiers a la forme m = ∏ je = 1 ré p je α je , (\displaystyle m=\prod _(i=1)^(d)p_(i)^(\alpha _(i)),) m (style d'affichage m) nécessaire et suffisant pour une ≡ b (mod p je α je) , je = 1 , 2 , … , d (\displaystyle a\equiv b(\pmod (p_(i)^(\alpha _(i)))),\quad i= 1,2,\points,d) Et Opérations avec comparaisons Les comparaisons par rapport au même module possèdent de nombreuses propriétés des égalités ordinaires. Par exemple, ils peuvent être ajoutés, soustraits et multipliés : si les nombres une 1 , une 2 , . Et b 1 ⋅ b 2 ⋅ .. m (style d'affichage m).

⋅ b n (\displaystyle b_(1)\cdot b_(2)\cdot ...\cdot b_(n)) une (\style d'affichage a) Et b (style d'affichage b) sont également comparables en module m (style d'affichage m). Cependant, vous ne pouvez pas effectuer ces opérations avec des comparaisons si leurs modules ne correspondent pas. Par ailleurs, il convient de noter que le même numéro peut être ajouté aux deux parties de la comparaison, et vous pouvez également transférer un numéro d'une partie de la comparaison à une autre avec un changement de signe. Si les chiffres Et comparable en module. m (style d'affichage m), puis leurs diplômes une k (\ displaystyle a ^ (k)) .

b k (\style d'affichage b^(k)) une (\style d'affichage a) Et b (style d'affichage b) sous n'importe quel naturel m (style d'affichage m) k (style d'affichage k) À n'importe laquelle des parties de la comparaison, vous pouvez ajouter un multiple entier du module, c'est-à-dire si les nombres comparable modulo un certain nombre , alors module m (style d'affichage m) (une + t 1 (\ displaystyle a + t_ (1)) Et comparable à b + t 2 (\displaystyle b+t_(2)) une (\style d'affichage a) Et b (style d'affichage b) t 1 (\style d'affichage t_(1)) m (style d'affichage m) t 2 (\displaystyle t_(2)) - nombres entiers arbitraires). De plus, les deux parties de la comparaison et le module peuvent être multipliés par le même nombre, c'est-à-dire si les nombres Et comparable modulo un entier, puis les chiffres une q (\ displaystyle aq) bq (\style d'affichage bq) les nombres sont comparables modulo m q (\style d'affichage mq)

,Où q (style d'affichage q)- entier. Toutefois, les comparaisons ne peuvent généralement pas être divisées entre elles ou par d’autres nombres. Exemple: 14 ≡ 20 (mod 6) (\displaystyle 14\equiv 20(\pmod (6)))

• , cependant, en réduisant de 2, on obtient une comparaison erronée :

PGCD (\ displaystyle ab = mt.)(d , m) = 1 , (\displaystyle ((d,m)=1),) (\ displaystyle ab = mt.) Que .

• Si, numéro

pas mutuellement uniquement avec le module, comme c'était le cas dans l'exemple ci-dessus, puis réduire de c'est interdit. Vous pouvez diviser simultanément les deux côtés de la comparaison et le module par leur diviseur commun : Si .

une c ≡ b c (mod m c) (\displaystyle (ac)\equiv (bc)(\pmod (mc)))

, Que

une ≡ b (mod m) (\displaystyle a\equiv b(\pmod (m))) une (\style d'affichage a) module m (style d'affichage m) Définitions associées Classes de déduction une (\style d'affichage a) module m (style d'affichage m) L'ensemble de tous les nombres comparables à , appelé classe de déduction , et est généralement noté[ une ] ​​m (\displaystyle [a]_(m)) Si ou une ¯ m (\displaystyle (\bar (a))_(m)) .

. Donc la comparaison est équivalent à l'égalité des classes de résidus module m (style d'affichage m)[ une ] ​​​​m = [ b ] m (\displaystyle [a]_(m)=[b]_(m)) N'importe quel numéro de classe est appelé moins m (style d'affichage m). Laissez pour certitude les nombres sont comparables modulo r (style d'affichage r) q = m t + r (\ displaystyle q = mt + r), Où t (style d'affichage t)-entier. Déduction égale au solde N'importe quel numéro de classe est appelé appelé plus petite déduction non négative, et la déduction ρ ( displaystyle rho ), le plus petit valeur absolue Définitions associées absolument la plus petite déduction. À r< m 2 {\displaystyle r<{\frac {m}{2}}} nous comprenons cela ρ = r (\ displaystyle \ rho = r), sinon ρ = r − m (\displaystyle \rho =rm). Si m (style d'affichage m)-même et r = m 2 (\displaystyle r=(\frac (m)(2))) Vous pouvez diviser simultanément les deux côtés de la comparaison et le module par leur diviseur commun : ρ = − m 2 (\displaystyle \rho =-(\frac (m)(2))) .

Depuis la comparabilité modulo m (style d'affichage m) est une relation d'équivalence sur l'ensemble des entiers, alors les classes de résidus modulo m (style d'affichage m) représentent les classes d'équivalence ; leur nombre est égal m (style d'affichage m).

L'ensemble de toutes les classes de résidus modulo m (style d'affichage m) désigné par ou Z / m Z (\displaystyle \mathbb (Z) /m\mathbb (Z) ) classe de déduction Z / (m) (\displaystyle \mathbb (Z) /(m)) .

Opérations d'addition et de multiplication par Z (\ displaystyle \ mathbb (Z) ) induire les opérations correspondantes sur le plateau Z m (\displaystyle \mathbb (Z)_(m)):

Concernant ces opérations, il existe de nombreuses Z m (\displaystyle \mathbb (Z)_(m)) est un anneau fini, et pour un premier m (style d'affichage m)- champ fini.

Systèmes de déduction

Le système de résidus permet d'effectuer des opérations arithmétiques sur un ensemble fini de nombres sans dépasser ses limites. Système complet de déductions module m (style d'affichage m)- n'importe quel ensemble de m (style d'affichage m) module incomparable par paire m (style d'affichage m) entiers. Généralement sous la forme d'un système complet de déductions modulo m (style d'affichage m) l'un des deux ensembles est pris :

• moins de résidus non négatifs, c'est-à-dire des nombres :

• ou déductions absolument minimes, composé de chiffres

L'ensemble maximum de modules incomparables par paires m (style d'affichage m) nombres premiers entre eux m (style d'affichage m) Définitions associées système de déductions donné module m (style d'affichage m). Tout système réduit de résidus modulo m (style d'affichage m) contient φ (m) (\ displaystyle \ varphi (m))éléments, où φ (⋅) (\displaystyle \varphi (\cdot))- Fonction Euler.

Par exemple, pour un nombre m = 42 (\ displaystyle m = 42). Système complet de déductions peut être représenté par des nombres : 0 , 1 , 2 , 3 , … , 21 , 22 , 23 , … , 39 , 40 , 41 (\displaystyle 0,1,2,3,\ldots,21,22,23,\ldots,39,40, 41), UN donné - 1 , 5 , 11 , 13 , 17 , 19 , 23 , 25 , 29 , 31 , 37 , 41 (\displaystyle 1,5,11,13,17,19,23,25,29,31,37,41).

Comparaisons dans l'anneau de polynômes sur un corps

Résoudre des comparaisons

Comparaisons du premier degré

En théorie des nombres, en cryptographie et dans d'autres domaines scientifiques, le problème de trouver des solutions aux comparaisons de forme au premier degré se pose souvent :

(\displaystyle ax\equiv b(\pmod (m)).) La résolution d'une telle comparaison commence par calculer . Les règles d'abréviation pour les comparaisons sont les suivantes. ré = (\style d'affichage d=)(une , m) (\ displaystyle (a, m))

X ≡ c une 1 X ≡ c b 1 ≡ une 1 − 1 b 1 (mod m 1) . , c'est-à-dire trouver un tel nombre(\displaystyle x\equiv ca_(1)x\equiv cb_(1)\equiv a_(1)^(-1)b_(1)(\pmod (m_(1))).) , c'est-à-dire trouver un tel nombre Calcul pratique de la valeur

sous la forme :

c ≡ a 1 − 1 ≡ a 1 φ (m 1) − 1 (mod m 1) (\displaystyle c\equiv a_(1)^(-1)\equiv a_(1)^(\varphi (m_(1 ))-1)(\pmod (m_(1)))) Exemples

A titre de comparaison 6 x ≡ 26 (mod 22) (\displaystyle 6x\equiv 26(\pmod (22))) nous avons

, donc modulo 22 la comparaison a deux solutions. Remplaçons 26 par 4, qui est comparable modulo 22, puis réduisons les trois nombres par 2 :

Puisque 3 est premier à modulo 11, il peut être inversé modulo 11 et trouvé

En multipliant la comparaison par 4, on obtient une solution modulo 11 :

Exemple 2. Comparaison donnée :

Notez que le module est un nombre premier. La première solution consiste à utiliser la relation de Bezout. En utilisant l’algorithme d’Euclide ou le programme donné dans l’article sur la relation de Bezout, on trouve que cette relation pour les nombres Et 100 (style d'affichage 100) 65537 (style d'affichage 65537)

17695 ⋅ 100 ≡ 1 (mod 65537) (\displaystyle 17695\cdot 100\equiv 1(\pmod (65537)))

100 ⋅ 725495 ≡ 41 (mod 65537) (\displaystyle 100\cdot 725495\equiv 41(\pmod (65537))) Il s’ensuit qu’il existe une solution à la comparaison originale. Il est plus pratique de le remplacer par quelque chose de comparable 4588 (style d'affichage 4588) (reste de division 725495 (style d'affichage 725495) 100 (style d'affichage 100) sur ). Répondre:

x ≡ 4588 (mod 65537) .

(\displaystyle x\equiv 4588(\pmod (65537)).) La deuxième méthode de résolution, plus simple et plus rapide, ne nécessite pas la construction de la relation de Bezout, mais est également équivalente à l'algorithme euclidien.Étape 1. Divisez le module par le coefficient de x avec le reste : 65537 = 100 ⋅ 655 + 37 (\displaystyle 65537=100\cdot 655+37). Multipliez les deux côtés de la comparaison originale par le quotient 655 (style d'affichage 655) et ajouter 37 x (\style d'affichage 37x); on obtient : 100 (style d'affichage 100) 65537 x ≡ 26855 + 37 x (mod 65537) (\displaystyle 65537x\equiv 26855+37x(\pmod (65537)))

, c'est-à-dire comparable à zéro, d'où : 37 x ≡ − 26855 (mod 65537) (\displaystyle 37x\equiv -26855(\pmod (65537))) Nous avons reçu à

x (style d'affichage x) coefficient 37 au lieu de 100. A chaque étape suivante, nous réduisons de la même manière jusqu'à en obtenir un.Étape 2. De même, divisez par le nouveau coefficient pour x : 65537 = 37 ⋅ 1771 + 10 (\displaystyle 65537=37\cdot 1771+10). Multipliez les deux côtés de la comparaison originale par le quotient . Multiplions les deux côtés de la comparaison obtenue à l'étape précédente par le quotient 1771 (\style d'affichage 1771)

10x (\style d'affichage 10x) 1. ; en remplaçant à nouveau le côté gauche par zéro, nous obtenons. Définition Et Si deux nombres sont 1) lorsqu'il est divisé par un b p donne le même reste r un.

, alors ces nombres sont appelés équireste ou 1. comparable en module un Déclaration Définition Laisser

un nombre positif. Puis chaque numéro p toujours et d'ailleurs de la seule manière peut être représenté sous la forme un Mais ces nombres peuvent être obtenus en définissant égal à 0, 1, 2,...,−1. Ainsi

Montrons que cette représentation est unique. Supposons que un peut être représenté de deux manières a=sp+r Et a = s 1 un+p 1. Alors

(2)

une − b = m t . p 1 accepte l'un des nombres 0,1, ..., un−1, alors la valeur absolue p 1 −p moins un. Mais de (2) il résulte que p 1 −p multiple un. Ainsi p 1 =p Et s 1 =s.

Nombre p appelé est équivalent à l'égalité des classes de résidus Nombres Définition module un(en d'autres termes, le nombre p appelé le reste d'un nombre Définition 725495 (style d'affichage 725495) un).

, alors ces nombres sont appelés équireste ou 2. Si deux nombres Définition Et Si deux nombres sont 1) sont également comparables en module un Vous pouvez diviser simultanément les deux côtés de la comparaison et le module par leur diviseur commun : a−b divisé par un.

Vraiment. Si deux nombres Définition Et Si deux nombres sont 1) sont également comparables en module un, puis lorsqu'il est divisé par un avoir le même reste un. Alors

divisé par un, parce que le côté droit de l’équation (3) est divisé par un.

, alors ces nombres sont appelés équireste ou 3. Si la différence de deux nombres est divisible par un, alors ces nombres sont comparables en module un.

Preuve. Notons par p Et p Reste de 1 division Définition Et Si deux nombres sont 1) 725495 (style d'affichage 725495) un. Alors

Exemples 25≡39 (mod 7), −18≡14 (mod 4).

Du premier exemple, il résulte que 25 divisé par 7 donne le même reste que 39. En effet, 25 = 3 7 + 4 (reste 4). 39=3·7+4 (reste 4). Lorsque vous envisagez le deuxième exemple, vous devez tenir compte du fait que le reste doit être un nombre non négatif inférieur au module (c'est-à-dire 4). On peut alors écrire : −18=−5·4+2 (reste 2), 14=3·4+2 (reste 2). Par conséquent, −18 lorsqu’il est divisé par 4 laisse un reste de 2, et 14 lorsqu’il est divisé par 4 laisse un reste de 2.

Propriétés des comparaisons modulo

Propriété 1. Pour n'importe qui Définition Et un Toujours

il n'y a pas toujours de comparaison

Où λ est le plus grand commun diviseur des nombres m Et un.

Preuve. Laisser λ plus grand diviseur commun des nombres m Et un. Alors

une − b = m t . m(une−b) divisé par k ré (style d'affichage d)

Ainsi

Et m est l'un des diviseurs du nombre un ré (style d'affichage d)

Où h = pqs.

Notez que nous pouvons autoriser des comparaisons basées sur des modules négatifs, c'est-à-dire comparaison une≡b mod( un) signifie dans ce cas que la différence a−b divisé par un. Toutes les propriétés des comparaisons restent en vigueur pour les modules négatifs.

Comparaison avec une inconnue x on dirait

Où . Si Définition n non divisible par m, c'est ce qu'on appelle degré comparaisons.

Par décision la comparaison est n'importe quel entier x 0 , pour lequel

Si X 0 satisfait la comparaison, alors, selon la propriété de 9 comparaisons, tous les entiers comparables à x 0 module m. Par conséquent, toutes les solutions de comparaison appartenant à la même classe de résidus modulo T, nous le considérerons comme une solution. Ainsi, la comparaison a autant de solutions qu’il y a d’éléments du système complet de résidus qui la satisfont.

Les comparaisons dont les ensembles de solutions coïncident sont appelées équivalent.

2.2.1 Comparaisons du premier degré

Comparaison au premier degré avec une inconnue X on dirait

(2.2)

Théorème 2.4. Pour qu'une comparaison ait au moins une solution, il faut et il suffit que le nombre Si deux nombres sont 1) divisé par PGCD ( Définition, m).

Preuve. Nous prouvons d’abord la nécessité. Laisser d = PGCD( Définition, m) Et X 0 - solution de comparaison. Alors , c'est-à-dire la différence Oh 0 − Si deux nombres sont 1) divisé par T. Il existe donc un tel entier q, Quoi Oh 0 − Si deux nombres sont 1) = qm. D'ici Si deux nombres sont 1)= ah 0 − qm. Et depuis d, en tant que diviseur commun, divise les nombres UN Et T, alors le menu et le sous-trahend sont divisés par d, et donc Si deux nombres sont 1) divisé par d.

Prouvons maintenant la suffisance. Laisser d- le plus grand commun diviseur des nombres UN Et T, Et Si deux nombres sont 1) divisé par d. Alors, par définition de la divisibilité, il existe des entiers tels que Définition 1 , Si deux nombres sont 1) 1 ,T 1 , Quoi .

En utilisant l'algorithme euclidien étendu, nous trouvons une représentation linéaire du nombre 1 = pgcd( Définition 1 , m 1 ):

pour certains x 0 , oui 0 . Multipliez les deux côtés de la dernière égalité par Si deux nombres sont 1) 1 d:

ou, ce qui est pareil,

,

c'est-à-dire et c'est la solution à la comparaison. □

Exemple 2.10. Comparaison 9 X= 6 (mod 12) a une solution puisque pgcd(9, 12) = 3 et 6 est divisible par 3. □

Exemple 2.11. Comparaison 6x= 9 (mod 12) n'a pas de solution, puisque pgcd(6, 12) = 6, et 9 n'est pas divisible par 6. □

Théorème 2.5. Soit la comparaison (2.2) résoluble et d = PGCD( Définition, m). Alors l’ensemble des solutions de comparaison (2.2) se compose de d classes de résidus modulo T,à savoir, si X 0 - une des solutions, alors toutes les autres solutions sont

Preuve. Laisser X 0 - solution de comparaison (2.2), soit Et , . Donc il y a une telle chose q, Quoi Oh 0 − Si deux nombres sont 1) = qm. En remplaçant maintenant par la dernière égalité au lieu de X 0 une solution arbitraire de la forme, où, on obtient l'expression

, divisible par m. □

Exemple 2.12. Comparaison 9 X=6 (mod 12) a exactement trois solutions, puisque pgcd(9, 12)=3. Ces solutions : X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

Exemple 2.13. Comparaison 11 X=2 (mod 15) a une solution unique X 0 = 7, puisque PGCD(11,15)=1.□

Nous allons vous montrer comment résoudre des comparaisons au premier degré. Sans perte de généralité, nous supposerons que GCD( Définition, t) = 1. Alors la solution de la comparaison (2.2) peut être recherchée, par exemple, en utilisant l’algorithme euclidien. En effet, en utilisant l'algorithme euclidien étendu, nous représentons le nombre 1 comme une combinaison linéaire de nombres Définition Et T:

Multiplions les deux côtés de cette égalité par Si deux nombres sont 1), on obtient : Si deux nombres sont 1) = abq + mrb, où abq - Si deux nombres sont 1) = - mrb, c'est Définition ∙ (bq) = Si deux nombres sont 1)(mod m) Et bq- solution de comparaison (2.2).

Une autre solution consiste à utiliser le théorème d'Euler. Encore une fois, nous pensons que GCD(a, T)= 1. On applique le théorème d’Euler : . Multipliez les deux côtés de la comparaison par Si deux nombres sont 1): . Réécrire la dernière expression comme , nous obtenons que c’est une solution à la comparaison (2.2).

Laissez maintenant GCD( Définition, m) = d>1. Alors Définition = Définitiontd, m = mtd, où PGCD( UN 1 , m 1) = 1. De plus, il faut Si deux nombres sont 1) = Si deux nombres sont 1) 1 d, pour que la comparaison puisse être résolue. Si X 0 - solution de comparaison UN 1 x = Si deux nombres sont 1) 1 (mod m 1), et le seul, puisque GCD( UN 1 , m 1) = 1, alors X 0 sera la solution et la comparaison UN 1 xd = base de données 1 (mod m 1), c'est-à-dire la comparaison originale (2.2). Repos d- 1 solutions sont trouvées par le Théorème 2.5.

Pour deux entiers X Et à introduisons une relation de comparabilité en parité si leur différence est nombre pair. Il est facile de vérifier que les trois conditions d’équivalence introduites précédemment sont satisfaites. La relation d'équivalence ainsi introduite divise l'ensemble des nombres entiers en deux sous-ensembles disjoints : le sous-ensemble des nombres pairs et le sous-ensemble des nombres impairs.

En généralisant ce cas, nous dirons que deux entiers qui diffèrent par un multiple d'un nombre naturel fixe sont équivalents. C'est la base du concept de comparabilité modulo, introduit par Gauss.

Nombre UN, comparable à Si deux nombres sont 1) module m, si leur différence est divisible par un nombre fixe nombre naturel m, c'est a-b divisé par m. Symboliquement, cela s'écrit :

une ≡ b(mod m),

et ça se lit comme ceci : UN comparable modulo un certain nombre Si deux nombres sont 1) module m.

La relation ainsi introduite, grâce à l'analogie profonde entre comparaisons et égalités, simplifie les calculs dans lesquels des nombres différant par un multiple m, ne diffèrent pas réellement (puisque la comparaison est une égalité jusqu'à un multiple de m).

Par exemple, les nombres 7 et 19 sont comparables modulo 4, mais pas comparables modulo 5, car 19-7=12 est divisible par 4 et non divisible par 5.

On peut aussi dire que le nombre X module mégal au reste lors de la division par un nombre entier X 725495 (style d'affichage 725495) m, parce que

x=km+r, r = 0, 1, 2, ... , m-1.

Il est facile de vérifier que la comparabilité des nombres selon un module donné possède toutes les propriétés d'équivalence. Par conséquent, l'ensemble des entiers est divisé en classes de nombres comparables en module m. Le nombre de ces classes est égal m, et tous les nombres de la même classe lorsqu'ils sont divisés par m donne le même reste. Par exemple, si m= 3, alors nous obtenons trois classes : la classe des nombres qui sont des multiples de 3 (donnant le reste 0 lorsqu'ils sont divisés par 3), la classe des nombres qui laissent le reste 1 lorsqu'ils sont divisés par 3, et la classe des nombres donnant le reste 2 lorsque divisé par 3.

Des exemples d'utilisation de comparaisons sont fournis par les critères de divisibilité bien connus. Représentation numérique commune n en chiffres en système décimal Le calcul a la forme :

n = c10 2 + b10 1 + a10 0,

Où une, b, c,- les chiffres d'un nombre écrit de droite à gauche, donc UN- nombre d'unités, Si deux nombres sont 1)- nombre de dizaines, etc. Depuis 10k ≡ 1(mod9) pour tout k≥0, alors de ce qui est écrit il s'ensuit que

n ≡ c + b + une(mod9),

d'où découle le test de divisibilité par 9 : n est divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9. Ce raisonnement s'applique également lors du remplacement de 9 par 3.

On obtient le test de divisibilité par 11. Des comparaisons ont lieu :

10≡- 1(mod11), 10 2 ≡ 1(mod11) 10 3 ≡- 1(mod11), et ainsi de suite. C'est pourquoi n ≡ c - b + a - ….(mod11).

Ainsi, n est divisible par 11 si et seulement si la somme alternée de ses chiffres a - b + c -... est divisible par 11.

Par exemple, la somme alternée des chiffres du nombre 9581 est 1 - 8 + 5 - 9 = -11, elle est divisible par 11, ce qui signifie que le nombre 9581 est divisible par 11.

S'il existe des comparaisons : , alors elles peuvent être additionnées, soustraites et multipliées terme par terme de la même manière que les égalités :

Une comparaison peut toujours être multipliée par un entier :

si, alors

Cependant, réduire une comparaison par n'importe quel facteur n'est pas toujours possible. Par exemple, il est impossible de réduire par le facteur commun 6 pour les nombres 42 et 12 ; une telle réduction conduit à un résultat incorrect, puisque .

De la définition de la comparabilité modulo, il s'ensuit qu'une réduction d'un facteur est autorisée si ce facteur est premier au module.

Il a déjà été noté plus haut que tout entier est comparable mod m avec l'un des nombres suivants : 0, 1, 2,... , m-1.

En plus de cette série, il existe d’autres séries de nombres qui ont la même propriété ; ainsi, par exemple, tout nombre est comparable mod 5 à l'un des nombres suivants : 0, 1, 2, 3, 4, mais également comparable à l'un des nombres suivants : 0, -4, -3, -2, - 1, ou 0, 1, -1, 2, -2. Une telle série de nombres est appelée un système complet de résidus modulo 5.

Ainsi, le système complet de résidus mod m toute série de m nombres dont aucun n’est comparable entre eux. Habituellement, un système complet de déductions est utilisé, composé de nombres : 0, 1, 2, ..., m-1. Soustraire le nombre n module m est le reste de la division n 725495 (style d'affichage 725495) m, qui découle de la représentation n = km + r, 0<p<m- 1.