The greatest divisor of coprime numbers. Greatest common divisor, coprime numbers. Mutually prime numbers"

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: _ /\ _ _/\ /\.

Evaluate your oral performance on a 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:

1 group

2nd group

GCD(48,84)=

gcd (60.48)=

GCD(60,80)=

gcd(80.64)=

GCD (12,15)=

gcd(15,20)=

gcd(50.30)=

GCD (12,16)=

3 group

4 group

GCD (123.72)=

gcd(120.96)=

gcd(90.72)=

gcd(15;100)=

GCD(45,30)=

gcd(15.9)=

GCD(14,42)=

GCD (34.51)=

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 the greatest divisor of 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 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


Remember!

If a natural number is divisible only by 1 and itself, then it is called prime.

Any natural number is always divisible by 1 and itself.

The number 2 is the smallest prime number. This is the only even prime number; all other prime numbers are odd.

There are many prime numbers, and the first among them is the number 2. However, there is no last prime number. In the “For Study” section you can download a table of prime numbers up to 997.

But many natural numbers are also divisible by other natural numbers.

For example:

  • the number 12 is divisible by 1, by 2, by 3, by 4, by 6, by 12;
  • The number 36 is divisible by 1, by 2, by 3, by 4, by 6, by 12, by 18, by 36.

The numbers by which the number is divisible by a whole (for 12 these are 1, 2, 3, 4, 6 and 12) are called divisors of the number.

Remember!

The divisor of a natural number a is a natural number that divides the given number “a” without a remainder.

A natural number that has more than two divisors is called composite.

Please note that the numbers 12 and 36 have common factors.

These numbers are: 1, 2, 3, 4, 6, 12.

Remember!

The greatest divisor of these numbers is 12. The common divisor of two given numbers “a” and “b” is the number by which both given numbers “a” and “b” are divided without remainder.

Greatest common divisor:

(GCD) of two given numbers “a” and “b” is the largest number by which both numbers “a” and “b” are divided without a remainder.

Briefly, the greatest common divisor of the numbers “a” and “b” is written as follows

GCD (a; b) .

Example: gcd (12; 36) = 12.

Divisors of numbers in the solution record are denoted by the capital letter “D”.

D (7) = (1, 7)

D (9) = (1, 9) GCD (7; 9) = 1.

Remember!

The numbers 7 and 9 have only one common divisor - the number 1. Such numbers are called

coprime numbers

Coprime numbers

  1. - these are natural numbers that have only one common divisor - the number 1. Their gcd is 1.

How to find the greatest common divisor

To find the gcd of two or more natural numbers you need:


  1. decompose the divisors of numbers into prime factors;
    28 = It is convenient to write calculations using a vertical bar. To the left of the line we first write down the dividend, to the right - the divisor. Next, in the left column we write down the values ​​of the quotients.

    Let's explain it right away with an example. Let's factor the numbers 28 and 64 into prime factors.

  2. We emphasize the same prime factors in both numbers.
    2 2 7

    64 = 2 2 2 2 2 2

Find the product of identical prime factors and write down the answer;

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

Either two integers or more of them can be mutually prime. 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 greatest common divisor of 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 is greater than one and is 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 given numbers is in this table, which means it is divisible only by one and 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 in this case 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


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 coursework that preparation for the development of diploma projects begins. 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 the implementation of others 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, which follows a bachelor's degree - a master's degree. In the master's program, students study with the aim of obtaining a master's degree, which is recognized in most countries of the world more than a bachelor's degree, and is also recognized by foreign employers. The result of master's studies is the defense of a master's thesis.
We will provide you with up-to-date analytical and textual material, the price includes 2 science articles and abstract.
Cost of work from 35,000 tenge

PRACTICE REPORTS

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 the 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.

Common factors

Example 1

Find the common divisors of the numbers $15$ and $–25$.

Solution.

Divisors of the number $15: 1, 3, 5, 15$ and their opposites.

Divisors of the number $–25: 1, 5, 25 $ and their opposites.

Answer: the numbers $15$ and $–25$ have common divisors of the numbers $1, 5$ and their opposites.

According to the properties of divisibility, the numbers $−1$ and $1$ are divisors of any integer, which means that $−1$ and $1$ will always be common divisors for any integers.

Any set of integers will always have at least $2$ common divisors: $1$ and $−1$.

Note that if the integer $a$ is a common divisor of some integers, then -a will also be a common divisor for these numbers.

Most often in practice they are limited to only positive divisors, but do not forget that every integer opposite to a positive divisor will also be a divisor given number.

Determining the Greatest Common Divisor (GCD)

According to the properties of divisibility, every integer has at least one divisor other than zero, and the number of such divisors is finite. In this case, the common divisors of the given numbers are also finite. Of all the common divisors of given numbers, the greatest number can be identified.

If all given numbers are equal to zero, it is impossible to determine the greatest common divisor, because zero is divisible by any integer, of which there are an infinite number.

The greatest common divisor of the numbers $a$ and $b$ in mathematics is denoted by $GCD(a, b)$.

Example 2

Find the gcd of the integers 412$ and $–30$..

Solution.

Let's find the divisors of each number:

$12$: numbers $1, 3, 4, 6, 12$ and their opposites.

$–30$: numbers $1, 2, 3, 5, 6, 10, 15, 30$ and their opposites.

The common divisors of the numbers $12$ and $–30$ are $1, 3, 6$ and their opposites.

$GCD(12, –30)=6$.

You can determine the GCD of three or more integers in the same way as determining the GCD of two numbers.

GCD of three or more integers is the largest integer that divides all numbers at the same time.

Denote the greatest divisor of $n$ numbers $GCD(a_1, a_2, …, a_n)= b$.

Example 3

Find the gcd of three integers $–12, 32, 56$.

Solution.

Let's find all the divisors of each number:

$–12$: numbers $1, 2, 3, 4, 6, 12$ and their opposites;

$32$: numbers $1, 2, 4, 8, 16, 32$ and their opposites;

$56$: numbers $1, 2, 4, 7, 8, 14, 28, 56$ and their opposites.

The common divisors of the numbers $–12, 32, 56$ are $1, 2, 4$ and their opposites.

Let's find the largest of these numbers by comparing only the positive ones: $1

$GCD(–12, 32, 56)=4$.

In some cases, the gcd of integers can be one of these numbers.

Coprime numbers

Definition 3

Integers $a$ and $b$ – relatively prime, if $GCD(a, b)=1$.

Example 4

Show that the numbers $7$ and $13$ are relatively prime.