The greatest divisor of coprime numbers. “Greatest common divisor. Mutually prime numbers. Learning new material in the form of conversation

In this article we will talk about what coprime numbers are. In the first paragraph, we formulate definitions for two, three or more relatively prime numbers, give several examples and show in which cases two numbers can be considered prime in relation to each other. After this, we move on to the formulation of the main properties and their proofs. In the last paragraph we will talk about a related concept - pairwise prime numbers.

What are coprime numbers

Both two integers and their large quantity. First, let's introduce a definition for two numbers, for which we need the concept of their greatest common divisor. If necessary, repeat the material dedicated to it.

Definition 1

Two such numbers a and b will be mutually prime, the largest common divisor which is equal to 1, i.e. GCD (a , b) = 1 .

From this definition we can conclude that the only positive common divisor of two coprime numbers will be equal to 1. Only two such numbers have two common divisors - one and minus one.

What are some examples of coprime numbers? For example, such a pair would be 5 and 11. They have only one common positive divisor, equal to 1, which confirms their mutual simplicity.

If we take two prime numbers, then in relation to each other they will be mutually prime in all cases, but such mutual relations are also formed between composite numbers. There are cases when one number in a pair of relatively primes is composite, and the second is prime, or they are both composite.

This statement is illustrated by the following example: the composite numbers 9 and 8 form a relatively prime pair. Let's prove this by calculating their greatest common divisor. To do this, we write down all their divisors (we recommend re-reading the article on finding the divisors of a number). For 8 these numbers will be ± 1, ± 2, ± 4, ± 8, and for 9 – ± 1, ± 3, ± 9. We choose from all the divisors the one that will be common and largest - this is one. Therefore, if GCD (8, − 9) = 1, then 8 and - 9 will be coprime to each other.

Coprime numbers are not 500 and 45, since they have another common divisor - 5 (see the article on the criteria for divisibility by 5). Five more than one and is a positive number. Another similar pair could be - 201 and 3, since both of them can be divided by 3, as indicated by the corresponding divisibility sign.

In practice, quite often it is necessary to determine the relative primeness of two integers. Finding out this can be reduced to finding the greatest common divisor and comparing it with unity. It is also convenient to use a table of prime numbers so as not to make unnecessary calculations: if one of the given numbers is in this table, then it is divisible only by one and by itself. Let's look at the solution to such a problem.

Example 1

Condition: find out whether the numbers 275 and 84 are coprime.

Solution

Both numbers clearly have more than one divisor, so we cannot immediately call them relatively prime.

We calculate the greatest common divisor using the Euclidean algorithm: 275 = 84 3 + 23, 84 = 23 3 + 15, 23 = 15 1 + 8, 15 = 8 1 + 7, 8 = 7 1 + 1, 7 = 7 · 1.

Answer: since GCD (84, 275) = 1, then these numbers will be relatively prime.

As we said earlier, the definition of such numbers can be extended to cases when we have not two numbers, but more.

Definition 2

Integers a 1 , a 2 , … , a k , k > 2 will be mutually prime when they have a greatest common divisor equal to 1 .

In other words, if we have a set of some numbers with the largest positive divisor greater than 1, then all these numbers are not mutually inverse with respect to each other.

Let's take a few examples. Thus, the integers − 99, 17 and − 27 are relatively prime. Any number of prime numbers will be coprime with respect to all members of the population, as in the sequences 2, 3, 11, 19, 151, 293 and 667. But the numbers 12, − 9, 900 and − 72 will not be relatively prime, because in addition to unity they will have one more positive divisor equal to 3. The same applies to the numbers 17, 85 and 187: except for one, they can all be divided by 17.

Usually the mutual primeness of numbers is not obvious at first glance; this fact needs proof. To find out whether some numbers are relatively prime, you need to find their greatest common divisor and draw a conclusion based on its comparison with one.

Example 2

Condition: determine whether the numbers 331, 463 and 733 are relatively prime.

Solution

Let's check the table of prime numbers and determine that all three of these numbers are in it. Then their common divisor can only be one.

Answer: all these numbers will be coprime to each other.

Example 3

Condition: give a proof that the numbers − 14, 105, − 2 107 and − 91 are not coprime.

Solution

Let's start by identifying their greatest common divisor, and then make sure that it is not equal to 1. Since negative numbers have the same divisors as the corresponding positive ones, then gcd (− 14, 105, 2 107, − 91) = gcd (14, 105, 2 107, 91). According to the rules that we gave in the article on finding the greatest common divisor, in this case the gcd will be equal to seven.

Answer: seven is greater than one, which means that these numbers are not relatively prime.

Basic properties of coprime numbers

Such numbers have some practically important properties. Let us list them in order and prove them.

Definition 3

If we divide the integers a and b by the number corresponding to their greatest common divisor, we get relatively prime numbers. In other words, a: gcd (a, b) and b: gcd (a, b) will be relatively prime.

We have already proven this property. The proof can be found in the article on the properties of the greatest common divisor. Thanks to it, we can determine pairs of relatively prime numbers: we just need to take any two integers and divide by GCD. As a result, we should get coprime numbers.

Definition 4

A necessary and sufficient condition for the mutual primeness of numbers a and b is the existence of such integers u 0 And v 0, for which equality a · u 0 + b · v 0 = 1 will be true.

Evidence 1

Let's start by proving the necessity of this condition. Let's say we have two relatively prime numbers, denoted a and b. Then, by the definition of this concept, their greatest common divisor will be equal to one. From the properties of gcd we know that for integers a and b there is a Bezout relation a · u 0 + b · v 0 = gcd (a, b). From it we get that a · u 0 + b · v 0 = 1. After this, we need to prove the sufficiency of the condition. Let equality a · u 0 + b · v 0 = 1 will be true in this case if GCD (a, b) divides and a , and b , then it will also divide the sum a · u 0 + b · v 0, and unit, respectively (this can be argued based on the properties of divisibility). And this is only possible if GCD (a, b) = 1, which proves the mutual simplicity of a and b.

In fact, if a and b are coprime, then according to the previous property, the equality will be true a · u 0 + b · v 0 = 1. We multiply both sides by c and get that a · c · u 0 + b · c · v 0 = c. We can divide the first term a · c · u 0 + b · c · v 0 by b, because this is possible for a · c, and the second term is also divisible by b, because one of our factors is equal to b. From this we conclude that the entire sum can be divided by b, and since this sum is equal to c, then c can be divided by b.

Definition 5

If two integers a and b are coprime, then gcd (a c, b) = gcd (c, b).

Evidence 2

Let us prove that GCD (a c, b) will divide GCD (c, b), and after that, that GCD (c, b) will divide GCD (a c, b), which will be proof of the correctness of the equality GCD (a · c , b) = GCD (c , b) .

Since GCD (a · c, b) divides both a · c and b, and GCD (a · c, b) divides b, then it will also divide b · c. This means that GCD (a c, b) divides both a c and b c, therefore, due to the properties of GCD, it also divides GCD (a c, b c), which will be equal to c GCD (a, b ) = c . Therefore, GCD (a · c, b) divides both b and c, therefore, it also divides GCD (c, b).

It can also be said that since GCD (c, b) divides both c and b, then it will divide both c and a c. This means that GCD (c, b) divides both a · c and b, therefore, it also divides GCD (a · c, b).

Thus, gcd (a c, b) and gcd (c, b) mutually divide each other, which means they are equal.

Definition 6

If the numbers are from the sequence a 1 , a 2 , … , a k will be relatively prime with respect to the numbers of the sequence b 1, b 2, …, b m(for natural values ​​of k and m), then their products a 1 · a 2 · … · a k And b 1 · b 2 · … · b m are also relatively prime, in particular, a 1 = a 2 = … = a k = a And b 1 = b 2 = … = b m = b, That a k And b m- mutually simple.

Evidence 3

According to the previous property, we can write equalities of the following form: GCD (a 1 · a 2 · … · a k, b m) = GCD (a 2 · … · a k, b m) = … = GCD (a k, b m) = 1. The possibility of the last transition is ensured by the fact that a k and b m are relatively prime by condition. This means GCD (a 1 · a 2 · … · a k , b m) = 1 .

Let us denote a 1 · a 2 · … · a k = A and obtain that GCD (b 1 · b 2 · … · b m , a 1 · a 2 · … · a k) = GCD (b 1 · b 2 · … · b m , A) = GCD (b 2 · … · b · b m , A) = … = GCD (b m , A) = 1 . This will be true due to the last equality from the chain constructed above. Thus, we have the equality GCD (b 1 · b 2 · … · b m, a 1 · a 2 · … · a k) = 1, with which we can prove the mutual primeness of the products a 1 · a 2 · … · a k And b 1 · b 2 · … · b m

These are all the properties of coprime numbers that we would like to tell you about.

The concept of pairwise prime numbers

Knowing what coprime numbers are, we can formulate a definition of pairwise prime numbers.

Definition 7

Pairwise prime numbers is a sequence of integers a 1 , a 2 , ... , a k , where each number will be relatively prime with respect to the others.

An example of a sequence of pairwise prime numbers would be 14, 9, 17, and − 25. Here all pairs (14 and 9, 14 and 17, 14 and − 25, 9 and 17, 9 and − 25, 17 and − 25) are coprime. Note that the condition of mutual prime is mandatory for pairwise prime numbers, but mutually prime numbers will not be pairwise prime in all cases. For example, in the sequence 8, 16, 5 and 15, the numbers are not such numbers, since 8 and 16 will not be relatively prime.

You should also dwell on the concept of a collection of a certain number of prime numbers. They will always be both mutually and pairwise simple. An example would be the sequence 71, 443, 857, 991. In the case of prime numbers, the concepts of mutual and pairwise prime will coincide.

If you notice an error in the text, please highlight it and press Ctrl+Enter

Prime and composite numbers

Definition 1. Common divisor of several natural numbers name the number that is a divisor of each of these numbers.

Definition 2. The largest common divisor is called greatest common divisor (GCD).

Example 1. The common divisors of the numbers 30, 45 and 60 are the numbers 3, 5, 15.

The greatest common divisor of these numbers is

GCD (30, 45, 10) = 15. Definition 3. If the greatest common divisor of several numbers is 1, then these numbers are called.

mutually prime

Example 2. The numbers 40 and 3 will be coprime numbers, but the numbers 56 and 21 are not coprime because the numbers 56 and 21 have a common factor of 7, which is greater than 1.

Note. If the numerator of a fraction and the denominator of the fraction are mutually prime numbers, then such a fraction is irreducible.

Algorithm for finding the greatest common divisor Let's consider algorithm for finding the greatest common divisor

several numbers in the following example.

Example 3. Find the greatest common divisor of the numbers 100, 750 and 800.

Solution . Let's factor these numbers into prime factors: The prime factor 2 is included in the first factorization to the power of 2, in the second factorization – to the power of 1, and in the third factorization – to the power of 5. Let's denote the smallest = 1 .

The prime factor 3 is included in the first factorization to the power of 0 (in other words, the factor 3 is not included in the first factorization at all), in the second factorization it is included in the power of 1, and in the third factorization – to the power of 0. The prime factor 2 is included in the first factorization to the power of 2, in the second factorization – to the power of 1, and in the third factorization – to the power of 5. Let's denote of these powers by the letter b. = 0 .

It's obvious that The prime factor 2 is included in the first factorization to the power of 2, in the second factorization – to the power of 1, and in the third factorization – to the power of 5. b The prime factor 5 is included in the first factorization to the power of 2, in the second factorization – to the power of 3, and in the third factorization – to the power of 2. = 2 .

Let's denote

of these powers by the letter c.

It's obvious that
c
Finished works

DEGREE WORKS

Much has already passed and now you are a graduate, if, of course, you write your thesis on time. But life is such a thing that only now it becomes clear to you that, having ceased to be a student, you will lose all the student joys, many of which you have never tried, putting everything off and putting it off until later. And now, instead of catching up, you're working on your thesis? There is an excellent solution: download the thesis you need from our website - and you will instantly have a lot of free time! Theses have been successfully defended at leading universities of the Republic of Kazakhstan. Cost of work from 20,000 tenge COURSE WORKS The course project is the first serious practical work. It is with the writing of the coursework that preparation for development begins.
diploma projects

. If a student learns to correctly present the content of a topic in a course project and format it competently, then in the future he will not have problems either with writing reports or with compiling

theses , nor with performing other practical tasks. In order to assist students in writing this type of student work and to clarify questions that arise during its preparation, in fact, this information section was created. Cost of work from 2,500 tenge MASTER'S DISSERTATIONS Currently in higher
educational institutions
In Kazakhstan and the CIS countries, the level of higher education is very common

vocational education

After completing any type of student internship (educational, industrial, pre-graduation), a report is required. This document will be confirmation practical work student and the basis for forming an assessment for practice. Usually, in order to draw up a report on an internship, you need to collect and analyze information about the enterprise, consider the structure and work routine of the organization in which the internship is taking place, draw up a calendar plan and describe your practical activities.
We will help you write a report on your internship, taking into account the specifics of the activities of a particular enterprise.

Competition for young teachers

Bryansk region

“Pedagogical debut – 2014”

2014-2015 academic year

Reinforcement lesson in mathematics in 6th grade

on the topic “GCD. Mutually prime numbers"

Place of work:MBOU "Glinishchevskaya Secondary School" of Bryansk District

Goals:

Educational:

• Consolidate and systematize the studied material;
• Practice the skills of decomposing numbers into prime factors and finding gcd;
• Test students' knowledge and identify gaps;

Educational:

• Promote development logical thinking students, speech and thinking skills;
• Contribute to the development of the ability to notice patterns;
• Contribute to improving the level of mathematical culture;

Educational:

• Promote interest in mathematics; the ability to express one’s thoughts, listen to others, defend one’s point of view;
• fostering independence, concentration, and concentration;
• instill the skills of accuracy in notebook keeping.

Lesson type: lesson of generalization and systematization of knowledge.

Teaching methods : explanatory and illustrative, independent work.

Equipment: computer, screen, presentation, handouts.

During the classes:

1. Organizing time.

“The bell rang and fell silent - the lesson begins.

You sat down quietly at your desks, everyone looked at me.

Wish each other success with your eyes.

And forward to new knowledge.”

Friends, on the tables you see the “Score Sheet”, i.e. In addition to my assessment, you will evaluate yourself by completing each task.

Evaluation paper

Guys, what topic have you studied over several lessons? (We learned to find the greatest common divisor).

What do you think we will do today? Formulate the topic of our lesson. (Today we will continue working with the greatest common divisor. The topic of our lesson is “Greatest common divisor”. In this lesson we will find the greatest common divisor of several numbers, and solve problems using knowledge about finding the greatest common divisor.).

Open your notebooks, write down the number, Classwork and the topic of the lesson: “Greatest common divisor. Mutually prime numbers.”

1. Updating knowledge

A few theoretical questions

Are the statements true? "Yes" - __; "No" - /\. Slide 3-4

• A prime number has exactly two divisors; (right)
• 1 is a prime number; (not true)
• The smallest two-digit prime number is 11; (right)
• The largest two-digit composite number is 99; (right)
• Numbers 8 and 10 are coprime (not true)
• Some composite numbers cannot be factorized; (not true).

Key: _ /\ _ _/\ /\.

Assessed your oral work on the score sheet.

1. Systematization of knowledge

Today in our lesson there will be a little magic.

Where does magic happen? (in a fairy tale)

Guess from the picture which fairy tale we will find ourselves in. ( Slide 5 ) Tale of Geese and Swans. Absolutely right. Well done. Now let's all try to remember the content of this fairy tale together. The chain is very brief.

There lived a man and a woman. They had a daughter and a little son. The father and mother went to work and asked their daughter to look after her brother.

She sat my brother down on the grass under the window, and she ran outside, started playing, and took a walk. When the girl returned, her brother was no longer there. She started looking for him, she screamed, called him, but no one responded. She ran out into an open field and just saw: swan geese darted in the distance and disappeared behind the dark forest. Then the girl realized that they had taken her brother away. She had known for a long time that swan geese carried away small children.

She rushed after them. On the way she met a stove, an apple tree, and a river. But our river is not a milk river on the banks of jelly, but an ordinary one, in which there are very, very many fish. None of them suggested where the geese flew, because she herself did not fulfill their requests.

For a long time the girl ran through the fields and forests. The day is already approaching evening, suddenly she sees a hut standing on chicken legs, with one window, turning around itself. In the hut, old Baba Yaga is spinning a tow. And her brother is sitting on the bench by the window. The girl did not say that she came for her brother, but lied, saying that she got lost. If it weren’t for the little mouse she fed with porridge, Baba Yaga would have fried it in the oven and eaten it. The girl quickly grabbed her brother and ran home. The geese and swans noticed them and flew after them. And whether they get home safely - everything now depends on us, guys. Let's continue the story.

They ran and ran and reached the river. They asked the river to help.

But the river will help them hide only if you guys “catch” all the fish.

Now you will work in pairs. I give each pair an envelope - a net in which three fish are entangled. Your task is to get all the fish, write down No. 1 and solve

Fish tasks. Prove that the numbers are coprime

1) 40 and 15 2) 45 and 49 3) 16 and 21

Peer review. Pay attention to the evaluation criteria. Slide 6-7

Generalization: How to prove that numbers are relatively prime?

Rated it.

Well done. Helped a girl and a boy. The river sheltered them under its bank. Geese-swans flew past.

As a token of gratitude, the Boy will give you a physical minute (video) Slide 9

In what case will the apple tree hide them?

If a girl tries her forest apple.

Right. Let's all “eat” forest apples together. And the apples on it are not simple, with unusual tasks, it’s called LOTTO. We “eat” large apples one per group, i.e. We work in groups. Find the GCD in each cell on the small cards for the answer. When all the cells are closed, turn the cards over and you should get a picture.

Quests on forest apples

Find GCD:

Check: I go through the rows and check the picture

Generalization: What needs to be done to find GCD?

Well done. The apple tree shaded them with branches and covered them with leaves. The geese and swans lost them and flew on. So what is next?

They ran again. They weren't far away, and then the geese saw them, started beating with their wings, and wanted to snatch their brother out of his hands. They reached the stove. The stove will hide them if the girl tries the rye pie.

Let's help the girl.Options assignment, test

TEST

Subject

Option 1

1. Which numbers are the common factors of 24 and 16?

1) 4, 8; 2) 6, 2, 4;

3) 2, 4, 8; 4) 8, 6.

1. Is the number 9 the greatest common divisor of the numbers 27 and 36?

1. Yes; 2) no.

1. Given the numbers 128, 64 and 32. Which one is greatest divisor all three numbers?

1) 128; 2) 64; 3) 32.

1. Are the numbers 7 and 418 relatively prime?

1) yes; 2) no.

1) 5 and 25;

2) 64 and 2;

3) 12 and 10;

4) 100 and 9.

TEST

Subject : NOD. Mutually prime numbers.

Option 1

1. Which numbers are the common factors of 18 and 12?

1) 9, 6, 3; 2) 2, 3, 4, 6;

3) 2, 3; 4) 2, 3, 6.

1. Is the number 4 the greatest common divisor of the numbers 16 and 32?

1. Yes; 2) no.

1. Given the numbers 300, 150 and 600. Which one is the greatest divisor of all three numbers?

1) 600; 2) 150; 3) 300.

1. Are the numbers 31 and 44 relatively prime?

1) yes; 2) no.

1. Which numbers are relatively prime?

1) 9 and 18;

2) 105 and 65;

3) 44 and 45;

4) 6 and 16.

Examination. Self-test from the slide. Evaluation criteria. Slide 10-11

Well done. We ate the pies. The girl and her brother sat down in the stomata and hid. The swan geese flew and flew, screamed and shouted, and flew away empty-handed to Baba Yaga.

The girl thanked the stove and ran home.

Soon father and mother came home from work.

Lesson summary. While we were helping the girl and the boy, what topics did we repeat? (Finding the gcd of two numbers, coprime numbers.)

How to find the gcd of several natural numbers?

How to prove that numbers are relatively prime?

During the lesson, I gave you grades for each assignment and you graded yourself. After comparing them, it will be exhibited GPA per lesson.

Reflection.

Dear friends! To summarize the lesson, I would like to hear your opinion about the lesson.

• What was interesting and instructive in the lesson?
• Can I be sure that you can cope with tasks of this type?
• Which tasks turned out to be the most difficult?
• What knowledge gaps were revealed during the lesson?
• What problems did this lesson create?
• How do you assess the role of a teacher? Did it help you acquire the skills and knowledge to solve problems of this type?

Glue apples onto the tree. Whoever completed all the tasks and everything was clear - glue a red apple. Those who had a question – green, those who didn’t understand – yellow. Slide 12

Is the statement true? The smallest two-digit prime number is 11

Is the statement true? The largest two-digit composite number is 99

Is the statement true? Numbers 8 and 10 are coprime

Is the statement true? Some composite numbers cannot be factorized

Key to the dictation: _ /\ _ _ /\ /\ Evaluation criteria No errors – “5” 1-2 errors – “4” 3 errors – “3” More than three – “2”

Prove that the numbers 16 and 21 are coprime 3 Prove that the numbers 40 and 15 are coprime Prove that the numbers 45 and 49 are coprime 2 1 40=2·2·2·5 15=3·5 GCD(40; 15) =5, numbers are not coprime 45=3·3·5 49=7·7 gcd(45, 49)=, numbers are coprime 16=2·2·2·2 21=3·7 gcd(45, 49) =1, numbers are relatively prime

Evaluation criteria No errors – “5” 1 error – “4” 2 errors – “3” More than two – “2”

Group 1 GCD(48.84)= GCD(60.48)= GCD(12.15)= GCD(15.20)= Group 3 GCD(123.72)= GCD(120.96)= GCD(45, 30)= GCD(15.9)= 2nd group GCD(60.80)= GCD(80.64)= GCD(50.30)= GCD(12.16)= 4th group GCD(90.72)= GCD (15,100)= GCD (14,42)= GCD(34,51)=

Tasks from the stove B1 3 2. 1 3. 3 4. 1 5. 4 B2 4 2. 2 3. 2 4. 1 5. 3

Evaluation criteria No errors – “5” 1-2 errors – “4” 3 errors – “3” More than three – “2”

Reflection was all clear to me, I coped with all the tasks, there were minor difficulties, but I coped with them, there were a few questions left