Nod and nok of numbers are the greatest common divisor and least common multiple of several numbers. Nod and nok of three or more numbers Nod definition examples

Definition. The largest natural number by which the numbers a and b are divided without remainder is called greatest common divisor (GCD) these numbers.

Let's find the greatest common divisor of the numbers 24 and 35.
The divisors of 24 are the numbers 1, 2, 3, 4, 6, 8, 12, 24, and the divisors of 35 are the numbers 1, 5, 7, 35.
We see that the numbers 24 and 35 have only one common divisor - the number 1. Such numbers are called mutually prime.

Definition. Natural numbers are called mutually prime, if their greatest common divisor (GCD) is 1.

Greatest Common Divisor (GCD) can be found without writing out all the divisors of the given numbers.

Factoring the numbers 48 and 36, we get:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
From the factors included in the expansion of the first of these numbers, we cross out those that are not included in the expansion of the second number (i.e., two twos).
The factors remaining are 2 * 2 * 3. Their product is equal to 12. This number is the greatest common divisor of the numbers 48 and 36. The greatest common divisor of three or more numbers is also found.

To find greatest common divisor

2) from the factors included in the expansion of one of these numbers, cross out those that are not included in the expansion of other numbers;
3) find the product of the remaining factors.

If all given numbers are divisible by one of them, then this number is greatest common divisor given numbers.
For example, the greatest common divisor of the numbers 15, 45, 75 and 180 is the number 15, since all other numbers are divisible by it: 45, 75 and 180.

Least common multiple (LCM)

Definition. Least common multiple (LCM) natural numbers a and b is the smallest natural number that is a multiple of both a and b. The least common multiple (LCM) of the numbers 75 and 60 can be found without writing down the multiples of these numbers in a row. To do this, let's factor 75 and 60 into prime factors: 75 = 3 * 5 * 5, and 60 = 2 * 2 * 3 * 5.
Let's write down the factors included in the expansion of the first of these numbers, and add to them the missing factors 2 and 2 from the expansion of the second number (i.e., we combine the factors).
We get five factors 2 * 2 * 3 * 5 * 5, the product of which is 300. This number is the least common multiple of the numbers 75 and 60.

They also find the least common multiple of three or more numbers.

To find least common multiple several natural numbers, you need:
1) factor them into prime factors;
2) write down the factors included in the expansion of one of the numbers;
3) add to them the missing factors from the expansions of the remaining numbers;
4) find the product of the resulting factors.

Note that if one of these numbers is divisible by all other numbers, then this number is the least common multiple of these numbers.
For example, the least common multiple of the numbers 12, 15, 20, and 60 is 60 because it is divisible by all of those numbers.

Pythagoras (VI century BC) and his students studied the question of the divisibility of numbers. They called a number equal to the sum of all its divisors (without the number itself) a perfect number. For example, the numbers 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) are perfect. The next perfect numbers are 496, 8128, 33,550,336. The Pythagoreans only knew the first three perfect numbers. The fourth - 8128 - became known in the 1st century. n. e. The fifth - 33,550,336 - was found in the 15th century. By 1983, 27 perfect numbers were already known. But scientists still don’t know whether there are odd perfect numbers or whether there is a largest perfect number.
The interest of ancient mathematicians in prime numbers is due to the fact that any number is either prime or can be represented as a product of prime numbers, i.e. prime numbers are like bricks from which the rest of the natural numbers are built.
You probably noticed that prime numbers in the series of natural numbers occur unevenly - in some parts of the series there are more of them, in others - less. But the further we move along the number series, the less common prime numbers are. The question arises: is there a last (largest) prime number? The ancient Greek mathematician Euclid (3rd century BC), in his book “Elements”, which was the main textbook of mathematics for two thousand years, proved that there are infinitely many prime numbers, i.e. behind every prime number there is an even greater prime number.
To find prime numbers, another Greek mathematician of the same time, Eratosthenes, came up with this method. He wrote down all the numbers from 1 to some number, and then crossed out one, which is neither a prime nor a composite number, then crossed out through one all the numbers coming after 2 (numbers that are multiples of 2, i.e. 4, 6 , 8, etc.). The first remaining number after 2 was 3. Then, after two, all numbers coming after 3 (numbers that were multiples of 3, i.e. 6, 9, 12, etc.) were crossed out. in the end only the prime numbers remained uncrossed.

To find the GCD (greatest common divisor) of two numbers you need to:

2. Find (underline) all common prime factors in the resulting expansions.

3. Find the product of common prime factors.

To find the LCM (least common multiple) of two numbers you need:

1. Divide the given numbers into prime factors.

2. The expansion of one of them is supplemented with those factors of the expansion of the other number that are not in the expansion of the first.

3. Calculate the product of the resulting factors.

Finding gcd

GCD is the greatest common divisor.

To find the greatest common divisor of several numbers you need:

• determine the factors common to both numbers;
• find the product of common factors.

An example of finding GCD:

Let's find the gcd of numbers 315 and 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Let’s write down the factors common to both numbers:

3. Find the product of common factors:

GCD(315, 245) = 5 * 7 = 35.

Answer: GCD(315, 245) = 35.

Finding the NOC

LCM is the least common multiple.

To find the least common multiple of several numbers you need:

• factor numbers into prime factors;
• write down the factors included in the expansion of one of the numbers;
• Let’s add to them the missing factors from the expansion of the second number;
• find the product of the resulting factors.

An example of finding the LOC:

Let's find the LCM of the numbers 236 and 328:

1. Let's factor the numbers into prime factors:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Let’s write down the factors included in the expansion of one of the numbers and add to them the missing factors from the expansion of the second number:

2; 2; 59; 2; 41.

3. Find the product of the resulting factors:

LOC(236, 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Answer: LCM(236, 328) = 19352.

The greatest common factor is another metric that makes working with fractions easier. Very often, calculations result in fractions with very large numerator and denominator values. It is possible to reduce such numbers step by step, but it is extremely time consuming, so it is easier to immediately find a GCD and reduce it by it. Let's look at the topic in more detail.

What is GCD?

The greatest common divisor (GCD) of a series of numbers is the largest number by which each of the numbers in the series can be divided without a remainder.

How to find GCD?

In order to find the gcd, it is necessary to decompose each of the numbers into prime factors and isolate the common part.

They didn’t come up with a special formula for this, but there is a calculation algorithm.

Let's give an example of finding the greatest common divisor of two natural numbers: 540 and 252. Let's factor 640 into prime factors. The sequence of actions is as follows:

• Divide the number by the smallest possible prime number. That is, if a number can be divided by 2, 3 or 5, then you first need to divide by 5. Just so as not to get confused.
• We divide the resulting result by the smallest possible prime number.
• We repeat the division of each result obtained until we get a prime number.

Now let's carry out the same procedure in practice.

• 540: 2=270
• 270:2=135
• 135: 3 =45
• 45: 3=15
• 15: 5 = 3

Let's write the result as the equality 540=2*2*3*3*3*5. In order to write down the result, you need to multiply the last resulting number by all divisors.

Let's do the same with the number 252:

• 252: 2=126
• 126: 2=63
• 63: 3=21
• 21: 3 = 7

Let's write down the result: 252=2*2*3*3*7.

Each expansion has the same numbers. Let's find them, these are two numbers 2 and two numbers 3. Only 7 and 3*5 differ.

In order to find the GCD you need to multiply the common factors. That is, there will be two twos and two threes in the work.

GCD=2*2*3*3=36

How can you use this?

Task: reduce the fraction $$252\over540$$.

We have already found the gcd for these two numbers, now we will simply use the already calculated value.

Reduce the numerator and denominator of the fraction by 36 and get the answer.

$$(252\over540) =(7\over15)$$ - to quickly reduce, just look at the decomposition of numbers.

If 540=2*2*3*3*3*5, and GCD=36=2*2*3*3, then 540 = 36*3*5. And if we divide 540 by 36, we get 3*5=15.

Without GCD, we would have to write abbreviations in one long line. In addition, there are times when it is not clear whether a fraction can be reduced at all. For such situations, mathematics came up with the decomposition of numbers into prime factors and gcd.

What have we learned?

We learned what the greatest common divisor of a pair of numbers is, figured out how to use the exponent in practice, solved the problem of finding GCD and using GCD to reduce fractions. We realized that using GCD you can more easily and quickly reduce cumbersome fractions by finding the GCD for the numerator and denominator.

Test on the topic

Article rating

Average rating: 4.3. Total ratings received: 204.

One of the tasks that poses a problem for modern schoolchildren, who are accustomed to using calculators built into gadgets appropriately and inappropriately, is finding the greatest common divisor (GCD) of two or more numbers.

It is impossible to solve any mathematical problem if you do not know what is actually being asked. To do this you need to know what this or that expression means., used in mathematics.

General concepts and definitions

Need to know:

1. If a certain number can be used to count various objects, for example, nine pillars, sixteen houses, then it is natural. The smallest of them will be one.
2. When a natural number is divided by another natural number, the smaller number is said to be a divisor of the larger number.
3. If two or more different numbers are divisible by a certain number without a remainder, then they say that the latter will be their common divisor (CD).
4. The largest of the ODs is called the greatest common divisor (GCD).
5. In this case, when a number has only two natural divisors (itself and one), it is called prime. The smallest among them is two, and it is also the only even number in their series.
6. If two numbers have a maximum common divisor of one, then they will be relatively prime.
7. A number that has more than two divisors is called composite.
8. The process of finding all the prime factors that, when multiplied among themselves, will give the product the initial value in mathematics is called decomposition into prime factors. Moreover, identical factors in the expansion can appear more than once.

The following notations are accepted in mathematics:

1. Divisors D (45) = (1;3;5;9;45).
2. OD (8;18) = (1;2).
3. GCD (8;18) = 2.

Different ways to find GCD

The easiest way to answer the question is how to find gcd in the case where the smaller number is a divisor of the larger one. In such a case, it will be the greatest common divisor.

For example, GCD (15;45) = 15, GCD (48;24) = 24.

But such cases in mathematics are very rare, therefore, in order to find GCD, more complex techniques are used, although checking this option before starting work is still highly recommended.

Method of decomposition into simple factors

If you need to find the gcd of two or more different numbers, it is enough to decompose each of them into simple factors, and then carry out the process of multiplying those of them that are present in each of the numbers.

Example 1

Let's look at how to find GCD 36 and 90:

1. 36 = 1*2*2*3*3;
2. 90 = 1*2*3*3*5;

GCD (36;90) = 1*2*3*3 = 18.

Now let's see how to find the same thing in case of three numbers, let's take 54 as an example; 162; 42.

We already know how to decompose 36, let’s figure out the rest:

1. 162 = 1*2*3*3*3*3;
2. 42 = 1*2*3*7;

Thus, gcd (36;162;42) = 1*2*3 = 6.

It should be noted that it is completely optional to write a unit in the expansion.

Let's consider a way how to simply factor into prime factors, to do this, we will write the number we need on the left, and on the right we will write simple divisors.

Columns can be separated using either a division sign or a simple vertical line.

1. 36 / 2 we will continue our division process;
2. 18/2 further;
3. 9/3 and again;
4. 3/3 is now quite elementary;
5. 1 - the result is ready.

Required 36 = 2*2*3*3.

Euclidean way

This option has been known to mankind since the times of ancient Greek civilization; it is simpler in many ways, and is attributed to the great mathematician Euclid, although very similar algorithms were used earlier. This method is to use the following algorithm, we divide the larger number with a remainder by the smaller one. Then we divide our divisor by the remainder and continue to do this in a circle until a complete division occurs. The last value will turn out to be the desired greatest common divisor.

Let's give an example of using this algorithm:

Let's try to find out what GCD the 816 and 252 have:

1. 816 / 252 = 3 and the remainder is 60. Now we divide 252 by 60;
2. 252 / 60 = 4 the remainder this time will be 12. Let's continue our circular process, divide sixty by twelve;
3. 60 / 12 = 5. Since this time we did not receive any remainder, we have a ready result, twelve will be the value we are looking for.

So, at the end of our process we got gcd (816;252) = 12.

Actions if it is necessary to determine the GCD if more than two values ​​are specified

We have already figured out what to do in the case when there are two different numbers, now we will learn how to act if there are any 3 or more.

Despite all its apparent complexity, this task will no longer cause problems for us. Now we select any two numbers and determine the value we are looking for. The next step is to find the gcd of the obtained result and the third of the given values. Then we again act according to the principle already known to us for the fourth fifth and so on.

Conclusion

So, despite the seemingly great complexity of the task initially set before us, in fact everything is simple, the main thing is to be able to carry out the division process accurately and adhere to any of the two algorithms described above.

Although both methods are quite acceptable, in a secondary school the first method is much more often used. This is due to the fact that factorization will be needed when studying the next educational topic - determining the greatest common multiple (LCM). But it’s still worth noting once again that the use of the Euclidean algorithm cannot in any way be considered erroneous.

Video

With this video you can learn how to find the greatest common divisor.

Let's consider two main methods of finding GCD in two main ways: using the Euclidean algorithm and by decomposing into prime factors. Let's apply both methods for two, three or more numbers.

Euclidean algorithm for finding GCD

The Euclidean algorithm makes it easy to calculate the greatest common factor of two positive numbers. We presented the formulations and proof of the Euclid algorithm in the section “Greatest common divisor: determinant, examples.”

The essence of the algorithm is to sequentially carry out division with a remainder, during which a series of equalities of the form are obtained:

a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

We can finish division when r k + 1 = 0, wherein r k = gcd (a , b).

Example 1

64 And 48 .

Solution

Let's introduce the following notations: a = 64, b = 48.

Based on the Euclidean algorithm, we will carry out division 64 on 48 .

We get 1 and the remainder 16. It turns out that q 1 = 1, r 1 = 16.

The second step is to divide 48 by 16, we get 3. That is q 2 = 3, A r 2 = 0 . Thus, the number 16 is the greatest common divisor for the numbers from the condition.

Answer: GCD (64, 48) = 16.

Example 2

What is the GCD of numbers? 111 And 432 ?

Solution

We divide 432 on 111 . According to the Euclidean algorithm, we obtain the chain of equalities 432 = 111 · 3 + 99, 111 = 99 · 1 + 12, 99 = 12 · 8 + 3, 12 = 3 · 4.

Thus, the greatest common divisor of numbers is 111 And 432 – this is 3.

Answer: GCD (111, 432) = 3.

Example 3

Find the greatest common divisor of the numbers 661 and 113.

Solution

Let's sequentially divide the numbers and get GCD (661 , 113) = 1 . This means that 661 and 113 are relatively prime numbers. We could figure this out before starting the calculation if we consulted a table of prime numbers.

Answer: GCD (661, 113) = 1.

Finding GCD by factoring numbers into prime factors

In order to find the greatest common divisor of two numbers using the factorization method, it is necessary to multiply all the prime factors that are obtained by factoring these two numbers and are common to them.

Example 4

If we factor the numbers 220 and 600 into prime factors, we get two products: 220 = 2 2 5 11 And 600 = 2 2 2 3 5 5. The common factors in these two products are 2, 2 and 5. This means that GCD (220, 600) = 2 2 5 = 20.

Example 5

Find the greatest common divisor of numbers 72 And 96 .

Solution

Find all prime factors of numbers 72 And 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

The common prime factors for two numbers are 2, 2, 2 and 3. This means that GCD (72, 96) = 2 2 2 3 = 24.

Answer: GCD (72, 96) = 24.

The rule for finding the greatest common divisor of two numbers is based on the properties of the greatest common divisor, according to which gcd (m a 1, m b 1) = m gcd (a 1, b 1), where m is any positive integer.

Finding the gcd of three or more numbers

Regardless of the number of numbers for which we need to find the GCD, we will follow the same algorithm, which consists of sequentially finding the GCD of two numbers. This algorithm is based on the application of the following theorem: GCD of several numbers a 1 , a 2 , … , a k equal to the number dk, which is found by sequentially calculating the gcd (a 1 , a 2) = d 2, GCD (d 2 , a 3) = d 3 , GCD (d 3 , a 4) = d 4 , … , GCD (d k - 1 , a k) = d k .

Example 6

Find the greatest common divisor of four numbers 78, 294, 570 and 36 .

Solution

Let us introduce the notation: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Let's start by finding the gcd of numbers 78 and 294: d 2 = GCD (78 , 294) = 6 .

Now let's start finding d 3 = GCD (d 2 , a 3) = GCD (6, 570). According to the Euclid algorithm 570 = 6 95. It means that d 3 = GCD (6 , 570) = 6 .

Let's find d 4 = GCD (d 3 , a 4) = GCD (6, 36). 36 divisible by 6 without remainder. This allows us to get d 4 = GCD (6 , 36) = 6 .

d4 = 6, that is, GCD (78 , 294 , 570 , 36) = 6 .

Answer:

Now let's look at another way to calculate GCD for those and more numbers. We can find the gcd by multiplying all the common prime factors of numbers.

Example 7

Calculate the GCD of the numbers 78, 294, 570 and 36 .

Solution

Let's decompose these numbers into prime factors: 78 = 2 3 13, 294 = 2 3 7 7, 570 = 2 3 5 19, 36 = 2 2 3 3.

For all four numbers, the common prime factors will be the numbers 2 and 3.

It turns out that GCD (78, 294, 570, 36) = 2 3 = 6.

Answer: GCD (78, 294, 570, 36) = 6.

Finding GCD of Negative Numbers

If we have to deal with negative numbers, then we can use the moduli of these numbers to find the greatest common divisor. We can do this, knowing the property of numbers with opposite signs: numbers n And -n have the same divisors.

Example 8

Find the gcd of negative integers − 231 And − 140 .

Solution

To perform calculations, we take the modules of the numbers given in the condition. These will be the numbers 231 and 140. Let's write it down briefly: GCD (− 231 , − 140) = GCD (231, 140) . Now we apply the Euclidean algorithm to find prime factors of two numbers: 231 = 140 · 1 + 91 ; 140 = 91 1 + 49 ; 91 = 49 · 1 + 42 ; 49 = 42 1 + 7 and 42 = 7 6. We get that GCD (231, 140) = 7 .

And since GCD (− 231 , − 140) = GCD (231 , 140) , then gcd of numbers − 231 And − 140 equals 7 .

Answer: GCD (− 231, − 140) = 7.

Example 9

Determine the gcd of three numbers − 585, 81 and − 189 .

Solution

Let's replace the negative numbers in the above list with their absolute values, we get GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Then we factor all these numbers into prime factors: 585 = 3 3 5 13, 81 = 3 3 3 3 and 189 = 3 3 3 7. Common to the three numbers are the prime factors 3 and 3. It turns out that GCD (585, 81, 189) = GCD (− 585, 81, − 189) = 9.

Answer: GCD (− 585, 81, − 189) = 9.

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