How to compare modulo positive integers. Comparing numbers modulo

We continue to study rational numbers. In this lesson we will learn how to compare them.

From previous lessons we learned that the further to the right a number is located on the coordinate line, the larger it is. And accordingly, the further to the left the number is located on the coordinate line, the smaller it is.

For example, if you compare the numbers 4 and 1, you can immediately answer that 4 is more than 1. This is a completely logical statement and everyone will agree with it.

As proof, we can cite the coordinate line. It shows that the four lies to the right of the one

For this case, there is also a rule that can be used if desired. It looks like this:

Of two positive numbers, the number whose modulus is greater is greater.

To answer the question which number is greater and which is less, you first need to find the modules of these numbers, compare these modules, and then answer the question.

For example, compare the same numbers 4 and 1, applying the above rule

Finding the modules of numbers:

|4| = 4

|1| = 1

Let's compare the found modules:

4 > 1

We answer the question:

4 > 1

For negative numbers There is another rule, it looks like this:

Of two negative numbers, the number whose modulus is smaller is greater.

For example, compare the numbers −3 and −1

Finding the modules of numbers

|−3| = 3

|−1| = 1

Let's compare the found modules:

3 > 1

We answer the question:

−3 < −1

The modulus of a number should not be confused with the number itself. Common mistake many newbies. For example, if the modulus of −3 is greater than the modulus of −1, this does not mean that −3 is greater than −1.

The number −3 is less than the number −1. This can be understood if we use the coordinate line

It can be seen that the number −3 lies further to the left than −1. And we know that the further to the left, the less.

If you compare a negative number with a positive one, the answer will suggest itself. Any negative number will be less than any positive number. For example, −4 is less than 2

It can be seen that −4 lies further to the left than 2. And we know that “the further to the left, the less.”

Here, first of all, you need to look at the signs of the numbers. A minus sign in front of a number indicates that the number is negative. If the number sign is missing, then the number is positive, but you can write it down for clarity. Recall that this is a plus sign

As an example, we looked at integers of the form −4, −3 −1, 2. Comparing such numbers, as well as depicting them on a coordinate line, is not difficult.

It is much more difficult to compare other types of numbers, such as fractions, mixed numbers and decimals, some of which are negative. Here you will basically have to apply the rules, because it is not always possible to accurately depict such numbers on a coordinate line. In some cases, a number will be needed to make it easier to compare and understand.

Example 1. Compare rational numbers

So, you need to compare a negative number with a positive one. Any negative number is less than any positive number. Therefore, without wasting time, we answer that it is less than

Example 2.

You need to compare two negative numbers. Of two negative numbers, the one whose magnitude is smaller is greater.

Finding the modules of numbers:

Let's compare the found modules:

Example 3. Compare the numbers 2.34 and

You need to compare a positive number with a negative one. Any positive number is greater than any negative number. Therefore, without wasting time, we answer that 2.34 is more than

Example 4. Compare rational numbers and

Finding the modules of numbers:

We compare the found modules. But first, let’s bring them to a clear form to make it easier to compare, namely, we’ll convert them into improper fractions and bring them to a common denominator

According to the rule, of two negative numbers, the number whose modulus is smaller is greater. This means rational is greater than , because the modulus of the number is less than the modulus of the number

Example 5.

You need to compare zero with a negative number. Zero is greater than any negative number, so without wasting time we answer that 0 is greater than

Example 6. Compare rational numbers 0 and

You need to compare zero with a positive number. Zero is less than any positive number, so without wasting time we answer that 0 is less than

Example 7. Compare rational numbers 4.53 and 4.403

You need to compare two positive numbers. Of two positive numbers, the number whose modulus is greater is greater.

Let's make the number of digits after the decimal point the same in both fractions. To do this, in the fraction 4.53 we add one zero at the end

Finding the modules of numbers

Let's compare the found modules:

According to the rule, of two positive numbers, the number whose absolute value is greater is greater. Means rational number 4.53 is greater than 4.403 because the modulus of 4.53 is greater than the modulus of 4.403

Example 8. Compare rational numbers and

You need to compare two negative numbers. Of two negative numbers, the number whose modulus is smaller is greater.

Finding the modules of numbers:

We compare the found modules. But first, let’s bring them to a clear form to make it easier to compare, namely, let’s convert the mixed number into improper fraction, then we bring both fractions to a common denominator:

According to the rule, of two negative numbers, the number whose modulus is smaller is greater. This means rational is greater than , because the modulus of the number is less than the modulus of the number

Comparing decimals is much easier than comparing fractions and mixed numbers. In some cases, by looking at the whole part of such a fraction, you can immediately answer the question of which fraction is larger and which is smaller.

To do this, you need to compare the modules of the entire parts. This will allow you to quickly answer the question in the task. After all, as you know, entire parts in decimals have more weight than fractional ones.

Example 9. Compare rational numbers 15.4 and 2.1256

The modulus of the whole part of the fraction is 15.4 greater than the modulus of the whole part of the fraction 2.1256

therefore the fraction 15.4 is greater than the fraction 2.1256

15,4 > 2,1256

In other words, we didn’t have to waste time adding zeros to the fraction 15.4 and comparing the resulting fractions like ordinary numbers

154000 > 21256

The comparison rules remain the same. In our case, we compared positive numbers.

Example 10. Compare rational numbers −15.2 and −0.152

You need to compare two negative numbers. Of two negative numbers, the number whose modulus is smaller is greater. But we will compare only the modules of integer parts

We see that the modulus of the whole part of the fraction is −15.2 greater than the modulus of the whole part of the fraction −0.152.

This means rational −0.152 is greater than −15.2 because the modulus of the integer part of the number −0.152 is less than the modulus of the integer part of the number −15.2

−0,152 > −15,2

Example 11. Compare rational numbers −3.4 and −3.7

You need to compare two negative numbers. Of two negative numbers, the number whose modulus is smaller is greater. But we will compare only the modules of integer parts. But the problem is that the moduli of integers are equal:

In this case, you will have to use the old method: find the modules of rational numbers and compare these modules

Let's compare the found modules:

According to the rule, of two negative numbers, the number whose modulus is smaller is greater. This means rational −3.4 is greater than −3.7 because the modulus of the number −3.4 is less than the modulus of the number −3.7

−3,4 > −3,7

Example 12. Compare rational numbers 0,(3) and

You need to compare two positive numbers. Moreover, compare a periodic fraction with a simple fraction.

Let's convert the periodic fraction 0,(3) into common fraction and compare it with a fraction. After converting the periodic fraction 0,(3) into an ordinary fraction, it becomes the fraction

Finding the modules of numbers:

We compare the found modules. But first, let’s bring them to an understandable form to make it easier to compare, namely, let’s bring them to a common denominator:

According to the rule, of two positive numbers, the number whose absolute value is greater is greater. This means that a rational number is greater than 0,(3) because the modulus of the number is greater than the modulus of the number 0,(3)

Did you like the lesson?
Join our new group VKontakte and start receiving notifications about new lessons

PERVUSHKIN BORIS NIKOLAEVICH

Private educational institution "St. Petersburg School "Tete-a-Tete"

Mathematic teacher Highest category

Comparing numbers modulo

Definition 1. If two numbers1 ) aAndbwhen divided bypgive the same remainderr, then such numbers are called equiremainder orcomparable in modulus p.

Statement 1. Letpsome positive number. Then every numberaalways and, moreover, in the only way can be represented in the form

Wheres- number, androne of the numbers 0,1, ...,p−1.

1 ) In this article, the word number will be understood as an integer.

Really. Ifswill receive a value from −∞ to +∞, then the numberssprepresent the collection of all numbers that are multiples ofp. Let's look at the numbers betweenspAnd (s+1) p=sp+p. Becausepis a positive integer, then betweenspAndsp+pthere are numbers

But these numbers can be obtained by settingrequal to 0, 1, 2,...,p−1. Hencesp+r=awill get all possible integer values.

Let us show that this representation is unique. Let's pretend thatpcan be represented in two waysa=sp+rAnda=s1 p+ r1 . Then

or

Becauser1 accepts one of the numbers 0,1, ...,p−1, then the absolute valuer1 − rlessp. But from (2) it follows thatr1 − rmultiplep. Hencer1 = rAnds1 = s.

Numberrcalledminus numbersamodulop(in other words, the numberrcalled the remainder of a numberaonp).

Statement 2. If two numbersaAndbcomparable in modulusp, Thata−bdivided byp.

Really. If two numbersaAndbcomparable in modulusp, then when divided byphave the same remainderp. Then

WheresAnds1 some integers.

The difference of these numbers

divided byp, because right part equation (3) is divided byp.

Statement 3. If the difference of two numbers is divisible byp, then these numbers are comparable in modulusp.

Proof. Let us denote byrAndr1 division remaindersaAndbonp. Then

where

According toa−bdivided byp. Hencer− r1 is also divisible byp. But becauserAndr1 numbers 0,1,...,p−1, then the absolute value |r− r1 |< p. Then, in order tor− r1 divided bypcondition must be metr= r1 .

It follows from the statement that comparable numbers are those numbers whose difference is divisible by the modulus.

If you need to write down that numbersaAndbcomparable in modulusp, then we use the notation (introduced by Gauss):

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 anyoneaAndpAlways

Property 2. If two numbersaAndccomparable to a numberbmodulop, ThataAndccomparable to each other according to the same module, i.e. If

That

Really. From the condition of property 2 it followsa−bAndb−care divided intop. Then their suma−b+(b−c)=a−calso divided intop.

Property 3. If

That

Really. Becausea−bAndm−nare divided intop, That

also divided intop.

This property can be extended to any number of comparisons that have the same modulus.

Property 4. If

That

Furtherm−ndivided byp, henceb(m−n)=bm−bnalso divided intop, Means

So two numbersamAndbncomparable in modulus to the same numberbm, therefore they are comparable to each other (property 2).

Property 5. If

That

Whereksome non-negative integer.

Really. We havea≡bmod(p). From property 4 it follows

Present all properties 1-5 in the following statement:

Statement 4. Letf( x1 , x2 , x3 , ...) is an entire rational function with integer coefficients and let

Then

With division everything is different. From comparison

Statement 5. Let

Whereλ Thisgreatest common divisornumbersmAndp.

Proof. Letλ greatest common divisor of numbersmAndp. Then

Becausem(a−b)divided byk, That

has a zero remainder, i.e.m1 ( a−b) divided byk1 . But the numbersm1 Andk1 numbers are relatively prime. Hencea−bdivided byk1 = k/λand then,p,q,s.

Really. Differencea≡bmust be a multiple ofp,q,s.and therefore must be a multipleh.

In the special case, if the modulesp,q,smutually prime numbers, That

Whereh=pqs.

Note that we can allow comparisons based on negative modules, i.e. comparisona≡bmod(p) means in this case that the differencea−bdivided byp. All properties of comparisons remain in force for negative modules.

For two integers X And at Let us introduce a relation of comparability by parity if their difference is an even number. It is easy to check that all three previously introduced equivalence conditions are satisfied. The equivalence relation introduced in this way splits the entire set of integers into two disjoint subsets: the subset of even numbers and the subset of odd numbers.

Generalizing this case, we will say that two integers that differ by a multiple of some fixed natural number are equivalent. This is the basis for the concept of modulo comparability, introduced by Gauss.

Number A, comparable to b modulo m, if their difference is divisible by a fixed natural number m, that is a - b divided by m. Symbolically this is written as:

a ≡ b(mod m),

and it reads like this: A comparable to b modulo m.

The relation introduced in this way, thanks to the deep analogy between comparisons and equalities, simplifies calculations in which numbers differing by a multiple m, do not actually differ (since comparison is equality up to some multiple of m).

For example, the numbers 7 and 19 are comparable modulo 4, but not comparable modulo 5, because 19-7=12 is divisible by 4 and not divisible by 5.

It can also be said that the number X modulo m equal to the remainder when dividing by an integer X on m, because

x=km+r, r = 0, 1, 2, ... , m-1.

It is easy to check that the comparability of numbers according to a given module has all the properties of equivalence. Therefore, the set of integers is divided into classes of numbers comparable in modulus m. The number of such classes is equal m, and all numbers of the same class when divided by m give the same remainder. For example, if m= 3, then we get three classes: the class of numbers that are multiples of 3 (giving a remainder 0 when divided by 3), the class of numbers that leave a remainder 1 when divided by 3, and the class of numbers that leave a remainder 2 when divided by 3.

Examples of using comparisons are delivered well known signs divisibility. Common number representation n numbers in the decimal number system has the form:

n = c10 2 + b10 1 + a10 0,

Where a, b, c,- digits of a number written from right to left, so A- number of units, b- number of tens, etc. Since 10k ≡ 1(mod9) for any k≥0, then from what is written it follows that

n ≡ c + b + a(mod9),

whence follows the test of divisibility by 9: n is divisible by 9 if and only if the sum of its digits is divisible by 9. This reasoning also applies when replacing 9 by 3.

We obtain the test for divisibility by 11. Comparisons take place:

10≡- 1(mod11), 10 2 ≡ 1(mod11) 10 3 ≡- 1(mod11), and so on. That's why n ≡ c - b + a - ….(mod11).

Hence, n is divisible by 11 if and only if the alternating sum of its digits a - b + c -... is divisible by 11.

For example, the alternating sum of the digits of the number 9581 is 1 - 8 + 5 - 9 = -11, it is divisible by 11, which means the number 9581 is divisible by 11.

If there are comparisons: , then they can be added, subtracted and multiplied term by term in the same way as equalities:

A comparison can always be multiplied by an integer:

if , then

However, reducing a comparison by any factor is not always possible. For example, but it is impossible to reduce it by the common factor 6 for the numbers 42 and 12; such a reduction leads to an incorrect result, since .

From the definition of comparability modulo it follows that reduction by a factor is permissible if this factor is coprime to the modulus.

It was already noted above that any integer is comparable mod m with one of the following numbers: 0, 1, 2,... , m-1.

In addition to this series, there are other series of numbers that have the same property; so, for example, any number is comparable mod 5 with one of the following numbers: 0, 1, 2, 3, 4, but also comparable with one of the following numbers: 0, -4, -3, -2, -1, or 0, 1, -1, 2, -2. Any such series of numbers is called a complete system of residues modulo 5.

Thus, the complete system of residues mod m any series of m numbers, no two of which are comparable to each other. Commonly used complete system residues, consisting of numbers: 0, 1, 2, ..., m-1. Subtracting the number n modulo m is the remainder of the division n on m, which follows from the representation n = km + r, 0<r<m- 1.

Comparing numbers modulo

Prepared by: Irina Zutikova

MAOU "Lyceum No. 6"

Class: 10 "a"

Scientific supervisor: Zheltova Olga Nikolaevna

Tambov

2016

• Problem
• Objective of the project
• Hypothesis
• Project objectives and plan for achieving them
• Comparisons and their properties
• Examples of problems and their solutions
• Used sites and literature

Problem:

Most students rarely use modulo comparison of numbers to solve non-standard and olympiad tasks.

Objective of the project:

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

Hypothesis:

A deeper study of the topic “Comparing numbers modulo” will help students solve some non-standard and olympiad tasks.

Project objectives and plan for achieving 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 “Comparing numbers modulo.”

4. Conduct a lesson on the topic “Comparing numbers modulo” in grade 10a.

5.Give the class homework on the topic “Comparison by module.”

6.Compare the time to complete the task before and after studying the topic “Comparison by Module”.

7.Draw conclusions.

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

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

As I found out, some textbooks do not even touch on this topic, despite the advanced level. And the topic is presented in the most clear and accessible way 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”, relying on the theory from this textbook.

Comparisons and their properties.

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

Theorem: if and only if the difference of 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. Symmetrical comparisons.If the number a is comparable to the number b modulo m, then the number b is comparable to the number a modulo the same (m>0; a,b,m are integers).
3. Transitivity of comparisons.If the number a is comparable to the number b modulo m, and the number b is comparable to the number c modulo the same modulo, then the number a is comparable to the number c modulo m (m>0; a,b,c,m are integers).
4. If the number a is comparable to the number b modulo m, then the number a n comparable by number b n modulo m(m>0; a,b,m-integers; n-natural number).

Examples of problems and their solutions.

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

Solution:

Because last digit numbers are the remainder of 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 +11 n+2 Divisible by 133 without remainder.

Solution:

12 2n+1 =12*144 n 12*11 n (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)divides by 133 without remainder. Therefore, (12 2n+1 +11 n+2 ) is divisible by 133 without a remainder.

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

Solution:

Since 16 1(mod 15), then

2 2015 8(mod 15)

Answer:8.

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

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. (Phystech2015)

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 such that, when divided by it, the remainders 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) (by 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) (by property)

41

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.