Solving comparisons of the first degree. Solving congruences and their applications Divisibility and modulo comparisons

Content.

Introduction

§1. Modulo comparison

§2. Comparison Properties

1. Module-Independent Comparison Properties
2. Module-Specific Comparison Properties

§3. Deduction system

1. Complete system of deductions
2. The reduced system of deductions

§4. Euler's theorem and Fermat

1. Euler function
2. Euler's theorem and Fermat

Chapter 2. Theory of comparisons with a variable

§1. Basic concepts related to the decision of comparisons

1. The roots of comparisons
2. Equivalence of comparisons
3. Wilson's theorem

§2. Comparisons of the first degree and their solutions

1. Selection method
2. Euler methods
3. Euclid's algorithm method
4. Continued fraction method

§3. Systems of comparisons of the 1st degree with one unknown

§4. Division of comparisons of higher powers

§5. Primitive roots and indices

1. Deduction class order
2. Primitive roots modulo prime
3. Indexes modulo prime

Chapter 3 Application of the theory of comparisons

§1. Signs of divisibility

§2. Checking the results of arithmetic operations

§3. Converting an ordinary fraction to a finite

decimal fraction

Conclusion

Literature

Introduction

In our life we ​​often have to deal with integers and tasks related to them. In this thesis, I consider the theory of comparison of integers.

Two integers whose difference is a multiple of a given natural number m are called comparable modulo m.

The word "module" comes from the Latin modulus, which in Russian means "measure", "value".

The statement "a is congruent to b modulo m" is usually written as ab (mod m) and is called comparison.

The definition of comparison was formulated in the book by K. Gauss "Arithmetic Research". This work, written in Latin, began to be printed in 1797, but the book was published only in 1801 due to the fact that the printing process at that time was extremely laborious and lengthy. The first section of Gauss's book is called "On the Comparison of Numbers in General".

Comparisons are very convenient to use in those cases when it is enough to know in any research numbers up to multiples of a certain number.

For example, if we are interested in what digit the cube of an integer a ends with, then it is enough for us to know a only up to multiples of 10 and we can use comparisons modulo 10.

The purpose of this work is to consider the theory of comparisons and study the main methods for solving comparisons with unknowns, as well as to study the application of the theory of comparisons to school mathematics.

The thesis consists of three chapters, and each chapter is divided into paragraphs, and paragraphs into paragraphs.

The first chapter deals with general questions of the theory of comparisons. Here we consider the concept of modulo comparison, the properties of comparisons, the complete and reduced system of residues, the Euler function, the Euler and Fermat theorem.

The second chapter is devoted to the theory of comparisons with the unknown. It outlines the basic concepts related to the solution of comparisons, considers methods for solving comparisons of the first degree (selection method, Euler's method, Euclid's algorithm method, the method of continued fractions, using indices), systems of comparisons of the first degree with one unknown, comparisons of higher degrees, etc. .

The third chapter contains some applications of number theory to school mathematics. The signs of divisibility, verification of the results of actions, conversion of ordinary fractions into systematic decimal fractions are considered.

The presentation of the theoretical material is accompanied by a large number of examples that reveal the essence of the introduced concepts and definitions.

Chapter 1. General questions of the theory of comparisons

§1. Modulo comparison

Let z-ring of integers, m-fixed integer and m z-set of all integers divisible by m.

Definition 1. Two integers a and b are said to be congruent modulo m if m divides a-b.

If the numbers a and b are comparable modulo m, then write a b (mod m).

Condition a b (mod m) means that a-b is divisible by m.

a b (mod m)↔(a-b) m

We define that the relation of comparability modulo m coincides with the relation of comparability modulo (-m) (divisibility by m is equivalent to divisibility by –m). Therefore, without loss of generality, we can assume that m>0.

Examples.

Theorem. (sign of comparability of spirit numbers modulo m): Two integers a and b are comparable modulo m if and only if a and b have the same remainder when divided by m.

Proof.

Let the remainders when dividing a and b by m be equal, that is, a=mq₁+r,(1)

B=mq₂+r, (2)

Where 0≤r≥m.

Subtract (2) from (1), we get a-b= m(q₁- q₂), i.e. a-b m or a b (mod m).

Conversely, let a b (mod m). This means a-b m or a-b=mt, t z (3)

Divide b by m; we get b=mq+r in (3), we will have a=m(q+t)+r, that is, dividing a by m gives the same remainder as dividing b by m.

Examples.

5=4 (-2)+3

23=4 5+3

24=3 8+0

10=3 3+1

Definition 2. Two or more numbers that give the same remainder when divided by m are called equidistant or comparable modulo m.

Examples.

We have: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², and (- m²) is divisible by m => our comparison is correct.

1. Prove that the following comparisons are false:

If the numbers are comparable modulo m, then they have the same gcd with it.

We have: 4=2 2, 10=2 5, 25=5 5

gcd(4,10) = 2, gcd(25,10) = 5, so our comparison is wrong.

§2. Comparison Properties

1. Module-independent comparison properties.

Many properties of comparisons are similar to those of equalities.

a) reflexivity: aa (mod m) (any integer a is comparable to itself modulo m);

C) symmetry: if a b (mod m), then b a (mod m);

C) transitivity: if a b (mod m), and b with (mod m), then a with (mod m).

Proof.

By condition m/(a-b) and m/ (c-d). Therefore, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b + d (mod m).

Examples.

Find remainder when dividing at 13.

Solution: -1 (mod 13) and 1 (mod 13), then (-1)+1 0 (mod 13), that is, the remainder of the division by 13 is 0.

a-c b-d (mod m).

Proof.

By condition m/(a-b) and m/(c-d). Therefore, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

1. (a consequence of properties 1, 2, 3). You can add the same integer to both parts of the comparison.

Proof.

Let a b (mod m) and k is any integer. By the property of reflexivity

k=k (mod m), and according to properties 2 and 3 we have a+k b + k (mod m).

a c d (mod m).

Proof.

By condition, a-b є mz, c-d є mz. Hence a c-b d = (a c - b c)+(b c- b d)=(a-b) c+b (c-d) є mz, i.e. a c d (mod m).

Consequence. Both parts of the comparison can be raised to the same integer non-negative power: if ab (mod m) and s is a non-negative integer, then a s b s (mod m).

Examples.

Solution: obviously 13 1 (mod 3)

2-1 (mod 3)

5 -1 (mod 3), then

- 1-1 0 (mod 13)

Answer: the desired remainder is zero, and A is divisible by 3.

Solution:

Let us prove that 1+ 0(mod13) or 1+ 0(mod 13)

1+ =1+ 1+ =

Since 27 is 1 (mod 13), it follows that 1+ 1+1 3+1 9 (mod 13).

h.t.d.

3. Find the remainder when dividing with the remainder of a number at 24.

We have: 1 (mod 24), so

1 (mod 24)

Adding 55 to both parts of the comparison, we get:

(mod 24).

We have: (mod 24), so

(mod 24) for any k є N.

Hence (mod 24). Since (-8)16(mod 24), the desired remainder is 16.

1. Both parts of the comparison can be multiplied by the same integer.

2.Properties of comparisons depending on the module.

Proof.

Since a b (mod t), then (a - b) t. And since t n , then due to the transitivity of the divisibility relation(a - b n) , that is, a b (mod n).

Example.

Find the remainder after dividing 196 by 7.

Solution:

Knowing that 196= , we can write 196(mod 14). Let's use the previous property, 14 7, we get 196 (mod 7), that is, 196 7.

1. Both parts of the comparison and the modulus can be multiplied by the same positive integer.

Proof.

Let a b (mod m ) and c is a positive integer. Then a-b = mt and ac-bc=mtc, or ac bc (mod mc).

Example.

Check if the value of an expression is whole number.

Solution:

Let's represent fractions in the form of comparisons: 4(mod 3)

1 (mod 9)

31 (mod 27)

We add these comparisons term by term (property 2), we get 124(mod 27) We see that 124 is not an integer divisible by 27, hence the value of the expressionis also not an integer.

1. Both parts of the comparison can be divided by their common factor if it is relatively prime to the modulus.

Proof.

If ca cb (mod m), i.e. m/c(a-b) and number With coprime to m, (c,m)=1, then m divides a-b. Hence, a b (mod t ).

Example.

60 9 (mod 17), after dividing both parts of the comparison by 3 we get:

20 (mod 17).

Generally speaking, it is impossible to divide both parts of the comparison by a number that is not coprime with the modulus, since after division, numbers can be obtained that are incomparable in this modulus.

Example.

8 (mod 4) but 2 (mod 4).

1. Both parts of the comparison and the modulus can be divided by their common divisor.

Proof.

If ka kb (mod km), then k (a-b) is divisible by km. Therefore, a-b is divisible by m, that is a b (mod t ).

Proof.

Let P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n . By condition a b (mod t), then

a k b k (mod m) for k = 0, 1, 2, …,n. Multiplying both parts of each of the resulting n + 1 comparisons by c n-k , we get:

c n-k a k c n-k b k (mod m), where k = 0, 1, 2, …,n.

Adding the last comparisons, we get: P (a) P(b) (mod m). If a (mod m) and c i d i (mod m), 0 ≤ i ≤ n, then

(mod m). Thus, in congruence modulo m, individual terms and factors can be replaced by numbers congruent modulo m.

At the same time, attention should be paid to the fact that the exponents encountered in comparisons cannot be replaced in this way: from

a n c(mod m) and n k(mod m) does not imply that a k with (mod m).

Property 11 has a number of important applications. In particular, it can be used to give a theoretical substantiation of the signs of divisibility. For illustration, as an example, we will give the derivation of the test for divisibility by 3.

Example.

Any natural number N can be represented as a systematic number: N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n .

Consider the polynomial f (x) = a 0 x n + a 1 x n-1 + ... + a n-1 x+a n . Because

10 1 (mod 3), then by property 10 f (10) f(1) (mod 3) or

N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n a 1 + a 2 +…+ a n-1 + a n (mod 3), i.e., for N to be divisible by 3, it is necessary and sufficient that the sum of the digits of this number is divisible by 3.

§3. Deduction systems

1. Complete billing system.

Equidistant numbers, or, what is the same, comparable modulo m, form a class of numbers modulo m.

It follows from this definition that the same remainder r corresponds to all numbers of the class, and we get all numbers of the class if we force q to run through all integers in the form mq + r.

Accordingly, with m different values ​​of r, we have m classes of numbers modulo m.

Any number of a class is called a residue modulo m with respect to all numbers of the same class. The residue obtained at q=0, equal to the remainder r, is called the smallest non-negative residue.

The residue ρ, the smallest in absolute value, is called the absolutely smallest residue.

Obviously, for r we have ρ=r; when r> we have ρ=r-m; finally, if m is even and r=, then for ρ one can take any of the two numbers and -m= - .

We choose from each class of residues modulo T by one number. Get m integers: x 1 ,…, x m . The set (x 1, ..., x t) is called complete system of residues modulo m.

Since each class contains an uncountable set of residues, it is possible to compose an uncountable set of different complete systems of residues modulo m, each of which contains t deductions.

Example.

Compose several complete systems of residues modulo T = 5. We have classes: 0, 1, 2, 3, 4.

0 = {... -10, -5,0, 5, 10,…}

1= {... -9, -4, 1, 6, 11,…}

Let's make several complete systems of deductions, taking one deduction from each class:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

10, -9, -8, -7, -6

5, -4, -3, -2, -1

etc.

Most used:

1. Complete system of least non-negative residues: 0, 1, t -1 In the example above: 0, 1, 2, 3, 4. Such a system of residues is simple: you need to write down all non-negative remainders resulting from division by m.
2. Complete system of least positive residues(the smallest positive deduction is taken from each class):

1, 2, …,m. In our example: 1, 2, 3, 4, 5.

1. A complete system of absolutely least residues.In the case of odd m, the absolute smallest residues appear side by side.

- ,…, -1, 0, 1,…, ,

and in the case of an even m, one of the two rows

1, …, -1, 0, 1,…, ,

, …, -1, 0, 1, …, .

In the example given: -2, -1, 0, 1, 2.

Let us now consider the main properties of the complete system of residues.

Theorem 1 . Any set of m integers:

x l ,x 2 ,…,х m (1)

pairwise incomparable modulo m, forms a complete system of residues modulo m.

Proof.

1. Each of the numbers in the set (1) belongs to some class.
2. Any two numbers x i and x j from (1) are incomparable with each other, i.e., they belong to different classes.
3. In total, there are m numbers in (1), i.e., as many as there are classes modulo T.

x 1, x 2,…, x t is a complete system of residues modulo m.

Theorem 2. Let (a, m) = 1, b - arbitrary integer; then if x 1, x 2,…, x t -complete system of residues modulo m, then the set of numbers ax 1 + b, ax 2 + b,…, ax m + b is also a complete system of residues modulo m.

Proof.

Consider

Ax 1 + b, ax 2 + b, ..., ax m + b (2)

1. Each of the numbers in the set (2) belongs to some class.
2. Any two numbers ax i +b and ax j + b from (2) are incomparable with each other, that is, they belong to different classes.

Indeed, if there were two numbers in (2) such that

ax i + b ax j + b (mod m), (i = j), then we would get ax i ax j (mod m). Since (a, t) = 1, then the property of comparisons can reduce both parts of the comparison by A . We get x i x j (mod m).

By condition, x i x j (mod m) for (i = j) , since x 1 ,x 2 , ..., x m - full system of deductions.

1. The set of numbers (2) contains T numbers, that is, as many as there are classes modulo m.

So, ax 1 + b, ax 2 + b, ..., ax m + b is the complete system of residues modulo m.

Example.

Let m = 10, a = 3, b = 4.

Let's take some complete system of residues modulo 10, for example: 0, 1, 2, ..., 9. Let's compose numbers of the form ax + b. We get: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. The resulting set of numbers is a complete system of residues modulo 10.

1. The given system of deductions.

Let us prove the following theorem.

Theorem 1.

Numbers of the same residue class modulo m have the same greatest common divisor with m: if a b (mod m), then (a, m) = (b, m).

Proof.

Let a b (mod m). Then a = b + mt, where t z. From this equality it follows that (a, m) = (b, m).

Indeed, let the δ-common divisor of a and m, then aδ, m δ. Since a = b + mt, then b=a-mt, hence bδ. Therefore, any common divisor of a and m is a common divisor of m and b.

Conversely, if m δ and b δ, then a = b + mt is divisible by δ, and therefore any common divisor of m and b is a common divisor of a and m. The theorem has been proven.

Definition 1. Greatest Common Divisor of a Modulus t and any number a from this class of deductions for T called the greatest common divisor T and this class of residues.

Definition 2. Residue class a modulo m is called coprime with modulo m if the greatest common divisor a and t equals 1 (that is, if m and any number from a are coprime).

Example.

Let t = 6. Residue class 2 consists of numbers (..., -10, -4, 2, 8, 14, ...). The greatest common divisor of any of these numbers and module 6 is 2. Hence, (2, 6) = 2. The greatest common divisor of any number from class 5 and module 6 is 1. Hence, class 5 is relatively prime to module 6.

Let us choose from each class of residues coprime with modulo m one number. We obtain a system of deductions, which is part of the complete system of deductions. They call herreduced system of residues modulo m.

Definition 3. The set of residues modulo m, taken one at a time from each coprime with T class of residues modulo this module is called a reduced residue system.

Definition 3 implies a method for obtaining a reduced system of residues modulo T: it is necessary to write out some complete system of residues and remove from it all residues that are not coprime with m. The remaining set of deductions is the reduced system of deductions. There are obviously an infinite number of reduced systems of residues modulo m.

If we take the complete system of the least non-negative or absolutely least residues as the initial one, then in the indicated way we obtain the respectively reduced system of the least non-negative or absolutely least residues modulo m.

Example.

If T = 8, then 1, 3, 5, 7 - reduced system of least non-negative residues, 1, 3, -3, -1- reduced system of absolutely least residues.

Theorem 2.

Let the number of classes relatively prime to m is equal to k.Then any collection of k integers

pairwise incomparable modulo m and relatively prime to m, is a reduced system of residues modulo m.

Proof

A) Each number in the set (1) belongs to some class.

1. All numbers from (1) are pairwise incomparable modulo T, that is, they belong to different classes modulo m.
2. Each number from (1) is coprime with T, that is, all these numbers belong to different classes coprime with modulus m.
3. In total, (1) has k numbers, that is, as many as the reduced system of residues modulo m should contain.

Therefore, the set of numbers(1) - reduced system of residues modulo T.

§4. Euler function.

Euler's and Fermat's theorems.

1. Euler function.

Denote by φ(T) the number of classes of residues modulo m coprime with m, that is, the number of elements of the reduced system of residues modulo t. Function φ (t) is numeric. They call herEuler function.

We choose as representatives of the residue classes modulo t numbers 1, ... , t - 1, t. Then φ (t) is the number of such numbers coprime with t. In other words, φ (t) - the number of positive numbers not exceeding m and relatively prime to m.

Examples.

1. Let t = 9. The complete system of residues modulo 9 consists of the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9. Of these, the numbers 1,2,4, 5, 7, 8 are coprime from 9. So since the number of these numbers is 6, then φ (9) = 6.
2. Let t = 12. The complete system of residues consists of the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Of these, the numbers 1, 5, 7, 11 are coprime from 12. Hence,

φ(12) = 4.

At t = 1, the complete system of residues consists of one class 1. The common natural divisor of the numbers 1 and 1 is 1, (1, 1) = 1. On this basis, we put φ(1) = 1.

Let's proceed to the calculation of the Euler function.

1) If m = p is a prime number, then φ(p) = p- 1.

Proof.

Residues 1, 2, ... , p- 1 and only they are coprime with a prime number R. Therefore φ (p) = p - 1.

2) If m = p k - power of a prime number p, then

φ(t) = (p - 1) . (1)

Proof.

Complete system of residues modulo t = p k consists of numbers 1,..., p k - 1, p k natural divisors T are degrees R. Therefore the number Amay have a common divisor with m other than 1, only whenAdivided byR.But among the numbers 1, ... , pk -1 onRdividing only numbersp, 2p, ... , p2 , ... RTo, the number of which isRTo: p = pk-1. Hence, coprime witht = pTorestRTo- Rk-1=pkl(p-1)numbers. Thus, it is proved that

φ (RTo) = pk-1(r-1).

Theorem1.

The Euler function is multiplicative, that is, for coprime numbers m and n we have φ (mn) = φ(m) φ (n).

Proof.

The first requirement in the definition of a multiplicative function is fulfilled in a trivial way: the Euler function is defined for all natural numbers, and φ (1) = 1. We only need to show that iftyperelatively prime numbers, then

φ (tp)= φ (T) φ (P).(2)

Arrange the complete system of residues modulotpasPXT -matrices

1 2 T

t+1 t+2 2t

………………………………

(P -1) t+1 (P -1) m +2 Fri

Because theTAndPcoprime, then the numberXmutually simple withtpif and only ifXmutually simple withTAndXmutually simple withP. But the numberkm + tmutually simple withTif and only iftmutually simple withT.Therefore, numbers relatively prime to m are located in those columns for whichtruns through the reduced system of residues moduloT.The number of such columns is φ(T).Each column presents the complete system of residues moduloP.From these residues φ(P)coprime withP.Hence, the total number of numbers coprime and withTand with n, equals φ(T)φ(n)

(φ (T)columns, each of which takes φ(P)numbers). These numbers, and only them, are coprime withetc.Thus, it is proved that

φ (tp)= φ (T) φ (P).

Examples.

№1 . Prove the following equalities

φ(4n) =

Proof.

№2 . solve the equation

Solution:because(m)=, That= , that is=600, =75, =3, then x-1=1, x=2,

y-1=2, y=3

Answer: x=2, y=3

We can calculate the value of the Euler function(m), knowing the canonical representation of the number m:

m=.

Because of the multiplier(m) we have:

(m)=.

But according to formula (1) we get that

-1), and therefore

(3)

Equality (3) can be rewritten as:

Because the=m, then(4)

Formula (3) or, which is the same, (4) is the desired one.

Examples.

№1 . What is the amount

Solution:,

, =18 (1- ) (1- =18 , Then= 1+1+2+2+6+6=18.

№2 . Based on the properties of the Euler number function, prove that there is an infinite set of primes in the sequence of natural numbers.

Solution:Flattening the number of primes by a finite set, suppose thatis the largest prime number and let a=is the product of all prime numbers, based on one of the properties of the Euler number function

Since a≥, then a is a composite number, but since its canonical representation contains all prime numbers, then=1. We have:

=1 ,

which is impossible, and thus it is proved that the set of prime numbers is infinite.

№3 .Solve the equation, where x=And=2.

Solution:We use the property of the Euler numerical function,

,

and by condition=2.

Express from=2 , we get, let's substitute in

:

(1+ -1=120, =11 =>

Then x=, x=11 13=143.

Answer:x= 143

2. Euler's theorem and Fermat.

In the theory of comparisons, Euler's theorem plays an important role.

Euler's theorem.

If an integer a is relatively prime to m, then

(1)

Proof.Let

(2)

is a reduced system of residues modulo m.

Ifais an integer relatively prime to m, then

(3)

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 a comparison of the form x 2 ≡a(mod pα), where p is a simple odd number. As shown in Section 4 §4, the solution to this congruence can be found by solving the congruence x 2 ≡a(mod p). And the comparison x 2 ≡a(mod pα) will have two solutions if a is a quadratic residue modulo p.

Example:

Solve Quadratic Comparison x 2 ≡86(mod 125).

125 = 5 3 , 5 is a prime number. Let's check if 86 is a square modulo 5.

The original comparison has 2 solutions.

Let's find a comparison solution x 2 ≡86(mod 5).

x 2 ≡1(mod 5).

This comparison could be solved in the way indicated in the previous paragraph, but we will use the fact that the square root of 1 modulo is ±1, and the comparison has exactly two solutions. Thus, the solution to congruence modulo 5 is

x≡±1(mod 5) or, otherwise, x=±(1+5 t 1).

Substitute the resulting solution in the comparison modulo 5 2 =25:

x 2 ≡86(mod 25)

x 2 ≡11(mod 25)

(1+5t 1) 2 ≡11(mod 25)

1+10t 1 +25t 1 2 ≡11(mod 25)

10t 1 ≡10(mod 25)

2t 1 ≡2(mod 5)

t 1 ≡1(mod 5), or equivalently, t 1 =1+5t 2 .

Then the solution to congruence modulo 25 is x=±(1+5(1+5 t 2))=±(6+25 t 2). Substitute the resulting solution in the comparison modulo 5 3 =125:

x 2 ≡86(mod 125)

(6+25t 2) 2 ≡86(mod 125)

36+12 25 t 2 +625t 2 2 ≡86(mod 125)

12 25 t 2 ≡50(mod 125)

12t 2 ≡2(mod 5)

2t 2 ≡2(mod 5)

t 2 ≡1(mod 5), or t 2 =1+5t 3 .

Then the solution to the comparison modulo 125 is x=±(6+25(1+5 t 3))=±(31+125 t 3).

Answer: x≡±31(mod 125).

Consider now a comparison of the form x 2 ≡a(mod2α). Such a comparison does not always have two solutions. For such a module, the following cases are possible:

1) α=1. Then the comparison has a solution only when a≡1(mod 2), and the solution is x≡1(mod 2) (one solution).

2) α=2. The comparison has solutions only when a≡1(mod 4), and the solution is x≡±1(mod 4) (two solutions).

3) α≥3. The comparison has solutions only when a≡1(mod 8), and there will be four such solutions. Comparison x 2 ≡a(mod 2 α) for α≥3 is solved in the same way as comparisons of the form x 2 ≡a(mod pα), only solutions modulo 8 act as the initial solution: x≡±1(mod 8) and x≡±3(mod 8). They should be compared modulo 16, then modulo 32, and so on up to modulo 2 α .

Example:

Solve Comparison x 2 ≡33(mod 64)

64=26. Let's check if the original comparison has a solution. 33≡1(mod 8), so the comparison has 4 solutions.

Modulo 8 these solutions will be: x≡±1(mod 8) and x≡±3(mod 8), which can be represented as x=±(1+4 t 1). Substitute this expression in comparison modulo 16

x 2 ≡33(mod 16)

(1+4t 1) 2 ≡1(mod 16)

1+8t 1 +16t 1 2 ≡1(mod 16)

8t 1 ≡0 (mod 16)

t 1 ≡0 (mod 2)

Then the solution will take the form x=±(1+4 t 1)=±(1+4(0+2 t 2))=±(1+8 t 2). Substitute the resulting solution in the congruence modulo 32:

x 2 ≡33(mod 32)

(1+8t 2) 2 ≡1(mod 32)

1+16t 2 +64t 2 2 ≡1(mod 32)

16t 2 ≡0 (mod 32)

t 2 ≡0 (mod 2)

Then the solution will take the form x=±(1+8 t 2) =±(1+8(0+2t 3)) =±(1+16 t 3). Substitute the resulting solution in the comparison modulo 64:

x 2 ≡33(mod 64)

(1+16t 3) 2 ≡33(mod 64)

1+32t 3 +256t 3 2 ≡33(mod 64)

32t 3 ≡32 (mod 64)

t 3 ≡1 (mod 2)

Then the solution will take the form x=±(1+16 t 3) =±(1+16(1+2t 4)) =±(17+32 t 4). So, modulo 64, the original comparison has four solutions: x≡±17(mod 64)and x≡±49(mod 64).

Now consider a general comparison: x 2 ≡a(mod m), (a,m)=1, - canonical decomposition of the module m. According to the Theorem from item 4 of §4, this comparison is equivalent to the system

If every comparison of this system is decidable, then the entire system is decidable. Having found the solution of each comparison of this system, we obtain a system of comparisons of the first degree, solving which, using the Chinese remainder theorem, we obtain the solution of the original comparison. Moreover, the number of different solutions of the original comparison (if it is solvable) is 2 k, if α=1, 2 k+1 if α=2, 2 k+2 if α≥3.

Example:

Solve Comparison x 2 ≡4(mod 21).

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.

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 .

Solution:

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)

Solution:

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.

Solution:

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 .

Solution:

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)

Solution:

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)

Solution:

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)

Solution:

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