Comparisons of the first degree. Modulo comparison of a natural number Definition Modulo comparison

At n they give the same remainder.

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, That 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:

[a] n + [b] n = [a + b] n

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

0,1,...,n − 1

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 b not a multiple d, then the comparison has no solutions.
If 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 in 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 comes down to finding out whether a given number is a quadratic residue (using the quadratic reciprocity law) and then calculating the square root modulo this.

Story

The Chinese remainder theorem, known for many centuries, states (in modern mathematical language) that the residue ring modulo the product of several coprime numbers is

Consider the system of comparisons

Where f1(x), f2(x), …. , fs(x)€Z[x].

Theorem 1. Let M = be the least common multiple of numbers m1,m2,…,ms . If a satisfies system (2), then any number from the class a modulo M satisfies this system.

Proof. Let b€ belong to the class a. Since a ≡ b(mod M), then a ≡b(mod m), i= 1,2,...,s (comparison property 16). Therefore, b, like a, satisfies every comparison of the system, which proves the theorem. Therefore, it is natural to consider the class modulo M as a solution to system (2).

Definition. By solving the system of comparisons(2) is the class of numbers modulo M = satisfying each comparison of the system.

12. We note right away that odd numbers do not satisfy the second comparison. Taking even numbers from the complete system of residues modulo 12, by direct verification we make sure that the numbers 2, -2, 6 satisfy the 2nd comparison, and the system has two solutions: x ≡ 2(mod l2), x ≡ -2(mod 12 ).

Consider the system of comparisons of the 1st degree (3)

Theorem 2. Let d=(m1,m2), M = .

If c1 - c2 is not divisible by d, then system (3) has no solutions.

If (c1 -c2):d, then system (3) has one solution - the class modulo M.

Proof. From the 1st comparison x = c1+m1t, t€Z. Substitute into the 2nd comparison: с1+ m1t ≡ c2(mod m2) or

m1t ≡ c2-cl (mod m2). This comparison has a solution only if (c2 - c1): d.

And the solution is a class modulo (Theorem 4 of §2).

Let the solution , i.e. , where k€Z.

M== , i.e. x≡c1+m1t0(mod M) is the solution

Examples.

1.:2, the system has one solution class modulo 24. From the 1st comparison x =2+6t. Substituting instead of x in the 2nd comparison, we have: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t≡2(mod8); t≡-1(mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, i.e. x≡-4(mod 24).

2. 7-3 is not divisible by 3, the system has no solutions.

Consequence 1. Comparison system (4)

Either it has no solutions, or it has one solution – the class modulo M=.

Proof. If the system of the first two comparisons has no solutions, then (4) has no solutions either. If it has a solution x ≡ a(mod), then, adding to this comparison the third comparison of the system, we again obtain a system of the form (3), which either has one solution or has no solutions. If it has a solution, then we continue in this way until we exhaust all comparisons of system (4). If there is a solution, then it is a class modulo M.

Comment. The LCM property is used here: =.

Consequence 2. If m1,m2,…,ms are pairwise coprime, then system (4) has one solution - the class modulo M=m1m2…ms.

Example:

Since the modules are pairwise coprime, the system has one solution - the modulo class 105 = 5*3*7. From the first comparison

Substitute in the second comparison: 2 +5t≡ 0(mod 3) or 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k. Substitute in the third comparison:

3+15k≡5(mod7), 15k≡8(mod 7), k=1+7l. then x=-3+15(1+7l); x=12+105l; x≡12(mod 105).

Let's get acquainted with others way to solve this system, (We use the fact that the system has one solution.) Let's multiply both parts and the modulus of the first comparison by 21, the second by 35b of the third by 15: subtract the second from the sum of the first and third:

(36 -35)x ≡ 75 + 42(modl05); x≡117(mod105); x≡12(mod105).

Let us now consider a system of comparisons of the first degree of a general form

If some comparison of this system has no solutions, then the system has no solutions. If each comparison of system (5) is solvable, then we solve it for x and obtain an equivalent system of the form (4):

Where (Theorem 4, §2).

By Corollary 1, the system either has no solutions or has one solution.

Example:

Solving each comparison of the system, we obtain an equivalent system

This system has one solution - the class modulo 105. Multiplying the first comparison and the modulus by 3, and the second by 35, we get

Subtracting from the second comparison the first multiplied by 11, we get 2x ≡-62(modl05), whence x ≡ -31(modl05).

Problems that boil down to consideration of the system of comparisons of the 1st degree were considered in the arithmetic of the Chinese mathematician Sun Tzu, who lived around the beginning of our era. His question was posed in the following form - to find a number that gives the given remainders when divided by given numbers. It also gives a way of solving that is equivalent to the following theorem.

Theorem (Chinese remainder theorem). Let m1,m2,…,ms be pairwise coprime numbers, M = mlm2...ms, β1, β2,…, βs are chosen so that

Then the solution to the system

It will look like x≡x0(mod M).

Proof. Since we get x0≡

Similarly, we check that x0≡c2(mod m2),…, x0≡cs(mod ms), that is, x0 satisfies all

system comparisons.

10. Comparisons of the 1st degree. Indefinite Equations

§ 2. Comparisons of the 1st degree. Indefinite Equations

Comparison of the 1st degree can be reduced to the form ax≡b(mod m).

Theorem 4. If (a,m) = 1, then the comparison ax ≡b(mod m) (2) has a unique solution.

Proof. Let's take 0,1,2,...,m-1 - the complete system of residues modulo m. Since (а, m) = 1, then 0,а,2а,...,(m-1)а is also a complete system of residues (Theorem 3, §2, Ch. 2.). It contains one and only one number congruent to b modulo m (belonging to the same class as b). Let it be ax 0 , i.e. ax 0 € class b or ax 0 ≡b(mod m). x ≡x 0 (mod m) is the only solution to (2). The theorem has been proven.

Theorem 5. If (a, m)= 1, then the solution of the comparison ax≡b(mod m) is the class x 0 ≡a φ (m)-1 b(mod m).

Proof. Since (a,m) = 1, then by the Euler time a φ(m) ≡1(mod m). It is easy to see that x 0 ≡a φ (m)-1 b (mod m) is the solution of comparison (2). Indeed, a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). It follows from Theorem 4 that this solution is unique.

Consider comparison decision methods ax ≡b(mod m).

1. Selection method. Taking a complete system of residues modulo m, we choose numbers that satisfy the comparison.

2. Use of the Euler theorem (Theorem 5).

3. Coefficient conversion method. We must try to transform the coefficients so that the right side can be divided by the coefficient at x. The transformations in question are as follows: replacing the coefficients with absolutely smallest residues, replacing the number b with a number comparable in absolute value (by adding a number that is a multiple of the modulus) so that the latter is divisible by a, moving from a and b to other numbers comparable with them , which would have a common divisor, and so on. In doing so, we use the properties of congruences and the theorems on equivalent comparisons based on them.

1) 223x ≡ 115(modll).

First, we replace the coefficients with the least absolute residues: Зх ≡ 5(mod 11). If we use the theorem

Euler, then

x≡3 φ(11)-1 *5=3 9 *5≡(3 3) 3 *5≡(27) 3 *5≡5 3 *5≡125*5≡4*5≡9(modll).

However, it is easier to convert the coefficients. Let's replace the comparison with an equivalent one by adding a multiple of the modulus to the right side:

3x ≡ 5 + 22(mod 11). Dividing both parts by a number 3 coprime with the modulus, we get x ≡ 9(mod l1).

2) 111x≡ 8(mod 34).

We use the coefficient conversion method.

(111-3*34)x≡8(mod 34), 9x≡8+34≡42(mod 34), 3x≡14(mod 34), 3x≡14+34≡48(mod 34), x≡16 (mod 34).

Theorem 6. If (a, m) = d and b is not divisible by d, then congruence (1) has no solutions.

Proof (by contradiction). Let the class x 0 be a solution, that is, ax 0 ≡b (mod m) or (ax 0 -b):m, and, therefore, (ax 0 -b):d. But a:d, then b:d is a contradiction. Therefore, the comparison has no solutions.

Theorem 7. If (a,m)= d, d>1, b:d, then comparison(1) has d

solutions that make up one class of modulo residues and are found by the formulas

Where With satisfies an auxiliary comparison

Comment. According to the theorem, comparison (1) is solved as follows.

1) After making sure that (a,m) = d, d> 1 and b:d, we divide both parts in comparison (2) by d and get an auxiliary comparison a 1 x≡b 1 (mod m 1) , where . The comparison has only one solution. Let class c be the solution.

2) Write down the answer x 0 ≡c(mod m), x 1 ≡c+m 1 (mod m), x 2 ≡c+2m 1 (mod m), … , x d -1 ≡c+(d-1)m 1 (mod m).

Proof. The auxiliary comparison by Theorem 2(3) is equivalent to the original comparison (2). Since ( 1, Then the auxiliary congruence has a unique solution, the class modulo m 1 = . Let x≡c(mod m 1) be the solution. The class of numbers c modulo m 1 splits into d classes modulo m: .

Indeed, any number from the class x0 modulo m 1 has the form x 0 +m 1 t. Divide t with remainder by d: t = dq +r, where 0≤r

So, comparison (1) has d solutions modulo m: x0, x0+m1,..., x0 +(d-1)m1. (Horizontal dashes above)

Examples.

1) 20x≡ 15(mod 108). Since (20,108) = 4 and 15 is not divisible by 4, there are no solutions.

2) 20x≡ 44(mod 108). (20,108) = 4 and 44:4, so the comparison has four solutions. Dividing both parts and the modulus by 4, we get:

5x≡11(mod 27); 5 x≡11-81 ≡ -70(mod27), x ≡ -14 ≡ 13(mod 27). Then x≡13 + 27r(mod 108), where r= 0.1,2.3. I jj

Answer: x≡13(modl08); x ≡ 40(modl08); x ≡ 67(modl08); x≡94(modl08).

Application of the theory of comparisons to the solution of indefinite equations

Consider an indefinite or, as it is otherwise called, Diophantine equation of the first degree with two unknowns ax + by = c, where a, b, c € Z. It is required to solve this equation in integers. If (a,b)=d and c is not divisible by d, then it is obvious that the comparison has no solutions in integers. If c is divisible by d, then we divide both sides of the equation by d. Therefore, it suffices to consider the case when (a, b) =1.

Since ax differs from c by a multiple of b, then ax ≡ c(mod b) (without loss of generality, we can assume that b > 0). Solving this comparison, we get x ≡x1 (mod b) or x=x1+bt, where t€Z. To determine the corresponding values of y, we have the equation a(x1 + bt) + by = c, whence

Moreover, it is an integer, it is a particular value of the unknown y, corresponding to x1 (it turns out, like x1, with t=0). And the general solution of the equation will take the form of a system of equations x=x1+bt, y=y1-at, where t is any integer.

Note that 1) the equation ax + by = c could be solved by starting with the comparison by ≡ c(mod a), since by differs from c by a multiple of a;

2) it is more convenient to choose as a module smallest of modules a and b.

Example, 50x – 42y= 34.

Divide both sides of the equation by 2.

25x ≡ 17(mod2l); 4x ≡ 17 (mod 21) or 4x ≡ 17-21 ≡ -4 (mod 21).

x ≡ -1 (mod 21), i.e. x=-1+21t, t€Z. Substitute the found x into the equation. 25(-1 + 21t)- 21y= 17; 21y \u003d -42 + 25 * 21t and y \u003d -2 + 25t.

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.

A comparison of the first degree with one unknown has the form:

f(x) 0 (mod m); f(X) = Oh + a n. (1)

Solve Comparison means to find all values of x that satisfy it. Two comparisons that satisfy the same values of x are called equivalent.

If comparison (1) satisfies some x = x 1, then (according to 49) all numbers comparable with x 1 , modulo m: x x 1 (mod m). This whole class of numbers counts as one solution. With this agreement, the following conclusion can be drawn.

66.C alignment (1) will have as many solutions as there are residues of the complete system that satisfies it.

Example. Comparison

6x– 4 0 (mod 8)

among the numbers 0, 1,2, 3, 4, 5, 6, 7 of the complete system of residues modulo 8, two numbers satisfy: X= 2 and X= 6. Therefore, this comparison has two solutions:

x 2 (mod 8), X 6 (mod 8).

Comparison of the first degree by transferring the free term (with the opposite sign) to the right side can be reduced to the form

ax b(mod m). (2)

Consider a comparison that satisfies the condition ( A, m) = 1.

According to 66 our comparison has as many solutions as there are residues of the complete system that satisfies it. But when x runs through the complete system of residues modulo T, That Oh runs through the full system of deductions (out of 60). Therefore, for one and only one value X, taken from the complete system, Oh will be comparable to b. So,

67. For (a, m) = 1 comparison ax b(mod m)has one solution.

Let now ( a, m) = d> 1. Then, for comparison (2) to have solutions, it is necessary (out of 55) that b divided into d, otherwise comparison (2) is impossible for any integer x . Assuming therefore b multiple d, let's put a = a 1 d, b = b 1 d, m = m 1 d. Then comparison (2) will be equivalent to this (reduced by d): a 1 x b 1 (mod m), in which already ( A 1 , m 1) = 1, and therefore it will have one solution modulo m 1 . Let X 1 is the smallest non-negative residue of this solution modulo m 1 , then all numbers x , forming this solution can be found in the form

x x 1 (mod m 1). (3)

Modulo, the numbers (3) form not one solution, but more, exactly as many solutions as there are numbers (3) in the series 0, 1, 2, ..., m 1 least non-negative residue modulo m. But the following numbers will fall here (3):

x 1 , x 1 + m 1 , x 1 + 2m 1 , ..., x 1 + (d – 1) m 1 ,

those. Total d numbers (3); hence comparison (2) has d solutions.

We get the theorem:

68. Let (a, m) = d. comparison ax b ( mod m) impossible if b is not divisible by d. When b is a multiple of d, the comparison has d solutions..

69. Method for solving comparison of the first degree, based on the theory of continued fractions:

Expanding into a continued fraction the ratio m:a,

and considering the last two convergents:

according to the properties of continued fractions (according to 30 ) we have

So the comparison has a solution

for the search, which is enough to calculate P n- 1 according to the method specified in 30.

Example. Let's solve the comparison

111x= 75 (mod 321). (4)

Here (111, 321) = 3, and 75 is a multiple of 3. Therefore, the comparison has three solutions.

Dividing both parts of the comparison and the modulus by 3, we get the comparison

37x= 25 (mod 107), (5)

which we need to decide first. We have

q
P 3

So, in this case n = 4, P n - 1 = 26, b= 25, and we have the solution of comparison (5) in the form

x–26 ∙ 25 99 (mod 107).

Hence, the solutions of comparison (4) are presented as follows:

X 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),

Xº99; 206; 313 (mod 321).

Calculation of the inverse element modulo a given

70.If integers a And n coprime, then there is a number a′, satisfying the comparison a ∙ a′ ≡ 1(mod n). Number a′ called multiplicative inverse of a modulo n and the notation is used for it a- 1 (mod n).

Calculating reciprocals modulo some can be done by first-degree comparison solution with one unknown, in which x accepted number a′.

To find a comparison solution

a x≡ 1(mod m),

Where ( a,m)= 1,

one can use the Euclid algorithm (69) or the Fermat-Euler theorem, which states that if ( a,m) = 1, then

a φ( m) ≡ 1(mod m).

x ≡ a φ( m)–1 (mod m).

Groups and their properties

Groups are one of the taxonomic classes used in the classification of mathematical structures with common characteristic properties. Groups have two components: a bunch of (G) And operations() defined on this set.

The concepts of set, element and membership are the basic undefined concepts of modern mathematics. Any set is defined by the elements included in it (which, in turn, can also be sets). Thus, we say that a set is defined or given if for any element we can say whether it belongs to this set or not.

For two sets A, B records B A, B A, B∩ A, B A, B \ A, A × B mean, respectively, that B is a subset of the set A(i.e. any element from B is also contained in A, for example, the set of natural numbers is contained in the set of real numbers; besides, always A A), B is a proper subset of the set A(those. B A And B ≠ A), intersection of many B And A(i.e. all such elements that lie simultaneously and in A, and in B, for example, the intersection of integers and positive real numbers is the set of natural numbers), the union of sets B And A(i.e. a set consisting of elements that lie either in A, either in B), set difference B And A(i.e. the set of elements that lie in B, but do not lie in A), the Cartesian product of sets A And B(i.e., a set of pairs of the form ( a, b), Where a A, b B). Through | A| the cardinality of the set is always denoted A, i.e. number of elements in the set A.