Comparison modulo a natural number. Solving comparisons and their applications Solving comparisons

Comparison with one unknown x looks like

Where . If a n not divisible by m, that’s what’s called degree comparisons.

By decision comparison is any integer x 0 , for which

If X 0 satisfies the comparison, then, according to the property of 9 comparisons, all integers comparable to x 0 modulo m. Therefore, all comparison solutions belonging to the same residue class modulo T, we will consider it as one solution. Thus, the comparison has as many solutions as there are elements of the complete system of residues that satisfy it.

Comparisons whose solution sets coincide are called equivalent.

2.2.1 Comparisons of the first degree

First degree comparison with one unknown X looks like

(2.2)

Theorem 2.4. In order for a comparison to have at least one solution, it is necessary and sufficient that the number b divided by GCD( a, m).

Proof. First we 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 such 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 subtrahend are divided by d, and therefore 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 exist the following integers a 1 , b 1 ,T 1 , What .

Using the extended Euclidean algorithm, we find a linear representation of the number 1 = gcd( a 1 , m 1 ):

for some x 0 , y 0 . Let's multiply both sides of the last equality by b 1 d:

or, what is the same,

,

that is, and is the solution to the comparison. □

Example 2.10. Comparison 9 X= 6 (mod 12) has a solution since gcd(9, 12) = 3 and 6 is divisible by 3. □

Example 2.11. Comparison 6x= 9 (mod 12) has no solutions, since gcd(6, 12) = 6, and 9 is not divisible by 6. □

Theorem 2.5. Let comparison (2.2) be solvable and d = GCD( a, m). Then the set of comparison solutions (2.2) consists of d modulo residue classes T, namely, if X 0 - one of the solutions, then all other solutions are

Proof. Let X 0 - solution of comparison (2.2), that is And , . So there is such a thing q, What Oh 0 − b = qm. Now substituting 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: X 0 = 2, x 0 + 4 = 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.□

We'll show you how to solve first degree comparisons. Without loss of generality, we will assume that GCD( a, t) = 1. Then the solution to comparison (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:

Let's multiply both sides of this equality by b, we get: b = abq + mrb, where abq - b = - mrb, that is a ∙ (bq) = b(mod m) And bq- solution of comparison (2.2).

Another solution is to use Euler's theorem. Again we believe that GCD(a, T)= 1. We apply Euler’s theorem: . Multiply both sides of the comparison by b: . Rewriting the last expression as , we obtain that is a solution to comparison (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, in order for the comparison to be resolvable. If X 0 - comparison solution A 1 x = b 1 (mod m 1), and the only one, since GCD( A 1 , m 1) = 1, then X 0 will be the solution 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.

Content.

Introduction

§1. Modulo comparison

§2. Comparison Properties

1. Module-Independent Comparison Properties
2. Module-dependent properties of comparisons

§3. Deduction system

1. Full system of deductions
2. 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 solving comparisons

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

§2. First degree comparisons and their solutions

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

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

§4. Division of comparisons of higher degrees

§5. Antiderivative 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. Conversion of an ordinary fraction to a final fraction

decimal systematic fraction

Conclusion

Literature

Introduction

In our lives we often have to deal with integers and problems 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 in modulus m.

The word “module” comes from the Latin modulus, which in Russian means “measure”, “magnitude”.

The statement “a is comparable 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 Studies”. 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 labor-intensive 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 cases where it is enough to know in any research numbers accurate 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 basic 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, with each chapter divided into paragraphs, and paragraphs into paragraphs.

The first chapter outlines general issues of the theory of comparisons. Here we consider the concept of modulo comparison, properties of comparisons, the complete and reduced system of residues, Euler's function, Euler's and Fermat's theorem.

The second chapter is devoted to the theory of comparisons with the unknown. It outlines the basic concepts associated with solving comparisons, considers methods for solving comparisons of the first degree (selection method, Euler's method, the method of the Euclidean algorithm, 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, checking the results of actions, and converting ordinary fractions into systematic decimal fractions are considered.

The presentation of 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 be the ring of integers, m be a fixed integer, and m·z be the set of all integers that are multiples of m.

Definition 1. Two integers a and b are said to be comparable 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 a-b is divisible by m.

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

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

Examples.

Theorem. (a 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 remainders 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₂), that is, a-b m or a b (mod m).

Conversely, let a b (mod m). This means that 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, when dividing a by m, the same remainder is obtained as when 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 identical remainders when divided by m are called equal remainders or comparable modulo m.

Examples.

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

1. Prove that the following comparisons are false:

If 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, therefore our comparison is incorrect.

§2. Comparison Properties

1. Module-independent properties of comparisons.

Many properties of comparisons are similar to the properties of equalities.

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

B) 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 the 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 sides 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. Therefore a·c-b·d = (a·c - b·c)+(b·c- b·d)=(a-b)·c+b·(c-d) є mz, that is, a·c·d (mod m).

Consequence. Both sides of the comparison can be raised to the same non-negative integer 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 required 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 1 (mod 13), then 1+ 1+1·3+1·9 (mod 13).

etc.

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 sides of the comparison, we get:

(mod 24).

We have: (mod 24), therefore

(mod 24) for any k є N.

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

1. Both sides 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 when 196 is divided 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 sides of the comparison and the modulus can be multiplied by the same positive integer.

Proof.

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

Example.

Determine whether the value of an expression is an integer.

Solution:

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

1 (mod 9)

31 (mod 27)

Let's 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 meaning of the expressionis also not an integer.

1. Both sides of the comparison can be divided by their common factor if it is coprime to the modulus.

Proof.

If ca cb (mod m), that is, m/c(a-b) and the 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 sides of the comparison by 3 we get:

20 (mod 17).

Generally speaking, it is impossible to divide both sides of a comparison by a number that is not coprime to the modulus, since after division the numbers may be obtained that are incomparable with respect to a given modulus.

Example.

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

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

Proof.

If ka kb (mod km), then k (a-b) is divided 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 sides 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 up 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 comparison modulo m, individual terms and factors can be replaced by numbers comparable modulo m.

At the same time, it should be noted that the exponents found in comparisons cannot be replaced in this way: from

a n c(mod m) and n k(mod m) it does not follow that a k s (mod m).

Property 11 has a number of important applications. In particular, with its help it is possible to give a theoretical justification for the signs of divisibility. To illustrate, as an example, we will give the derivation of the divisibility test by 3.

Example.

Every 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. Full system of deductions.

Equal remainder numbers, or, what is the same thing, comparable modulo m, form a class of numbers modulo m.

From this definition it follows that all numbers in the class correspond to the same remainder r, and we get all the numbers in the class if, in the form mq+r, we make q run through all the integers.

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; at r> we have ρ=r-m; finally, if m is even and r=, then any of the two numbers can be taken as ρ and -m= - .

Let us choose from each class of residues modulo T one number at a time. We get t integers: x 1,…, x m. The set (x 1,…, x t) is called complete system of deductions modulo m.

Since each class contains an infinite number of residues, it is possible to compose an infinite number of different complete systems of residues for a given module m, each of which contains t deductions.

Example.

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

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

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

Let's create 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.

The most common:

1. Complete system of least non-negative residues: 0, 1, t -1 In the example above: 0, 1, 2, 3, 4. This system of residues is simple to create: you need to write down all the non-negative remainders obtained when dividing 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 minimal deductions.In the case of odd m, the absolute smallest residues are represented side by side.

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

and in the case of 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 basic properties of the complete system of residues.

Theorem 1 . Any collection of m integers:

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

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

Proof.

1. Each of the numbers in the collection (1) belongs to a certain 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. There are m numbers in (1), i.e., the same number as there are modulo classes T.

x 1, x 2,…, x t - complete system of deductions modulo m.

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

Proof.

Let's consider

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

1. Each of the numbers in the collection (2) belongs to a certain 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 in (2) there were two numbers such that

ax i +b ax j + b (mod m), (i = j), then we would get ax i ax j (mod t). 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 t) at (i = j) , since x 1, x 2, ..., x m - a complete 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 - 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, t) = (b, t).

Indeed, let δ be a common divisor of a and m, then aδ, m δ. Since a = b +mt, then b=a-mt, therefore bδ. Therefore, any common divisor of the numbers 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 modulus divisor t and any number a from this class of deductions by T called the greatest common divisor T and this class of deductions.

Definition 2. Residue class a modulo t called coprime to modulus 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 the numbers (..., -10, -4, 2, 8, 14, ...). The greatest common divisor of any of these numbers and modulus 6 is 2. Hence, (2, 6) = 2. The greatest common divisor of any number from class 5 and modulus 6 is 1. Hence, class 5 is coprime to modulus 6.

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

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

From Definition 3 follows a method for obtaining the reduced system of modulo residues T: it is necessary to write down 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. Obviously, an infinite number of systems of residues modulo m can be composed.

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

Example.

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

Theorem 2.

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

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

Proof

A) Each number in the population (1) belongs to a certain class.

1. All numbers from (1) are pairwise incomparable in modulus 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 to modulo m.
3. Total (1) available 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 modulo deductions T.

§4. Euler function.

Euler's and Fermat's theorems.

1. Euler function.

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

Let us choose as representatives of the modulo residue classes t numbers 1, ..., t - 1, t. Then φ (t) - 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 to 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, numbers 1, 5, 7, 11 are coprime to 12. This means

φ(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 assume φ(1) = 1.

Let's move on to calculating the Euler function.

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

Proof.

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

2) If t = p k - prime power p, then

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

Proof.

Complete system of modulo deductions 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 in the case whenAdivided byR.But among the numbers 1, ... , pk -1 onRonly numbers are divisiblep, 2p, ... , p2 , ... RTo, the number of which is equalRTo: p = pk-1. This means that they are coprime witht = pTorestRTo- Rk-1= pk-l(p-1)numbers. This proves that

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

Theorem1.

The Euler function is multiplicative, that is, for relatively prime 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 iftypecoprime numbers, then

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

Let us arrange the complete system of deductions modulotpasPXT -matrices

1 2 T

t +1 t +2 2t

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

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

Because theTAndPare relatively prime, then the numberXreciprocally just withtpthen and only whenXreciprocally just withTAndXreciprocally just withP. But the numberkm+treciprocally just withTif and only iftreciprocally just withT.Therefore, numbers coprime to m are located in those columns for whichtruns through the reduced system of modulo residuesT.The number of such columns is equal to φ(T).Each column presents the complete system of deductions moduloP.From these deductions φ(P)coprime withP.This means that the total number of numbers that are relatively prime and withTand with n, equal to φ(T)φ(n)

(φ (T)columns, in each of which φ is taken(P)numbers). These numbers, and only they, are coprime toetc.This proves that

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

Examples.

№1 . Prove the validity of 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=.

Due to multiplicativity(m) we have:

(m)=.

But according to formula (1) we find 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 what we are looking for.

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 in the sequence of natural numbers there is an infinite set of prime numbers.

Solution:Assuming that the number of prime numbers is a finite set, we assume that- 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.

Let us express from=2 , we get, substitute in

:

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

Then x=, x=11·13=143.

Answer:x= 143

2. Euler's theorem and Fermat.

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

Euler's theorem.

If an integer a is coprime to m, then

(1)

Proof.Let

(2)

there is a reduced system of residues modulo m.

Ifais an integer coprime to m, then

(3)

A first degree comparison with one unknown has the form:

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

Solve comparison- means finding all values ​​of x that satisfy it. Two comparisons that satisfy the same values ​​of x are called equivalent.

If comparison (1) is satisfied by any x = x 1, then (according to 49) all numbers comparable to x 1, modulo m: x x 1 (mod m). This entire class of numbers is considered to be one solution. With such an agreement, the following conclusion can be drawn.

66.C alignment (1) will have as many solutions as the number of residues of the complete system that satisfy it.

Example. Comparison

6x– 4 0 (mod 8)

Among the numbers 0, 1,2, 3, 4, 5, 6, 7, two numbers satisfy the complete system of residues modulo 8: 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 moving 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 satisfy it. But when x runs through the complete system of modulo residues T, That Oh runs through the complete 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. When (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 by d, otherwise comparison (2) is impossible for any integer x . Assuming therefore b multiples d, let's put a = a 1 d, b = b 1 d, m = m 1 d. Then comparison (2) will be equivalent to this (abbreviated 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 – the smallest non-negative residue of this solution modulo m 1 , then all numbers are x , forming this solution are found in the form

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

Modulo m, 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 modulo residues m. But the following numbers (3) will fall here:

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

those. Total d numbers (3); therefore comparison (2) has d decisions.

We get the theorem:

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

69. A method for solving comparisons of the first degree, based on the theory of continued fractions:

Expanding into a continued fraction the relation m:a,

and looking at the last two matching fractions:

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

So the comparison has a solution

to find, 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 sides of the comparison and the modulus by 3, we get the comparison

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

which we must first solve. We have

q
P 3

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

x–26 ∙ 25 99 (mod 107).

Hence, the solutions to 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 by a given modulo

70.If the numbers are integers a And n are 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 used for it is a- 1 (mod n).

The calculation of reciprocal quantities modulo a certain value can be performed by solving a comparison of the first degree with one unknown, in which x number accepted a′.

To find a comparison solution

a∙x≡ 1(mod m),

Where ( a,m)= 1,

you 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 tell 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 respectively mean 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 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), Cartesian product of sets A And B(i.e. a set of pairs of the form ( a, b), Where a A, b B). Via | A| the power of the set is always denoted A, i.e. number of elements in the set A.

An operation is a rule according to which any two elements of a set G(a And b) is matched with the third element from G: a b.

Lots of elements G with an operation is called group, if the following conditions are satisfied.

Let's consider the system of comparisons

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

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

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

Definition. Solution of the system of comparisons(2) is the class of numbers modulo M = that satisfy each comparison of the system.

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

Let's consider the system of comparisons of the 1st degree (3)

Theorem2. 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 - a 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 from §2).

Let the solution be , that is, where k€Z.

M== , that is, 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 x into 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, that is x≡-4(mod 24).

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

Corollary 1. Comparison system (4)

Either it has no solutions, or it has one solution - a class modulo M=.

Proof. If the system of the first two comparisons has no solutions, then (4) does not have solutions. If it has a solution x ≡ a(mod), then by adding a third comparison of the system to this comparison, 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 will continue this way until we have exhausted all comparisons of system (4). If there is a solution, then this is a class modulo M.

Comment. The LCM property is used here: =.

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

Example:

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

We substitute into the second comparison: 2 +5t≡ 0(mod 3) or 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k. Let's 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 to know others method of solving this system, (We use the fact that the system has one solution.) Let us multiply both parts and the module of the first comparison by 21, the second by 35, and the third by 15: from the sum of the first and third we subtract the second:

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

Having solved each comparison of the system, we obtain an equivalent system

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

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

Problems that boil down to the consideration of a 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: find a number that gives given remainders when divided by given numbers. It also gives a solution equivalent to the following theorem.

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

Then the solution of the system

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

Proof. Since we get x0≡

In a similar way, we check that x0≡c2(mod m2),…, x0≡cs(mod ms), that is, x0 satisfies all

system comparisons.

10. Comparisons of the 1st degree. Uncertain equations

§ 2. Comparisons of the 1st degree. Uncertain equations

The 1st degree comparison 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 - a complete system of residues modulo m. Since (a,m) = 1, then 0,a,2a,...,(m-1)a is also a complete system of residues (Theorem 3, §2, Chapter 2.). It contains one and only one number comparable to b modulo m (belonging to the same class as b). Let this be ax 0, that is, 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 to the comparison ax≡b(mod m) is the class x 0 ≡a φ (m)-1 b(mod m).

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

Let's consider comparison solution methods ax ≡b(mod m).

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

2. Using Euler's theorem (Theorem 5).

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

1) 223x ≡ 115(mod ll).

First, we replace the coefficients with the smallest absolute value deductions: 3х ≡ 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 to the right side a number that is a multiple of the modulus:

3x ≡ 5 + 22(mod 11). Dividing both sides by the number 3, coprime to the modulus, we obtain 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 comparison (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 constitute one class of modulo residues and are found by the formulas

Where With satisfies the auxiliary comparison

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

1) Having made sure that (a,m) = d, d> 1 and b:d, we divide both parts in comparisons (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 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 according to Theorem 2(3) is equivalent to the original comparison (2). Since ( 1, Then the auxiliary comparison 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 lines at the top)

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, therefore the comparison has four solutions. Dividing both parts and the module by 4, we get:

5х≡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 solving uncertain equations

Let us consider an indeterminate or, as it is otherwise called, a Diophantine equation of the first degree with two unknowns ax + by = c, where a, b, c € Z. You need 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 divide both sides of the equation by d. Therefore, it is enough 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, from which

Moreover, - is an integer, it is a partial value of the unknown y, corresponding to x1 (it turns out, like x1, at t = 0). And the general solution to 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 module 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(mod21).

x ≡ -1 (mod 21), that is, x=-1+21t, t€Z. Let's substitute the found x into the equation. 25(-1 + 21t)- 21y= 17; 21у =-42 + 25* 21t and у =-2 + 25t.