Numbers comparable modulo 7. Comparison modulo a natural number

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.

Math project on topic

"Comparisons modulo"

Zaripova Aisylu

Sovetsky district of Kazan

MBOU "Secondary School No. 166", 7a grade

Scientific supervisor: Antonova N.A.

Table of contents

Introduction__________________________________________________________3

What are comparisons_____________________________________________4

Applying comparisons to problem solving______________________________6

The simplest use of modulo comparisons is to determine the divisibility of numbers___________________________6
One comparison task_______________________________8
The use of modulo comparisons in professional activities________________________________________________9

Conclusion_________________________________________________10

List of used literature_______________________________________11

Introduction.

Topic: Modulo comparisons.

Problem: Many students are faced with problems when preparing for Olympiads, the solution of which is based on knowledge of remainders from dividing integers by a natural number. We were interested in these types of problems and possible methods for solving them. It turns out that they can be solved using modulo comparisons.

Goal: Find out the essence of modulo comparisons, the main methods of working with modulo comparisons.

Objectives: find theoretical material on this topic, consider problems that are solved using modulo comparisons, show the most common methods for solving such problems, draw conclusions.

Object of study: number theory.

Subject of research: theory of modulo comparisons.

The work relates to theoretical research and can be used in preparation for mathematics Olympiads. Its content reveals the basic concepts of modulo comparisons and their main properties, and provides examples of solving problems on this topic.

I . What are comparisons?

The numbers and are said to be comparable in modulus if they are divisible by, in other words, a and b have the same remainders when divided by.

Designation

Examples:

12 and 32 are comparable modulo 5, since 12 when divided by 5 has a remainder of 2 and 32 when divided by 2 has a remainder of 2. It is written12 ;

101 and 17 are comparable modulo 21;

The theory of divisibility was largely created by Euler. The definition of comparison was formulated in the book by K.F. 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.” It was Gauss who proposed the symbolism of modulo comparisons that has become established in mathematics.

Proof:

If we add the second to the first equality, we get

is the sum of two integers, therefore is an integer, therefore.

If we subtract the second from the first equality, we get

this is the difference of two integers, which means it is an integer, therefore.

Consider the expression:

This is the difference of products of integers, which means it is an integer, therefore.

This is a consequence of the third property of comparisons.

Q.E.D.

5) If.

Proof: Let's find the sum of these two expressions:

is the sum of two integers, therefore it is an integer, therefore .

Q.E.D.

6) If is an integer, then

Proof: , wherep– an integer, multiply this equality by, we get: . Since is a product of integers, that is what needed to be proven.

7) If

Proof: the reasoning is similar to the proof of property 6.

8) If - coprime numbers, then

Proof: , divide this expression by, we get: - coprime numbers, which means they are divisible by an integer, i.e. =. And this means that what needed to be proven.

II . Applying comparisons to problem solving.

2.1. The simplest use of modulo comparisons is to determine the divisibility of numbers.

Example. Find the remainder of 2 2009 at 7.

Solution: Consider the powers of 2:

raising the comparison to the power of 668 and multiplying by, we get: .

Answer: 4.

Example. Prove that 7+7 2 +7 3 +…+7 4 n is divisible by 100 for anynfrom a set of integers.

Solution: Consider comparisons

etc. The cyclical nature of remainders is explained by the rules for multiplying numbers in a column. Adding up the first four comparisons, we get:

This means that this amount is divided by 100 without a remainder. Similarly, adding the following comparisons about four, we get that each such sum is divisible by 100 without a remainder. This means that the entire sum consisting of 4nterms is divisible by 100 without a remainder. Q.E.D.

Example. Determine at what valuenthe expression is divisible by 19 without a remainder.

Solution: .

Let's multiply this comparison by 20. We get.

Let's add up the comparisons, then. . Thus, the right side of the comparison is always divisible by 19 for any natural numbern, which means the original expression is divisible by 19 with naturaln.

Answer n – any natural number.

Example. What digit does the number end with?

Solution. To solve this problem, we will monitor only the last digit. Consider the powers of the number 14:

You can notice that if the exponent is odd, the value of the degree ends in 4, and if the exponent is even, it ends in 6. Then it ends in 6, i.e. is an even number. So it will end in 6.

Answer 6.

2.2. One comparison task.

The article by N. Vilenkin “Comparisons and classes of residues” presents a problem that was solved by the famous English physicist Dirac during his student years.

There is also a brief solution to this problem using modulo comparisons. But we encountered a number of similar problems. For example.

One passerby found a pile of apples near a tree on which a monkey was sitting. After counting them, he realized that if 1 apple is given to the monkey, then the number of remaining apples will be divided into n without a trace. Having given the extra apple to the monkey, he took 1/ n remaining apples and left. Later, the next passer-by approached the pile, then the next, etc. Each subsequent passer-by, having counted the apples, noticed that their number when divided by n gives the remainder 1 and, having given the extra apple to the monkey, he took 1 for himself n the remaining apples and moved on. After the last one left, n th passerby, the number of apples remaining in the pile was divided by n without a trace. How many apples were in the pile at first?

Carrying out the same reasoning as Dirac, we obtained a general formula for solving a class of similar problems: , wheren- natural number.

2.3. Application of module comparisons in professional activities.

Comparison theory is applied to coding theory, so all people who choose a profession related to computers will study, and possibly apply comparisons in their professional activities. For example, a number of number theory concepts, including modulo comparisons, are used to develop public key encryption algorithms.

Conclusion.

The work outlines the basic concepts and properties of modulo comparisons and illustrates the use of modulo comparisons with examples. The material can be used in preparation for olympiads in mathematics and the Unified State Exam.

The given list of references allows, if necessary, to consider some more complex aspects of the theory of modulo comparisons and its applications.

List of used literature.

Alfutova N.B. Algebra and number theory./N.B.Alfutova, A.V.Ustinov. M.:MCNMO, 2002, 466 p.

Bukhshtab A.A. Number theory. /A.A.Bukhshtab. M.: Education, 1960.

Vilenkin N. Comparisons and classes of residues./N. Vilenkin.//Quantum. – 1978.- 10.

Fedorova N.E. Study of algebra and mathematical analysis. Grade 10.http:// www. prosv. ru/ ebooks/ Fedorova_ Algebra_10 kl/1/ xht

ru. wikipedia. org/ wiki/Comparison_modulo.

Definition 1. If two numbers are 1) a And b when divided by p give the same remainder r, then such numbers are called equiremainder or comparable in modulus p.

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

But these numbers can be obtained by setting r equal to 0, 1, 2,..., p−1. Hence sp+r=a will get all possible integer values.

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

(2)

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

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

Statement 2. If two numbers a And b comparable in modulus p, That a−b divided by p.

Really. If two numbers a And b comparable in modulus p, then when divided by p have the same remainder p. Then

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

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

Proof. Let us denote by r And r 1 division remainder a And b on p. Then

Examples 25≡39 (mod 7), −18≡14 (mod 4).

From the first example it follows that 25 when divided by 7 gives the same remainder as 39. Indeed, 25 = 3·7+4 (remainder 4). 39=3·7+4 (remainder 4). When considering the second example, you need to take into account that the remainder must be a non-negative number less than the modulus (i.e. 4). Then we can write: −18=−5·4+2 (remainder 2), 14=3·4+2 (remainder 2). Therefore, −18 when divided by 4 leaves a remainder of 2, and 14 when divided by 4 leaves a remainder of 2.

Properties of modulo comparisons

Property 1. For anyone a And p Always

there is not always a comparison

Where λ is the greatest common divisor of numbers m And p.

Proof. Let λ greatest common divisor of numbers m And p. Then

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

Hence

And m is one of the divisors of the number p, That

Where h=pqs.

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

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 to classify 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.

At n they give the same remainders.

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

The statement “a and b are comparable modulo n” is written as:

Modulo equality properties

The modulo comparison relation has the properties

Any two integers a And b comparable modulo 1.

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

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

If the numbers a And b comparable in modulus n, then their degrees a k And b k are also comparable in modulus n under any natural k.

If the numbers a And b comparable in modulus n, And n divided by m, That a And b comparable in modulus m.

In order for the numbers a And b were comparable in modulus n, presented in the form of its canonical decomposition into simple 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 abbreviation rules for comparisons are as follows.

You also cannot perform operations on comparisons if their moduli 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 [ a] n or . Thus, the comparison is equivalent to the equality of residue classes [a] n = [b] n .

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

The operations of addition and multiplication by induce 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 - finite field.

Deduction systems

The residue system allows you to perform arithmetic operations on a finite set of numbers without going beyond its limits. Full system of deductions modulo n is any set of n integers that are incomparable modulo n. Usually, the smallest non-negative residues are taken as a complete system of residues modulo n

0,1,...,n − 1

or the absolute smallest deductions consisting of numbers

in case of odd n and numbers

in case of even n .

Solving comparisons

Comparisons of the first degree

In number theory, cryptography and other fields of science, the problem of finding solutions to first-degree comparisons of the form often arises:

Solving such a comparison begins with calculating 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, what is the same, d modulo solutions m. In this case, as a result of reducing the original comparison by d the comparison is:

Where a 1 = a / d , b 1 = b / d And m 1 = m / d are integers, and a 1 and m 1 are relatively prime. 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 calculation of value c can be implemented 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 down the value c as:

Example

For comparison we have d= 2, so modulo 22 the comparison has two solutions. Let's replace 26 by 4, comparable to it modulo 22, and then reduce all 3 numbers by 2:

Since 2 is coprime to modulo 11, we can reduce the left and right sides by 2. As a result, we obtain one solution modulo 11: , 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.

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