Comparisons on the simple and composite module. Comparison decision

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.

Two integers a and b are comparable modulo a natural number m є N if, when divided by m, they give the same remainder. .

Theorem (comparability criterion): . Corollary 1: each number is congruent modulo m with its remainder modulo m: . Corollary 2: a number is congruent modulo m, m. and so. m., since it is divisible by this mod.

Basic comparison properties: 1). Relative comparisons are relatively equivalent. 2). Comparisons in the same modulo can be subtracted term by term: . The term can be transferred from one part to another, while the sign is reversed. 3). In each part of the comparison, you can add any number that is a multiple of the modulus: comparisons by the same modulo can be multiplied term by term. Consequences: 1. Both parts of the comparison can be raised to any natural power. 2. Both parts of the comparison can be multiplied by any natural number. four). Both parts of the comparison and the modulus can be multiplied by the same number or reduced by any of their common divisors. five). If the comparison takes place in several modules, then it also takes place in the modulo, which is equal to their greatest multiple or greatest common divisor

6). If the comparison takes place modulo m, then it also takes place modulo m

divisor of m. 7). The common divisor of one part of the comparison and the modulus is the divisor of the other part of the comparison: , .

Fermat's Little Theorem: if a and m are coprime numbers, then . The Euler function is the number of positive numbers not exceeding n and coprime to n. If an integer a is coprime with m, then . Euler's theorem: if an integer a is coprime with m, then . Fermat's theorem: 1. If an integer a does not divide p, where p is prime, then . 2. If p is prime and a is any integer, then . Comparability relation are equivalence classes. Equivalence classes are also called residue classes, and their equivalences are called residues.

Comparison solution: Let , , mєN. Then it is called a k-power comparison with one unknown and has at most m solution classes. The solutions of this comparison will be the residue classes modulo m. Comparisons of the first degree with one unknown can be written as: if: 1). this comparison has no solution (e.g. 5x ). 2). If the decision of this comparison. 3). .

Theorem: Let , , then , d be solution classes mod m. Methods for solving comparisons: 1). Method for testing a complete system of deductions. 2). Coefficient conversion method. Any number that is a multiple of the modulus is added or subtracted from the right side, replacing the coefficients on the left side with the number of comparisons with the modulus. It is possible to transform comparisons so that it can be reduced by a and get a solution.

Comparing numbers modulo

Project prepared by: Irina Zutikova

MAOU "Lyceum №6"

Class: 10 "a"

Scientific adviser: Zheltova Olga Nikolaevna

Tambov

2016

  • Problem
  • Objective of the project
  • Hypothesis
  • Project objectives and plan to achieve them
  • Comparisons and their properties
  • Examples of tasks and their solutions
  • Used sites and literature

Problem:

Most students rarely use modulo comparison of numbers for solving non-standard and Olympiad tasks.

Objective of the project:

Show how, by comparing numbers modulo, you can solve non-standard and Olympiad tasks.

Hypothesis:

A deeper study of the topic "Modulo comparison of numbers" will help students solve some non-standard and Olympiad tasks.

Project objectives and plan to achieve them:

1. Study in detail the topic "Comparison of numbers modulo".

2. Solve several non-standard and Olympiad tasks using modulo comparison of numbers.

3.Create a memo for students on the topic "Comparison of numbers modulo".

4. Conduct a lesson on the topic "Modulo comparison of numbers" in class 10 "a".

5. Give the class homework on the topic "Modulo Comparison".

6. Compare the task completion time before and after studying the topic "Modulo Comparison".

7. Draw conclusions.

Before starting to study the topic “Comparing numbers modulo” in detail, I decided to compare how it is presented in various textbooks.

  • Algebra and beginning of mathematical analysis. Deep level. Grade 10 (Yu.M. Kolyagin and others)
  • Mathematics: algebra, functions, data analysis. Grade 7 (L.G. Peterson and others)
  • Algebra and beginning of mathematical analysis. profile level. Grade 10 (E.P. Nelin and others)
  • Algebra and beginning of mathematical analysis. profile level. Grade 10 (G.K. Muravin and others)

As I found out, in some textbooks this topic is not even touched upon, despite the in-depth level. And the most understandable and accessible topic is presented in the textbook by L.G. Peterson (Chapter: Introduction to the theory of divisibility), so let's try to understand the "Comparison of numbers modulo", based on the theory from this textbook.

Comparisons and their properties.

Definition: If two integers a and b have the same remainder when divided by some integer m (m>0), then they say thata and b are congruent modulo m, and write:

Theorem: if and only if the difference between a and b is divisible by m.

Properties:

  1. Reflexivity of comparisons.Any number a is comparable to itself modulo m (m>0; a,m are integers).
  2. Symmetry of comparisons.If the number a is congruent with the number b modulo m, then the number b is congruent with the number a modulo m (m>0; a,b,m are integers).
  3. Transitivity of comparisons.If a number a is congruent to b modulo m, and b is congruent to c modulo m, then a is congruent to c modulo m(m>0; a,b,c,m are integers).
  4. If the number a is congruent to the number b modulo m, then the number a n comparable to the number b n modulo m(m>0; a,b,m are integers; n is a natural number).

Examples of tasks and their solutions.

1.Find the last digit of the number 3 999 .

Decision:

Because the last digit of the number is the remainder of the division by 10, then

3 999 =3 3 *3 996 =3 3 *(3 4 ) 249 =7*81 249 7(mod 10)

(Because 34=81 1(mod 10);81 n 1(mod10) (by property))

Answer:7.

2. Prove that 2 4n -1 is divisible by 15 without a remainder. (Phystech2012)

Decision:

Because 16 1(mod 15), then

16n-1 0(mod 15) (by property); 16n= (2 4) n

2 4n -1 0(mod 15)

3.Prove that 12 2n+1 +11n+2 divisible without remainder by 133.

Decision:

12 2n+1 =12*144n 12*11n (mod 133) (by property)

12 2n+1 +11 n+2 =12*11 n +11 n *121=11 n *(12+121) =11 n *133

Number (11n *133) is divisible by 133 without remainder. Therefore, (12 2n+1 +11n+2 ) is divisible by 133 without a remainder.

4. Find the remainder of the division by 15 of the number 2 2015 .

Decision:

Since 16 1(mod 15), then

2 2015 8(mod 15)

Answer: 8.

5. Find the remainder of the division by 17 of the number 2 2015 . (Phystech 2015)

Decision:

2 2015 =2 3 *2 2012 =8*16 503

Since 16 -1(mod 17), then

2 2015-8(mod 15)

8 9(mod 17)

Answer:9.

6.Prove that the number is 11 100 -1 is divisible by 100 without a remainder. (Phystech 2015)

Decision:

11 100 =121 50

121 50 21 50 (mod 100) (by property)

21 50 =441 25

441 25 41 25 (mod 100) (by property)

41 25 =41*1681 12

1681 12 (-19) 12 (mod 100) (by property)

41*(-19) 12 =41*361 6

361 6 (-39) 6 (mod 100)(by property)

41*(-39) 6 =41*1521 3

1521 3 21 3 (mod100) (by property)

41*21 3 =41*21*441

441 41(mod 100) (by property)

21*41 2 =21*1681

1681 -19(mod 100) (by property)

21*(-19)=-399

399 1(mod 100) (by property)

So 11 100 1(mod 100)

11 100 -1 0(mod 100) (by property)

7. Three numbers are given: 1771,1935,2222. Find the number that when divided by which the remainder of the three given numbers will be equal. (HSE2016)

Decision:

Let the unknown number be equal to a, then

2222 1935(mod a); 1935 1771(mod a); 2222 1771(mod a)

2222-1935 0(moda) (property); 1935-17710(moda) (by property); 2222-17710(moda) (by property)

287 0(mod a); 164 0(mod a); 451 0(mod a)

287-164 0(moda) (by property); 451-2870(moda)(by property)

123 0(mod a); 164 0(mod a)

164-123 0(mod a) (property)

41

  • HSE Olympiad2016

    • Consider comparisons of the first degree of the form

    ax≡ b(mod m),

    How to solve such a comparison? Let's consider two cases.

    Case 1 Let a and m mutually simple. Then the irreducible fraction m/a she herself asks to expand into a continued fraction:

    This continued fraction is, of course, finite, since m/a is a rational number. Consider its last two convergent fractions:

    We recall an important property of numerators and denominators of suitable fractions: mQ n-1 -aP n-1 =(-1) n. Further (term mQ n-1, multiple m, can be thrown out from the left side

    comparisons):

    -aP n-1≡ (-1) n (mod m) those.

    aP n-1≡ (-1) n-1 (mod m) those.

    a[(-1) n-1 P n-1 b]≡ b(mod m)

    and the only solution to the original comparison is:

    x ≡ (-1) n-1 P n-1 b(mod m)

    Example. Solve comparison 111x ≡ 75(mod 322).

    Decision.(111, 322)=1. Turn on the Euclid algorithm:

    322=111 2+100

    (Incomplete quotients are underlined in equalities.) Hence, n=4, and the corresponding chain

    the fraction is:

    Let's calculate the numerators of suitable fractions by compiling a standard table for this:

    The numerator of the penultimate convergent is 29, therefore, the finished formula

    gives the answer: x≡ (-1) 3 ⋅ 29 ⋅ 75 ≡ -2175 ≡ 79(mod 322)

    Case 2 Let (a,m)=d. In this case, for the comparison to be resolvable ax≡ b(mod m)

    it is necessary that d divided b, otherwise the comparison cannot be performed at all.

    Really, ax≡ b(mod m) happens when, and only when ax-b divided by m completely, i.e.

    ax-b=t m, t∈ Z, whence b=ax-t⋅ m, and the right side of the last equality is a multiple of d.

    Let b=db 1, a=da1, m=dm 1. Then both sides of the comparison xa 1 d≡ b 1 d(mod m 1 d) and divide its modulus by d:

    xa 1≡ b 1 (mod m 1),

    where already a 1 and m 1 mutually simple. According to case 1 of this subsection, such a comparison has a unique solution x0:

    x≡ x 0 (mod m 1)(*)

    According to the original module m, the numbers (*) form as many solutions of the original comparison as there are numbers of the form (*) in the complete system of residues: 0,1,2,..., m-2, m-1. Obviously, from the numbers x = x0 + t⋅m only x 0 , x 0 + m 1 , x 0 +2m 1 , ..., x 0 +(d-1)m 1, i.e. Total d numbers. So the original comparison has d decisions.

    We summarize the considered cases in the form of the following theorem

    Theorem 1. Let (a,m)=d. If b not divisible by d, comparison ax≡ b(mod m) has no solutions. If b multiple d, comparison ax≡ b(mod m) It has d pieces of solutions.



    Example. Solve Comparison 111x≡ 75(mod 321).

    Decision.(111,321)=3 , so we divide the comparison and its modulus by 3:

    37x≡ 25(mod 107) and already (37,107)=1 .

    We turn on the Euclid algorithm (as usual, incomplete quotients are underlined):

    We have n=4 and the continued fraction is:

    Table for finding the numerators of suitable fractions:

    Means, x≡ (-1) 3 ⋅ 26 ⋅ 25 ≡ -650(mod 107)≡ -8(mod 107)≡ 99(mod 107).

    Three solutions to the original comparison:

    x≡ 99(mod 321), x≡ 206(mod 321), x≡ 313(mod 321),

    and there are no other solutions.

    Theorem 2. Let m>1, (a,m)=1 Then comparison ax≡ b(mod m) has a solution: x≡ ba ϕ (m)-1 (mod m).

    Example. Solve Comparison 7x≡ 3(mod 10). We calculate:

    ϕ (10)=4; x≡ 3 ⋅ 7 4-1 (mod 10)≡ 1029(mod 10)≡ 9(mod 10).

    It can be seen that this method of solving comparisons is good (in the sense of a minimum of intellectual costs for its implementation), but may require the construction of a number a to a fairly large extent, which is quite laborious. To get a feel for this, raise the number 24789 to the power of 46728 yourself.

    Theorem 3. Let R- Prime number, 0 Then comparison ax≡ b(modp) has a solution:

    where is the binomial coefficient.

    Example. Solve Comparison 7x≡ 2(mod 11). We calculate:

    Lemma 1 (Chinese remainder theorem). Let the simplest system of comparisons of the first degree be given:

    where m 1 ,m 2 ,...,m k are pairwise coprime. Let, further, m 1 m 2 ...m k =M s m s; Ms Ms ∇ ≡ 1(mod m s)(Obviously, what is the number Ms∇ can always be chosen using at least the Euclidean algorithm, because (m s ,M s)=1); x 0 \u003d M 1 M 1 ∇ b 1 +M 2 M 2 ∇ b 2 +...+M k M k ∇ b k. Then the system (*) is equivalent to one comparison x≡ x 0 (mod m 1 m 2 ...m k), i.e. the set of solutions (*) is the same as the set of comparison solutions x≡ x 0 (mod m 1 m 2 ...m k).

    Example. Once an average friend approached a smart friend and asked him to find a number that when divided by 4 gives a remainder of 1, when divided by 5 gives a remainder of 3, and when divided by 7 gives a remainder of 2. The average friend himself has been looking for such a number for two weeks. A smart comrade immediately compiled a system:

    which he began to solve using Lemma 1. Here is his solution:

    b 1 =1; b2=3; b 3 \u003d 2; m 1 m 2 m 3, i.e. M 1 \u003d 35, M 2 \u003d 28, M 3 \u003d 20.

    those. M1 ∇ =3, M2 ∇ =2, M3∇=6. Means x0=35 ⋅ 3 ⋅ 1+28 ⋅ 2 ⋅ 3+20 ⋅ 6 ⋅ 2=513. After that, by Lemma 1, the smart comrade immediately received the answer:

    x≡ 513(mod 140) ≡ 93(mod 140),

    those. the smallest positive number that the average friend was looking for for two weeks is 93. So the smart friend once again helped the average friend.

    Lemma 2. If b 1 ,b 2 ,...,b k run through complete systems of residues modulo m 1 ,m 2 ,...,m k respectively, then x0 runs through the complete system of residues modulo m 1 m 2 ...m k.

    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), М = .

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