Comparer des nombres modulo. Comparaison modulo un nombre naturel

Définition 1. Si deux nombres sont 1) un Et b lorsqu'il est divisé par p donne le même reste r, alors ces nombres sont appelés équireste ou comparable en module p.

Déclaration 1. Laisser p un nombre positif. Puis chaque numéro un toujours et en plus Le seul moyen peut être représenté sous la forme

Mais ces nombres peuvent être obtenus en définissant régal à 0, 1, 2,..., p−1. Ainsi sp+r=a obtiendra toutes les valeurs entières possibles.

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

(2)

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

Nombre r appelé moins Nombres un module p(en d'autres termes, le nombre r appelé le reste d'un nombre un sur p).

Déclaration 2. Si deux nombres un Et b comparable en module p, Que a−b divisé par p.

Vraiment. Si deux nombres un Et b comparable en module p, puis lorsqu'il est divisé par p avoir le même reste p. Alors

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

Déclaration 3. Si la différence de deux nombres est divisible par p, alors ces nombres sont comparables en module p.

Preuve. Notons par r Et r Reste de 1 division un Et b sur p. 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 tout le monde un Et p Toujours

il n'y a pas toujours de comparaison

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

Preuve. Laisser λ le plus grand diviseur commun Nombres m Et p. Alors

Parce que m(une−b) divisé par k, Que

Ainsi

Et m est l'un des diviseurs du nombre p, Que

Où h = pqs.

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

Définitions

Deux entiers a et b comparable en module nombre naturel n (ou équirestant lorsqu'ils sont divisés par n), si lorsqu'ils sont divisés par n, ils donnent le même reste.

Formulations équivalentes : a et b comparable en module n si leur différence un - b est divisible par n, ou si a peut être représenté par un = b + kn , Où k- un nombre entier. Par exemple : 32 et −10 sont comparables modulo 7, puisque

L’énoncé « a et b sont comparables modulo n » s’écrit :

Propriétés d'égalité modulo

La relation de comparaison modulo a les propriétés

Deux entiers quelconques un Et b comparable modulo 1.

Pour que les chiffres un Et bétaient comparables en module n, il faut et il suffit que leur différence soit divisible par n.

Si les nombres et sont comparables deux à deux en module n, alors leurs sommes et , ainsi que les produits et sont également comparables en module n.

Si les chiffres un Et b comparable en module n, puis leurs diplômes un k Et b k sont également comparables en module n sous n'importe quel naturel k.

Si les chiffres un Et b comparable en module n, Et n divisé par m, Que un Et b comparable en module m.

Pour que les chiffres un Et bétaient comparables en module n, présenté sous la forme de sa décomposition canonique en facteurs simples p je

nécessaire et suffisant pour

La relation de comparaison est une relation d’équivalence et possède de nombreuses propriétés des égalités ordinaires. Par exemple, ils peuvent être additionnés et multipliés : si

Toutefois, les comparaisons ne peuvent généralement pas être divisées entre elles ou par d’autres nombres. Exemple : , cependant en réduisant de 2, on obtient une comparaison erronée : . Les règles d'abréviation pour les comparaisons sont les suivantes.

Vous ne pouvez pas non plus effectuer d'opérations sur des comparaisons si leurs modules ne correspondent pas.

Autres propriétés :

Définitions associées

Classes de déduction

L'ensemble de tous les nombres comparables à un module n appelé classe de déduction un module n , et est généralement noté [ un] n ou . Ainsi, la comparaison équivaut à l'égalité des classes de résidus [un] n = [b] n .

Depuis la comparaison modulo n est une relation d'équivalence sur l'ensemble des entiers, alors les classes de résidus modulo n représentent les classes d'équivalence ; leur nombre est égal n. L'ensemble de toutes les classes de résidus modulo n désigné par ou.

Les opérations d'addition et de multiplication induisent des opérations correspondantes sur l'ensemble :

[un] n + [b] n = [un + b] n

Par rapport à ces opérations, l'ensemble est un anneau fini, et si n simple - 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 modulo n est un ensemble de n entiers incomparables modulo n. Habituellement, les plus petits résidus non négatifs sont considérés comme un système complet de résidus modulo n

0,1,...,n − 1

ou les plus petites déductions absolues constituées de nombres

en cas d'impair n et des chiffres

en cas de même n .

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 :

La résolution d'une telle comparaison commence par le calcul du pgcd (une, m)=ré. Dans ce cas, 2 cas sont possibles :

Si b pas un multiple d, alors la comparaison n'a pas de solutions.
Si b plusieurs d, alors la comparaison a une solution unique modulo m / d, ou, ce qui est pareil, d solutions modulables m. Dans ce cas, suite à la réduction de la comparaison initiale de d la comparaison est :

Où un 1 = un / d , b 1 = b / d Et m 1 = m / d sont des entiers, et un 1 et m 1 sont relativement premiers. Donc le nombre un 1 peut être inversé modulo m 1, c'est-à-dire trouver un tel nombre c, cela (en d’autres termes, ). La solution est maintenant trouvée en multipliant la comparaison obtenue par c:

Calcul pratique de la valeur c peut être fait différentes façons: en utilisant le théorème d'Euler, l'algorithme d'Euclide, la théorie des fractions continues (voir algorithme), etc. En particulier, le théorème d'Euler permet d'écrire la valeur c comme:

Exemple

A titre de comparaison nous avons d= 2, donc modulo 22 la comparaison a deux solutions. Remplaçons 26 par 4, comparable à celui-ci modulo 22, puis réduisons les 3 nombres par 2 :

Puisque 2 est premier à modulo 11, on peut réduire les côtés gauche et droit de 2. On obtient ainsi une solution modulo 11 : , équivalente à deux solutions modulo 22 : .

Comparaisons du deuxième degré

Résoudre des comparaisons du deuxième degré revient à déterminer si un nombre donné est un résidu quadratique (en utilisant la loi de réciprocité quadratique) puis à calculer la racine carrée modulo.

Histoire

Le théorème des restes chinois, connu depuis de nombreux siècles, stipule (en langage mathématique moderne) que l'anneau résiduel modulo le produit de plusieurs est mutuellement nombres premiers est le produit direct des anneaux résiduels correspondant aux facteurs.

La théorie de la divisibilité et du résidu a été largement créée par Euler. Les comparaisons modulo ont été utilisées pour la première fois par Gauss dans son livre Arithmetic Studies de 1801. Il a également proposé un symbolisme pour les comparaisons établi en mathématiques.

Pour deux entiers X Et à Introduisons une relation de comparabilité par parité si leur différence est un 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 à b module m, si leur différence est divisible par un nombre fixe entier naturel m, c'est un B divisé par m. Symboliquement, cela s'écrit :

une ≡ b(mod m),

et ça se lit comme ceci : UN comparable à b 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 sur 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 un reste 0 lorsqu'ils sont divisés par 3), la classe des nombres qui laissent un reste 1 lorsqu'ils sont divisés par 3, et la classe des nombres qui laissent un reste un reste 2 lorsqu'il est 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 Les nombres dans le système de nombres décimaux ont 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, b- nombre de dizaines, etc. Depuis 10k ≡ 1(mod9) pour tout k≥0, alors d’après 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 donc

Cependant, il n'est pas toujours possible de réduire une comparaison par un facteur quelconque : par exemple, il est impossible de la réduire du 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. Couramment utilisé système complet résidus, constitués de nombres : 0, 1, 2, ..., m-1. Soustraire le nombre n module m est le reste de la division n sur m, qui découle de la représentation n = km + r, 0<r<m- 1.

Si deux entiers une (\style d'affichage a) Et b (style d'affichage b)à division sur 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 forme de 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) é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

une ≡ b (mod m) . (\displaystyle a\equiv b(\pmod (m)).)

Ainsi,

une − b = m t . (\ displaystyle ab = mt.)

Parce que ré (style d'affichage d) est diviseur Nombres m (style d'affichage m), Que

m = c ré (\ displaystyle m = cd).

Ainsi,

a − b = m t = c ré t = q ré , (q = c t) (\displaystyle a-b=mt=cdt=qd,(q=ct)) une ≡ b (mod d) (\displaystyle a\equiv b(\pmod (d)))

un-prieuré.

Preuve

une ≡ b (mod m je) , je = 1 , 2 , . . . , k. (\displaystyle a\equiv b(\pmod (m_(i))),i=1,2,...,k.)

Ainsi,

une − b = m je t . (\ displaystyle ab = m_ (i) t.)

Depuis la différence une − b (\ displaystyle a-b) est un multiple de chacun, alors c'est un multiple d'eux multiple moins commun

Conséquence: Pour que les chiffres une (\style d'affichage a) Et b (style d'affichage b)étaient comparables en module m (style d'affichage m), décomposition canonique dont les facteurs premiers ont la forme m = ∏ je = 1 ré p je α je , (\displaystyle m=\prod _(i=1)^(d)p_(i)^(\alpha _(i)),)

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) .

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 , . . . , une n (\displaystyle a_(1),a_(2),...,a_(n)) Et b 1 , b 2 , . . . , bn (\displaystyle b_(1),b_(2),...,b_(n)) comparable par paire en module m (style d'affichage m), puis leurs sommes une 1 + une 2 + . . . + une n (\displaystyle a_(1)+a_(2)+...+a_(n)) Et b 1 + b 2 + . . . + bn (\displaystyle b_(1)+b_(2)+...+b_(n)), ainsi que des travaux une 1 ⋅ une 2 ⋅ . . . ⋅ une n (\displaystyle a_(1)\cdot a_(2)\cdot ...\cdot a_(n)) Et b 1 ⋅ b 2 ⋅ . . . ⋅ b n (\displaystyle b_(1)\cdot b_(2)\cdot ...\cdot b_(n)) 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 une (\style d'affichage a) Et b (style d'affichage b) comparable en module m (style d'affichage m), puis leurs diplômes une k (\ displaystyle a ^ (k)) Et b k (\style d'affichage b^(k)) sont également comparables en module m (style d'affichage m) sous n'importe quel naturel 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 une (\style d'affichage a) Et b (style d'affichage b) comparable modulo un certain nombre m (style d'affichage m), alors une + t 1 (\ displaystyle a + t_ (1)) comparable à b + t 2 (\displaystyle b+t_(2)) module m (style d'affichage m) (t 1 (\style d'affichage t_(1)) Et t 2 (\displaystyle t_(2))- arbitraire entier nombres). 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 une (\style d'affichage a) Et b (style d'affichage b) comparable modulo certains la totalité Nombres m (style d'affichage m), puis les chiffres une q (\ displaystyle aq) Et 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 : 7 ≡ 10 (mod 6) (\displaystyle 7\equiv 10(\pmod (6))). Les règles d'abréviation pour les comparaisons sont les suivantes.

Vous pouvez diviser les deux côtés de la comparaison par un nombre, mais seulement mutuellement premier avec module : si

une ré ≡ b ré (mod m) (\displaystyle (ad)\equiv (bd)(\pmod (m))) Et PGCD (d , m) = 1 , (\displaystyle ((d,m)=1),) Que .

Si, numéro ré (style d'affichage d) Pas mutuellement juste avec un module, comme c'était le cas dans l'exemple ci-dessus, puis réduire de ré (style d'affichage d) 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))) .

Définitions associées

Classes de déduction

L'ensemble de tous les nombres comparables à une (\style d'affichage a) module m (style d'affichage m), appelé classe de déduction une (\style d'affichage a) module m (style d'affichage m) , et est généralement noté [ une ] m (\displaystyle [a]_(m)) ou une ¯ m (\displaystyle (\bar (a))_(m)). Donc la comparaison une ≡ b (mod m) (\displaystyle a\equiv b(\pmod (m))) est équivalent à l'égalité des classes de résidus [ une ] m = [ b ] m (\displaystyle [a]_(m)=[b]_(m)) .

N'importe quel numéro de classe est appelé moins module m (style d'affichage m). Laissez pour certitude r (style d'affichage r)―reste de la division l'un des représentants de la classe sélectionnée sur m (style d'affichage m), alors n'importe quel nombre q (style d'affichage q) de cette classe peut être représenté comme q = m t + r (\ displaystyle q = mt + r), Où t (style d'affichage t) -entier. Déduction égale le reste r (style d'affichage r) appelé plus petite déduction non négative, et la déduction ρ ( displaystyle rho ), le plus petit en valeur absolue, est appelé 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))), Que ρ = − m 2 (\displaystyle \rho =-(\frac (m)(2))) .

Depuis la comparabilité modulo m (style d'affichage m) est relation d'équivalence sur l'ensemble des entiers, puis les classes de résidus modulo m (style d'affichage m) représenter 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) ) ou 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)):

[ une ] m + [ b ] m = [ une + b ] m (\displaystyle [a]_(m)+[b]_(m)=_(m)) [ une ] m ⋅ [ b ] m = [ une ⋅ b ] m (\displaystyle [a]_(m)\cdot [b]_(m)=_(m))

Concernant ces opérations, il existe de nombreuses Z m (\displaystyle \mathbb (Z)_(m)) est définitif anneau, et pour simple 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 :

0 , 1 , … , m − 1 (\displaystyle 0,1,\ldots,m-1)

ou déductions absolument minimes, composé de chiffres

0 , ± 1 , ± 2 , … , ± m − 1 2 (\displaystyle 0,\pm 1,\pm 2,\ldots,\pm (\frac (m-1)(2))), quand impair m (style d'affichage m), et des chiffres 0 , ± 1 , ± 2 , … , ± (m 2 − 1) , m 2 (\displaystyle 0,\pm 1,\pm 2,\ldots ,\pm ((\frac (m)(2))- 1),(\frac (m)(2))) quand même m (style d'affichage m).

L'ensemble maximum de modules incomparables par paires m (style d'affichage m) Nombres, mutuellement premier Avec m (style d'affichage m), appelé 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 d'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é

DANS la théorie du nombre , cryptographie et d'autres domaines scientifiques, la tâche de trouver des solutions aux comparaisons de premier degré de la forme se pose souvent :

une X ≡ b (mod m) . (\displaystyle ax\equiv b(\pmod (m)).)

La résolution d'une telle comparaison commence par calculer ré = (\style d'affichage d=) PGCD (une , m) (\ displaystyle (a, m)). Dans ce cas, 2 cas sont possibles :

une 1 x ≡ b 1 (mod m 1) (\displaystyle a_(1)x\equiv b_(1)(\pmod (m_(1)))) Où une 1 = une ré (\displaystyle a_(1)=(\frac (a)(d))), b 1 = b ré (\displaystyle b_(1)=(\frac (b)(d))) Et m 1 = m ré (\displaystyle m_(1)=(\frac (m)(d))) sont nombres entiers, et m 1 (\style d'affichage m_(1)) mutuellement simples. Donc le nombre une 1 (\ displaystyle a_ (1)) peut être inversé modulo m 1 (\style d'affichage m_(1)), c'est-à-dire trouver un tel nombre c (style d'affichage c), Quoi c ⋅ une 1 ≡ 1 (mod m 1) (\displaystyle c\cdot a_(1)\equiv 1(\pmod (m_(1))))(autrement dit, c ≡ a 1 − 1 (mod m 1) (\displaystyle c\equiv a_(1)^(-1)(\pmod (m_(1))))). La solution est maintenant trouvée en multipliant la comparaison obtenue par c (style d'affichage c): X ≡ c une 1 X ≡ c b 1 ≡ une 1 − 1 b 1 (mod m 1) . (\displaystyle x\equiv ca_(1)x\equiv cb_(1)\equiv a_(1)^(-1)b_(1)(\pmod (m_(1))).)

Calcul pratique de la valeur c (style d'affichage c) peut être réalisé de différentes manières : en utilisant Théorème d'Euler , Algorithme euclidien, théories fractions continues(cm. algorithme) etc. En particulier, Théorème d'Euler vous permet d'écrire une valeur c (style d'affichage c) comme:

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

Exemple 1. En comparaison

6 x ≡ 26 (mod 22) (\displaystyle 6x\equiv 26(\pmod (22)))

nous avons ré = 2 (\ displaystyle d = 2), 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 :

3 x ≡ 2 (mod 11) (\displaystyle 3x\equiv 2(\pmod (11)))

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

3 − 1 ≡ 4 (mod 11) (\displaystyle 3^(-1)\equiv 4(\pmod (11))).

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

x ≡ 8 (mod 11) (\displaystyle x\equiv 8(\pmod (11))),

équivalent à la combinaison de deux solutions modulo 22 :

x ≡ 8 (mod 22) (\displaystyle x\equiv 8(\pmod (22))) Et x ≡ 19 (mod 22) (\displaystyle x\equiv 19(\pmod (22))).

Exemple 2. Comparaison donnée :

100 x ≡ 41 (mod 65537) . (\displaystyle 100x\equiv 41(\pmod (65537)).) Notez que le module est un nombre premier.

La première solution consiste à utiliser rapport sans. En utilisant Algorithme euclidien ou le programme donné dans l'article sur la relation de Bezout, on trouve que c'est la relation des nombres 100 (style d'affichage 100) Et 65537 (style d'affichage 65537) a la forme :

17695 ⋅ 100 + (− 27) ⋅ 65537 = 1 , (\displaystyle 17695\cdot 100+(-27)\cdot 65537=1,) ou 17695 ⋅ 100 ≡ 1 (mod 65537) (\displaystyle 17695\cdot 100\equiv 1(\pmod (65537)))

En multipliant les deux côtés de cette comparaison par 41, nous obtenons :

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 la division 725495 (style d'affichage 725495) sur 65537 (style d'affichage 65537)). 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 a: 65537 x ≡ 26855 + 37 x (mod 65537) (\displaystyle 65537x\equiv 26855+37x(\pmod (65537))), mais le côté gauche est un multiple 65537 (style d'affichage 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). Multiplions les deux côtés de la comparaison obtenue à l'étape précédente par le quotient 1771 (\style d'affichage 1771) et ajouter 10x (\style d'affichage 10x); en remplaçant à nouveau le côté gauche par zéro, nous obtenons.