Comparison of numbers modulo. Comparison modulo a natural number

Definition 1. If two numbers 1) a and b when dividing by p give the same remainder r, then such numbers are called equidistant or comparable in modulo p.

Statement 1. Let p some positive number. Then any number a always and, moreover, in a unique way can be represented in the form

But these numbers can be obtained by asking r equal to 0, 1, 2,..., p-1. Consequently sp+r=a takes all possible integer values.

Let us show that this representation is unique. Let's pretend that p can be represented in two ways a=sp+r and a=s 1 p+r one . Then

(2)

Because r 1 takes one of the numbers 0,1, ..., p−1, then the absolute value r 1 −r less p. But from (2) it follows that r 1 −r multiple p. Consequently r 1 =r and s 1 =s.

Number r called minus numbers a modulo p(in other words, the number r called the remainder of the division of a number a on the p).

Statement 2. If two numbers a and b comparable modulo p, then a−b divided by p.

Really. If two numbers a and b comparable modulo p, then when divided by p have the same remainder p. Then

divided by p, because the right side of equation (3) is divided by p.

Statement 3. If the difference of two numbers is divisible by p, then these numbers are comparable modulo p.

Proof. Denote by r and r 1 remainder from division a and b on the p. Then

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 anyone a and p always

comparison is not always necessary

where λ is the greatest common divisor of numbers m and p.

Proof. Let λ largest common divisor numbers m and p. Then

Because m(a−b) divided by k, then

Consequently

and m is one of the divisors of the number p, then

where h=pqs.

Note that we can allow comparisons in negative modules, i.e. comparison a≡b mod( p) means in this case that the difference a−b divided by p. All properties of comparisons remain valid for negative modules.

Definitions

Two integers a and b comparable modulo natural number n (or equidistant when divided by n) if they give the same remainder when divided by n.

Equivalent formulations: a and b comparable modulo n if their difference a - b is divisible by n , or if a can be represented as a = b + kn , where k is some integer. For example: 32 and −10 are congruent modulo 7 because

The statement "a and b are congruent modulo n" is written as:

Modulo Equality Properties

The modulo comparison relation has the properties

Any two integers a and b are comparable modulo 1.

In order for the numbers a and b were comparable modulo n, it is necessary and sufficient that their difference is divisible by n.

If the numbers and are pairwise comparable modulo n, then their sums and , as well as products and are also comparable modulo n.

If numbers a and b comparable modulo n, then their degrees a k and b k are also comparable modulo n for any natural k.

If numbers a and b comparable modulo n, and n divided by m, then a and b comparable modulo m.

In order for the numbers a and b were comparable modulo n, represented as its canonical decomposition into prime factors p i

necessary and sufficient to

The comparison relation is an equivalence relation and has many of the properties of ordinary equalities. For example, they can be added and multiplied: if

Comparisons, however, cannot, generally speaking, be divided by each other or by other numbers. Example: , however, reducing by 2, we get an erroneous comparison: . The reduction rules for comparisons are as follows.

You also cannot perform operations on comparisons if their modules do not match.

Other properties:

Related definitions

Deduction classes

The set of all numbers comparable to a modulo n called deduction class a modulo n , and is usually denoted by [ a] n or . Thus, the comparison is equivalent to the equality of the residue classes [a] n = [b] n .

Because modulo comparison n is an equivalence relation on the set of integers, then the residue classes modulo n are equivalence classes; their number is n. The set of all residue classes modulo n denoted by or .

The operations of addition and multiplication on induce the corresponding operations on the set:

With respect to these operations, the set is a finite ring, and if n simple - 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 n is any set of n integers that are incomparable modulo n. Usually, as a complete system of residues modulo n, one takes the smallest non-negative residues

or absolutely smallest residues consisting of numbers

in case of odd n and numbers

in case of even n .

Comparison decision

Comparisons of the first degree

In number theory, cryptography, and other fields of science, the problem often arises of finding solutions for a comparison of the first degree of the form:

The solution of such a comparison begins with the calculation of the gcd (a, m)=d. In this case, 2 cases are possible:

• If a b not a multiple d, then the comparison has no solutions.
• If a b multiple d, then the comparison has a unique solution modulo m / d, or, which is the same, d modulo solutions m. In this case, as a result of reducing the original comparison by d comparison results:

where a 1 = a / d , b 1 = b / d and m 1 = m / d are integers, and a 1 and m 1 are coprime. Therefore the number a 1 can be inverted modulo m 1 , that is, find such a number c that (in other words, ). Now the solution is found by multiplying the resulting comparison by c:

Practical value calculation c can be done different ways: using Euler's theorem, Euclid's algorithm, the theory of continued fractions (see algorithm), etc. In particular, Euler's theorem allows you to write the value c as:

Example

For comparison, we have 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 3 numbers by 2:

Since 2 is relatively prime to modulo 11, we can reduce the left and right sides by 2. As a result, we get one solution modulo 11: , which is equivalent to two solutions modulo 22: .

Comparisons of the second degree

Solving comparisons of the second degree is reduced to finding out whether a given number is a quadratic residue (using the quadratic law of reciprocity) and then calculating the square root modulo this.

Story

The Chinese remainder theorem, known for many centuries, states (in modern mathematical language) that a residue ring modulo the product of several mutually prime numbers is a direct product of the residue rings corresponding to the factors.

To a large extent, the theory of divisibility and residues was created by Euler. Modulo comparisons were first used by Gauss in his Arithmetical Investigations, 1801. He also proposed the symbolism established in mathematics for comparison.

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 the m, because

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. That's why n ≡ c - b + a - ....(mod11).

Consequently, n is divisible by 11 if and only if the alternating sum of 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. Commonly used complete system residues, consisting of numbers: 0, 1, 2, ..., m-one. subtracting a number n modulo m is the remainder of the division n on the m, which follows from the representation n = km + r, 0<r<m- 1.

If two integers a (\displaystyle a) and b (\displaystyle b) at division on the 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

Consequently,

Because d (\displaystyle d) is divider numbers m (\displaystyle m), then

Consequently,

by definition.

Proof

Consequently,

Since the difference a − b (\displaystyle a-b) is a multiple of each , then it is a multiple of their least common multiple

necessary and sufficient to

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 a 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)):

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:

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:

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:

Examples

Example 1 For comparison

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:

Since 3 is coprime modulo 11, it can be inverted modulo 11 and found

Multiplying the comparison by 4, we get the solution modulo 11:

equivalent to the set of two solutions modulo 22:

Example 2 Given a comparison:

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:

Multiplying both sides of this comparison by 41, we get:

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 the 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:

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.