For two integers X and at we introduce the relation of parity comparability if their difference is an even number. It is easy to check that in this case all three previously introduced equivalence conditions are satisfied. The equivalence relation introduced in this way divides the whole set of integers into two disjoint subsets: a subset of even numbers and a subset of odd numbers.
Generalizing this case, we will say that two integers that differ by a multiple of some fixed natural number are equivalent. This is the basis of the concept of modulo comparability introduced by Gauss.
Number a, comparable to b modulo m if their difference is divisible by a fixed natural number m, that is a - b divided by m. Symbolically, this is written as:
a ≡ b(mod m),
and it reads like this: a comparable to b modulo m.
The relation introduced in this way, thanks to the deep analogy between comparisons and equalities, simplifies calculations in which numbers differing by a multiple m, do not actually differ (since comparison is equality up to some multiple of m).
For example, the numbers 7 and 19 are congruent modulo 4, but not congruent modulo 5, because 19-7=12 is divisible by 4 and not divisible by 5.
It can also be said that the number X modulo m equal to the remainder of the integer division X on m, as
x=km+r, r = 0, 1, 2, ... , m-1.
It is easy to check that the comparability of numbers modulo a given property has all the properties of equivalence. Therefore, the set of integers is divided into classes of numbers comparable to each other modulo m. The number of such classes is m, and all numbers of the same class when divided by m give the same remainder. For example, if m= 3, then three classes are obtained: the class of numbers that are multiples of 3 (giving a remainder of 0 when divided by 3), the class of numbers that give a remainder of 1 when divided by 3, and the class of numbers that give a remainder of 2 when divided by 3.
Examples of the use of comparisons are provided by well-known divisibility tests. The usual representation of a number n digits in the decimal number system has the form:
n = c10 2 + b10 1 + a10 0,
where a, b, c, are the digits of the number, written from right to left, so that a- number of units, b- the number of tens, etc. Since 10k ≡ 1(mod9) for any k≥0, then it follows from what has been written that
n ≡ c + b + a(mod9),
whence follows the test for divisibility by 9: n is divisible by 9 if and only if the sum of its digits is divisible by 9. This argument also holds when replacing 9 by 3.
We get the sign of divisibility by 11. Comparisons take place:
10≡- 1(mod11), 10 2 ≡ 1(mod11) 10 3 ≡- 1(mod11), and so on. therefore n ≡ c - b + a - ....(mod11).
Consequently, n is divisible by 11 if and only if alternating sum its digits a - b + c -... is divisible by 11.
For example, the alternating sum of the digits of the number 9581 is 1 - 8 + 5 - 9 = -11, it is divisible by 11, which means that the number 9581 is also divisible by 11.
If there are comparisons:, then they can be added, subtracted and multiplied term by term in the same way as equalities:
The comparison can always be multiplied by an integer:
if , then
However, reduction of the comparison by any factor is not always possible, For example, but it is impossible to reduce by the factor 6 common to the numbers 42 and 12; such a reduction leads to an incorrect result, since .
It follows from the definition of modulo comparability that reduction by a factor is admissible if this factor is relatively prime to the modulus.
It has already been noted above that any integer is congruent mod m with one of the following numbers: 0, 1, 2,... , m-1.
In addition to this series, there are other series of numbers that have the same property; so, for example, any number is comparable mod 5 with one of the following numbers: 0, 1, 2, 3, 4, but is also comparable with one of the following numbers: 0, -4, -3, -2, -1, or 0, 1, -1, 2, -2. Any such series of numbers is called a complete system of residues modulo 5.
Thus, the complete system of residues mod m any series is called m numbers, no two of which are incomparable with each other. Usually a full system of deductions is used, consisting of numbers: 0, 1, 2, ..., m-1. subtracting a number n modulo m is the remainder of the division n on m, which follows from the representation n = km + r, 0<r<m- 1.
BORIS NIKOLAEVICH PERVUSHKIN
PEI "St. Petersburg School "Tete-a-Tete"
Mathematics teacher of the highest category
Comparing numbers modulo
Definition 1. If two numbers1 ) aandbwhen dividing bypgive the same remainderr, then such numbers are called equidistant orcomparable in modulo p.
Statement 1. Letpsome positive number. Then any numberaalways and, moreover, in a unique way can be represented in the form
| a=sp+r, | (1) |
wheres- number, androne of the numbers 0,1, ...,p−1.
1 ) In this article, the word number will mean an integer.
Really. Ifsgets a value from −∞ to +∞, then the numbersspare the collection of all numbers that are multiplesp. Consider numbers betweenspand (s+1) p=sp+p. Asppositive integer, thenspandsp+pthere are numbers
But these numbers can be obtained by askingrequal to 0, 1, 2,...,p-1. Consequentlysp+r=atakes all possible integer values.
Let us show that this representation is unique. Let's pretend thatpcan be represented in two waysa=sp+randa=s1 p+ r1 . Then
or
| (2) |
Asr1 takes one of the numbers 0,1, ...,p−1, then the absolute valuer1 − rsmallerp. But from (2) it follows thatr1 − rmultiplep. Consequentlyr1 = rands1 = s.
Numberrcalledminus numbersamodulop(in other words, the numberrcalled the remainder of the division of a numberaonp).
Statement 2. If two numbersaandbcomparable modulop, thena−bdivided byp.
Really. If two numbersaandbcomparable modulop, then when divided byphave the same remainderp. Then
wheresands1 some whole numbers.
The difference between these numbers
| (3) |
divided byp, because the right side of equation (3) is divided byp.
Statement 3. If the difference of two numbers is divisible byp, then these numbers are comparable modulop.
Proof. Denote byrandr1 remainder from divisionaandbonp. Then
where
According toa−bdivided byp. Consequentlyr− r1 is also divided intop. But sincerandr1 numbers 0,1,...,p−1, then the absolute value |r− r1 |< p. Then, in order tor− r1 divided intopcondition must be metr= r1 .
It follows from the statement that comparable numbers are those numbers whose difference is divisible by the modulus.
If you need to write down that the numbersaandbcomparable to each other modulop, then use the notation (introduced by Gauss):
| a≡bmod(p) |
Examples 25≡39 (mod 7), −18≡14 (mod 4).
It follows from the first example that 25 when divided by 7 gives the same remainder as 39. Indeed, 25=3 7+4 (remainder 4). 39=3 7+4 (remainder 4). When considering the second example, keep in mind that the remainder must be a non-negative number less than the modulus (ie 4). Then we can write: −18=−5 4+2 (remainder 2), 14=3 4+2 (remainder 2). Therefore, −18 when divided by 4 leaves a remainder of 2, and 14 when divided by 4 leaves a remainder of 2.
Properties of Modulo Comparisons
Property 1. For anyoneaandpalways
| a≡amod(p). |
Property 2. If two numbersaandccomparable to the numberbmodulop, thenaandcare comparable to each other in the same modulus, i.e. if
| a≡bmod(p), b≡cmod(p). |
then
| a≡cmod(p). |
Really. From the condition of property 2 it followsa−bandb−care divided intop. Then their suma−b+(b−c)=a−calso divided intop.
Property 3. If
| a≡bmod(p) andm≡nmod(p), |
then
| a+m≡b+nmod(p) anda−m≡b−nmod(p). |
Really. Asa−bandm−nare divided intop, then
| ( a−b)+ ( m−n)=( a+m)−( b+n) , |
| ( a−b)−( m−n)=( a−m)−( b−n) |
also divided intop.
This property can be extended to any number of comparisons that have the same modulus.
Property 4. If
| a≡bmod(p) andm≡nmod(p), |
then
Furtherm−ndivided byp, Consequentlyb(m−n)=bm−bnalso divided intop, means
| bm≡bnmod(p). |
So two numbersamandbncomparable in modulus with the same numberbm, hence they are comparable to each other (property 2).
Property 5. If
| a≡bmod(p). |
then
| ak≡bkmod(p). |
whereksome non-negative integer.
Really. We havea≡bmod(p). Property 4 implies
| ................. |
| ak≡bkmod(p). |
All properties 1-5 present in the following statement:
Statement 4. Letf( x1 , x2 , x3 , ...) is an entire rational function with integer coefficients and let
| a1 ≡ b1 , a2 ≡ b2 , a3 ≡ b3 , ... mod (p). |
then
| f( a1 , a2 , a3 , ...)≡ f( b1 , b2 , b3 , ...) mod (p). |
With division, things are different. From comparison
Statement 5. Let
whereλ this isgreatest common divisornumbersmandp.
Proof. Letλ greatest common divisor of numbersmandp. Then
Asm(a−b)divided byk, then
has zero remainder, i.e.m1 ( a−b) divided byk1 . But the numbersm1 andk1 numbers are coprime. Consequentlya−bdivided byk1 = k/λand then,p,q,s.
Really. Differencea≡bmust be a multiple ofp,q,s.and therefore must be a multipleh.
In a particular case, if the modulesp,q,srelatively prime numbers, then
| a≡bmod(h), |
whereh=pqs.
Note that we can allow comparisons in negative modules, i.e. comparisona≡bmod(p) means in this case that the differencea−bdivided byp. All properties of comparisons remain valid for negative modules.
Comparison with one unknown x has the form
Where . If a n not divisible by m, then it is called degree comparisons.
Decision comparison is any integer x 0 , for which
If X 0 satisfies the comparison, then, according to property 9 of comparisons, this comparison will satisfy all integers comparable with x 0 modulo m. Therefore, all comparison solutions belonging to the same class of modulo residues t, we will consider as one solution. Thus, a comparison has as many solutions as there are elements of the complete system of residues that satisfy it.
Comparisons whose solution sets are the same are called equivalent.
2.2.1 Comparisons of the first degree
Comparison of the first degree with one unknown X has the form
(2.2)
Theorem 2.4. For a comparison to have at least one solution, it is necessary and sufficient that the number b divided by GCD( a, m).
Proof. We first prove the necessity. Let d
=
GCD( a,
m)
and X 0
- comparison solution. Then 
, that is, the difference Oh 0
−
b
divided by t. So there is an integer q,
what Oh 0
−
b
=
qm.
From here b= ah 0
−
qm.
And since d,
as a common divisor, divides numbers a and t, then the minuend and the subtrahend are divided by d,
and hence b
divided by d.
Now let's prove the sufficiency. Let d- greatest common divisor of numbers a and t, and b divided by d. Then, by the definition of divisibility, there are integers a 1 , b 1 ,t 1 , what .
Using the extended Euclid algorithm, we find a linear representation of the number 1 = gcd( a 1 , m 1 ):
for some x 0 , y 0 . We multiply both parts of the last equality by b 1 d:
or, which is the same,
,
that is, , and is the solution of the comparison. □
Example 2.10. Comparison 9 X= 6 (mod 12) has a solution because gcd(9, 12) = 3 and 6 is divisible by 3. □
Example 2.11. Comparison 6x= 9 (mod 12) has no solutions because gcd(6, 12) = 6 and 9 is not divisible by 6. □
Theorem 2.5. Let congruence (2.2) be decidable and d = GCD( a, m). Then the set of solutions of comparison (2.2) consists of d modulo residue classes t, namely, if X 0 is one of the solutions, then all other solutions are
Proof. Let X 0
is the solution of comparison (2.2), i.e. 
and ,
.
So there is such q, what Oh 0
−
b
=
qm.
Substituting now into the last equality instead of X 0
an arbitrary solution of the form, where, we obtain the expression
, divisible by m. □
Example 2.12. Comparison 9 X=6 (mod 12) has exactly three solutions since gcd(9, 12)=3. These solutions are: X 0 \u003d 2, x 0 + 4 \u003d 6, X 0 + 2∙4=10.□
Example 2.13. Comparison 11 X=2 (mod 15) has a unique solution X 0 = 7 since gcd(11,15)=1.□
Let us show how to solve first-degree comparison. Without loss of generality, we will assume that GCD( a, t) = 1. Then the solution of congruence (2.2) can be sought, for example, using the Euclidean algorithm. Indeed, using the extended Euclidean algorithm, we represent the number 1 as a linear combination of numbers a and t:
Multiply both sides of this equation by b, we get: b = abq + mrb, where abq - b = - mrb, that is a ∙ (bq) = b(mod m) and bq is the solution of comparison (2.2).
Another way to solve is to use Euler's theorem. Again, we assume that GCD(a, t)= 1. We apply the Euler theorem: 
. Multiply both sides of the comparison by b:
.
Rewriting the last expression as 
, we obtain that is the solution of congruence (2.2).
Let now GCD( a, m) = d>1. Then a = atd, m = mtd, where gcd( a 1 , m 1) = 1. In addition, it is necessary b = b 1 d, for the comparison to be resolvable. If X 0 - comparison solution a 1 x = b 1 (mod m 1), and the only one, because GCD( a 1 , m 1) = 1, then X 0 will be the decision and comparison a 1 xd = db 1 (mod m 1), that is, the original comparison (2.2). Rest d- 1 solutions are found by Theorem 2.5.
If two integers a (\displaystyle a) and b (\displaystyle b) at division on m (\displaystyle m) give the same remainder, they are called comparable(or equidistant) modulo a number m (\displaystyle m) . Template:/frame Comparability of numbers a (\displaystyle a) and b (\displaystyle b) is written as a formula ( comparisons):
Number m (\displaystyle m) called module comparisons.
Definition comparability numbers a (\displaystyle a) and b (\displaystyle b) modulo m (\displaystyle m) is tantamount to any of the following statements:
Proof
In addition to the above properties, the following statements are true for comparisons:
Proof
a ≡ b (mod m) . (\displaystyle a\equiv b(\pmod (m)).)Consequently,
a − b = m t . (\displaystyle a-b=mt.)As d (\displaystyle d) is divider numbers m (\displaystyle m), then
m = c d (\displaystyle m=cd).Consequently,
a − b = m t = c d t = q d , (q = c t) (\displaystyle a-b=mt=cdt=qd,(q=ct)) a ≡ b (mod d) (\displaystyle a\equiv b(\pmod (d)))a-priory.
Proof
a ≡ b (mod m i) , i = 1 , 2 , . . . , k . (\displaystyle a\equiv b(\pmod (m_(i))),i=1,2,...,k.)Consequently,
a − b = m i t . (\displaystyle a-b=m_(i)t.)Since the difference a − b (\displaystyle a-b) is a multiple of each , then it is a multiple of their least common multiple
Consequence: In order for the numbers a (\displaystyle a) and b (\displaystyle b) were comparable modulo m (\displaystyle m), canonical expansion into prime factors of which has the form m = ∏ i = 1 d p i α i , (\displaystyle m=\prod _(i=1)^(d)p_(i)^(\alpha _(i)),)necessary and sufficient to
a ≡ b (mod p i α i) , i = 1 , 2 , … , d (\displaystyle a\equiv b(\pmod (p_(i)^(\alpha _(i)))),\quad i= 1,2,\dots ,d) .Operations with Comparisons
Comparisons modulo one and the same have many of the properties of ordinary equalities. For example, they can be added, subtracted and multiplied: if the numbers a 1 , a 2 , . . . , a n (\displaystyle a_(1),a_(2),...,a_(n)) and b 1 , b 2 , . . . , b n (\displaystyle b_(1),b_(2),...,b_(n)) pairwise comparable modulo m (\displaystyle m), then their sums a 1 + a 2 + . . . + a n (\displaystyle a_(1)+a_(2)+...+a_(n)) and b1 + b2 + . . . + b n (\displaystyle b_(1)+b_(2)+...+b_(n)), as well as works a 1 ⋅ a 2 ⋅ . . . ⋅ a n (\displaystyle a_(1)\cdot a_(2)\cdot ...\cdot a_(n)) and b 1 ⋅ b 2 ⋅ . . . ⋅ b n (\displaystyle b_(1)\cdot b_(2)\cdot ...\cdot b_(n)) are also comparable modulo m (\displaystyle m). However, you cannot perform these operations with comparisons if their modules do not match.
Separately, it should be noted that the same number can be added to both parts of the comparison, it is also possible to transfer the number from one part of the comparison to another with a sign change. If numbers a (\displaystyle a) and b (\displaystyle b) comparable modulo m (\displaystyle m), then their degrees a k (\displaystyle a^(k)) and b k (\displaystyle b^(k)) are also comparable modulo m (\displaystyle m) for any natural k (\displaystyle k) .
To any of the parts of the comparison, you can add an integer multiple of the module, that is, if the numbers a (\displaystyle a) and b (\displaystyle b) are comparable modulo some number m (\displaystyle m), then and a + t 1 (\displaystyle a+t_(1)) comparable to b + t 2 (\displaystyle b+t_(2)) modulo m (\displaystyle m) (t 1 (\displaystyle t_(1)) and t 2 (\displaystyle t_(2))- arbitrary whole numbers). Also, both parts of the comparison and the modulus can be multiplied by the same number, that is, if the numbers a (\displaystyle a) and b (\displaystyle b) are comparable modulo some the whole numbers m (\displaystyle m), then the numbers aq (\displaystyle aq) and bq (\displaystyle bq) are comparable modulo numbers m q (\displaystyle mq),where q (\displaystyle q) - whole.
Comparisons, however, cannot, generally speaking, be divided by each other or by other numbers. Example: 14 ≡ 20 (mod 6) (\displaystyle 14\equiv 20(\pmod (6))), however, reducing by 2, we get an erroneous comparison: 7 ≡ 10 (mod 6) (\displaystyle 7\equiv 10(\pmod (6))). The reduction rules for comparisons are as follows.
- You can divide both sides of the comparison by a number, but only coprime with module: if
If, number d (\displaystyle d) not mutually simple with the module, as it was in the example above, then abbreviate by d (\displaystyle d) it is forbidden.
- You can simultaneously divide both parts of the comparison and the modulus by their common divisor:
if a c ≡ b c (mod m c) (\displaystyle (ac)\equiv (bc)(\pmod (mc))), then a ≡ b (mod m) (\displaystyle a\equiv b(\pmod (m))) .
Related definitions
Deduction classes
The set of all numbers comparable to a (\displaystyle a) modulo m (\displaystyle m), is called deduction class a (\displaystyle a) modulo m (\displaystyle m) , and is usually denoted [ a ] m (\displaystyle [a]_(m)) or a ¯ m (\displaystyle (\bar(a))_(m)). So the comparison a ≡ b (mod m) (\displaystyle a\equiv b(\pmod (m))) is equivalent to the equality of the residue classes [ a ] m = [ b ] m (\displaystyle [a]_(m)=[b]_(m)) .
Any class number is called minus modulo m (\displaystyle m). Let for definiteness r (\displaystyle r)―remainder of the division any of the representatives of the selected class on m (\displaystyle m), then any number q (\displaystyle q) from this class can be represented as q = m t + r (\displaystyle q=mt+r), where t (\displaystyle t) -whole. deduction equal remnant r (\displaystyle r) called the smallest non-negative residue, and the deduction ρ (\displaystyle \rho ), the smallest in absolute value, is called absolutely least deductible. At r< m 2 {\displaystyle r<{\frac {m}{2}}} we get that ρ = r (\displaystyle \rho =r), otherwise ρ = r − m (\displaystyle \rho =r-m). If m (\displaystyle m)-even and r = m 2 (\displaystyle r=(\frac (m)(2))), then ρ = − m 2 (\displaystyle \rho =-(\frac (m)(2))) .
Since comparability modulo m (\displaystyle m) is equivalence relation on the set of integers , then the residue classes modulo m (\displaystyle m) represent equivalence classes; their number is m (\displaystyle m).
The set of all residue classes modulo m (\displaystyle m) denoted or Z / m Z (\displaystyle \mathbb (Z) /m\mathbb (Z) ) or Z / (m) (\displaystyle \mathbb (Z) /(m)) .
Operations of addition and multiplication by Z (\displaystyle \mathbb (Z) ) induce the corresponding operations on the set Z m (\displaystyle \mathbb (Z) _(m)):
[ a ] m + [ b ] m = [ a + b ] m (\displaystyle [a]_(m)+[b]_(m)=_(m)) [ a ] m ⋅ [ b ] m = [ a ⋅ b ] m (\displaystyle [a]_(m)\cdot [b]_(m)=_(m))Regarding these operations, the set Z m (\displaystyle \mathbb (Z) _(m)) is final ring, and for simple m (\displaystyle m) - final field.
Deduction systems
The residue system allows you to perform arithmetic operations on a finite set of numbers without going beyond it. Complete system of deductions modulo m (\displaystyle m) is any set of m (\displaystyle m) pairwise incomparable modulo m (\displaystyle m) whole numbers. Usually as a complete system of residues modulo m (\displaystyle m) one of two sets is taken:
- smallest non-negative residues, that is, numbers:
- or absolutely the smallest deductions, consisting of numbers
The maximum set of pairwise incomparable modulo m (\displaystyle m) numbers, coprime With m (\displaystyle m), is called reduced system of residues modulo m (\displaystyle m). Any reduced system of residues modulo m (\displaystyle m) contains φ (m) (\displaystyle \varphi (m)) elements, where φ (⋅) (\displaystyle \varphi (\cdot)) - Euler function.
For example, for the number m = 42 (\displaystyle m=42). Complete system of deductions can be represented by numbers: 0 , 1 , 2 , 3 , … , 21 , 22 , 23 , … , 39 , 40 , 41 (\displaystyle 0,1,2,3,\ldots ,21,22,23,\ldots ,39,40, 41), a reduced - 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).
Comparisons in a polynomial ring over a field
Comparison decision
Comparisons of the first degree
AT number theory , cryptography and other fields of science, the problem often arises of finding solutions for comparison of the first degree of the form:
a x ≡ b (mod m) . (\displaystyle ax\equiv b(\pmod (m)).)The solution of such a comparison begins with the calculation d = (\displaystyle d=) GCD (a , m) (\displaystyle (a,m)). In this case, 2 cases are possible:
a 1 x ≡ b 1 (mod m 1) (\displaystyle a_(1)x\equiv b_(1)(\pmod (m_(1)))) where a 1 = a d (\displaystyle a_(1)=(\frac (a)(d))), b 1 = b d (\displaystyle b_(1)=(\frac (b)(d))) and m 1 = m d (\displaystyle m_(1)=(\frac (m)(d))) are whole numbers, and m 1 (\displaystyle m_(1)) mutually simple. Therefore the number a 1 (\displaystyle a_(1)) can be inverted modulo m 1 (\displaystyle m_(1)), that is, to find such a number c (\displaystyle c), what c ⋅ a 1 ≡ 1 (mod m 1) (\displaystyle c\cdot a_(1)\equiv 1(\pmod (m_(1))))(in other words, c ≡ a 1 − 1 (mod m 1) (\displaystyle c\equiv a_(1)^(-1)(\pmod (m_(1))))). Now the solution is found by multiplying the resulting comparison by c (\displaystyle c): x ≡ c a 1 x ≡ c b 1 ≡ a 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))).)Practical value calculation c (\displaystyle c) can be done in different ways: Euler's theorems , algorithm Euclid, theories continued fractions(cm. algorithm) and others. In particular, Euler's theorem allows you to write a value c (\displaystyle c) as:
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)))) .Examples
Example 1 For comparison
6 x ≡ 26 (mod 22) (\displaystyle 6x\equiv 26(\pmod (22)))we have d = 2 (\displaystyle d=2), so modulo 22 the comparison has two solutions. Let's replace 26 with 4, which is comparable modulo 22, and then cancel all three numbers by 2:
3 x ≡ 2 (mod 11) (\displaystyle 3x\equiv 2(\pmod (11)))Since 3 is coprime modulo 11, it can be inverted modulo 11 and found
3 − 1 ≡ 4 (mod 11) (\displaystyle 3^(-1)\equiv 4(\pmod (11))).Multiplying the comparison by 4, we get the solution modulo 11:
x ≡ 8 (mod 11) (\displaystyle x\equiv 8(\pmod (11))),equivalent to the set of two solutions modulo 22:
x ≡ 8 (mod 22) (\displaystyle x\equiv 8(\pmod (22))) and x ≡ 19 (mod 22) (\displaystyle x\equiv 19(\pmod (22))).Example 2 Given a comparison:
100 x ≡ 41 (mod 65537) . (\displaystyle 100x\equiv 41(\pmod (65537)).) Note that the modulus is a prime number.The first solution is to use Bezout ratio. By using algorithm Euclid or the program given in the article on Bezout's ratio, we find that this ratio for numbers 100 (\displaystyle 100) and 65537 (\displaystyle 65537) looks like:
17695 ⋅ 100 + (− 27) ⋅ 65537 = 1 , (\displaystyle 17695\cdot 100+(-27)\cdot 65537=1,) or 17695 ⋅ 100 ≡ 1 (mod 65537) (\displaystyle 17695\cdot 100\equiv 1(\pmod (65537)))Multiplying both sides of this comparison by 41, we get:
100 ⋅ 725495 ≡ 41 (mod 65537) (\displaystyle 100\cdot 725495\equiv 41(\pmod (65537)))It follows that there is a solution to the original comparison. It is more convenient to replace it with a comparable one 4588 (\displaystyle 4588)(remainder of the division 725495 (\displaystyle 725495) on 65537 (\displaystyle 65537)). Answer: x ≡ 4588 (mod 65537) . (\displaystyle x\equiv 4588(\pmod (65537)).)
The second solution, simpler and faster, does not require the construction of the Bezout relation, but is also equivalent to the Euclidean algorithm.
Step 1. Divide the modulus by the coefficient of x with a remainder: 65537 = 100 ⋅ 655 + 37 (\displaystyle 65537=100\cdot 655+37). Multiply both sides of the original comparison by the quotient 655 (\displaystyle 655) and add 37x (\displaystyle 37x); we get: 65537 x ≡ 26855 + 37 x (mod 65537) (\displaystyle 65537x\equiv 26855+37x(\pmod (65537))), but the left side is a multiple of 65537 (\displaystyle 65537), that is, comparable to zero, whence:
37 x ≡ − 26855 (mod 65537) (\displaystyle 37x\equiv -26855(\pmod (65537)))We received at x (\displaystyle x) coefficient 37 instead of 100. At each next step, we decrease in the same way until we get one.
Step 2. Similarly, we divide by a new coefficient at x: 65537 = 37 ⋅ 1771 + 10 (\displaystyle 65537=37\cdot 1771+10). Multiply both parts of the comparison obtained in the previous step by the quotient 1771 (\displaystyle 1771) and add 10x (\displaystyle 10x); again replacing the left side with zero, we get.