Find a node and a node of three. Nod and nok of numbers - the greatest common divisor and least common multiple of several numbers

Let's start studying the least common multiple of two or more numbers. In the section, we will give a definition of the term, consider a theorem that establishes a relationship between the least common multiple and the greatest common divisor, and give examples of solving problems.

Common multiples - definition, examples

In this topic, we will be interested only in common multiples of integers other than zero.

Definition 1

Common multiple of integers is an integer that is a multiple of all given numbers. In fact, it is any integer that can be divided by any of the given numbers.

The definition of common multiples refers to two, three, or more integers.

Example 1

According to the definition given above for the number 12, the common multiples are 3 and 2. Also the number 12 will be a common multiple of the numbers 2 , 3 and 4 . The numbers 12 and -12 are common multiples of the numbers ±1, ±2, ±3, ±4, ±6, ±12.

At the same time, the common multiple for the numbers 2 and 3 will be the numbers 12 , 6 , − 24 , 72 , 468 , − 100 010 004 and whole line any others.

If we take numbers that are divisible by the first number of a pair and not divisible by the second, then such numbers will not be common multiples. So, for the numbers 2 and 3, the numbers 16 , − 27 , 5009 , 27001 will not be common multiples.

0 is a common multiple of any set of non-zero integers.

If we recall the property of divisibility with respect to opposite numbers, then it turns out that some integer k will be a common multiple of these numbers in the same way as the number - k . This means that common divisors can be either positive or negative.

Is it possible to find an LCM for all numbers?

The common multiple can be found for any integers.

Example 2

Suppose we are given k integers a 1 , a 2 , … , a k. The number that we get during the multiplication of numbers a 1 a 2 … a k according to the divisibility property, it will be divided by each of the factors that were included in the original product. This means that the product of the numbers a 1 , a 2 , … , a k is the least common multiple of these numbers.

How many common multiples can these integers have?

A group of integers can have a large number of common multiples. In fact, their number is infinite.

Example 3

Suppose we have some number k . Then the product of the numbers k · z , where z is an integer, will be a common multiple of the numbers k and z . Given that the number of numbers is infinite, then the number of common multiples is infinite.

Least Common Multiple (LCM) - Definition, Symbol and Examples

Let's remember the concept the smallest number from given set numbers, which we discussed in the Comparison of Integers section. With this concept in mind, we formulate the definition of the least common multiple, which has the greatest practical significance among all common multiples.

Definition 2

Least common multiple of given integers is the least positive common multiple of these numbers.

The least common multiple exists for any number of given numbers. The abbreviation NOK is the most commonly used to designate a concept in the reference literature. Brief entry least common multiple for numbers a 1 , a 2 , … , a k will look like LCM (a 1 , a 2 , … , a k).

Example 4

The least common multiple of 6 and 7 is 42. Those. LCM(6, 7) = 42. The least common multiple of four numbers - 2 , 12 , 15 and 3 will be equal to 60 . Shorthand will be LCM (- 2 , 12 , 15 , 3) = 60 .

Not for all groups of given numbers, the least common multiple is obvious. Often it has to be calculated.

Relationship between NOC and NOD

Least Common Multiple and Greatest common divisor interconnected. The relationship between concepts is established by the theorem.

Theorem 1

The least common multiple of two positive integers a and b is equal to the product of the numbers a and b divided by the greatest common divisor of the numbers a and b , that is, LCM (a , b) = a b: GCD (a , b) .

Proof 1

Suppose we have some number M which is a multiple of numbers a and b . If the number M is divisible by a , there is also some integer z , under which the equality M = a k. According to the definition of divisibility, if M is also divisible by b, so then a k divided by b.

If we introduce a new notation for gcd (a , b) as d, then we can use the equalities a = a 1 d and b = b 1 · d . In this case, both equalities will be coprime numbers.

We have already established above that a k divided by b. Now this condition can be written as follows:
a 1 d k divided by b 1 d, which is equivalent to the condition a 1 k divided by b 1 according to the properties of divisibility.

According to the property mutual prime numbers, if a 1 and b 1 are mutually prime numbers, a 1 not divisible by b 1 despite the fact that a 1 k divided by b 1, then b 1 should share k.

In this case, it would be appropriate to assume that there is a number t, for which k = b 1 t, and since b1=b:d, then k = b: d t.

Now instead of k put into equality M = a k expression of the form b: d t. This allows us to come to equality M = a b: d t. At t=1 we can get the least positive common multiple of a and b , equal a b: d, provided that the numbers a and b positive.

So we have proved that LCM (a , b) = a b: GCD (a,b).

Establishing a connection between LCM and GCD allows you to find the least common multiple through the greatest common divisor of two or more given numbers.

Definition 3

The theorem has two important consequences:

multiples of the least common multiple of two numbers are the same as common multiples of those two numbers;
the least common multiple of coprime positive numbers a and b is equal to their product.

It is not difficult to substantiate these two facts. Any common multiple of M numbers a and b is defined by the equality M = LCM (a, b) t for some integer value t. Since a and b are coprime, then gcd (a, b) = 1, therefore, LCM (a, b) = a b: gcd (a, b) = a b: 1 = a b.

Least common multiple of three or more numbers

In order to find the least common multiple of several numbers, you must successively find the LCM of two numbers.

Theorem 2

Let's pretend that a 1 , a 2 , … , a k are some integers positive numbers. To calculate the LCM m k these numbers, we need to sequentially calculate m 2 = LCM(a 1 , a 2) , m 3 = NOC(m 2 , a 3) , … , m k = NOC(m k - 1 , a k) .

Proof 2

The first corollary of the first theorem discussed in this topic will help us to prove the correctness of the second theorem. Reasoning is built according to the following algorithm:

common multiples of numbers a 1 and a 2 coincide with multiples of their LCM, in fact, they coincide with multiples of the number m2;
common multiples of numbers a 1, a 2 and a 3 m2 and a 3 m 3;
common multiples of numbers a 1 , a 2 , … , a k coincide with common multiples of numbers m k - 1 and a k, therefore, coincide with multiples of the number m k;
due to the fact that the smallest positive multiple of the number m k is the number itself m k, then the least common multiple of the numbers a 1 , a 2 , … , a k is an m k.

So we have proved the theorem.

If you notice a mistake in the text, please highlight it and press Ctrl+Enter

Finding the least common multiple (LCM) and the greatest common divisor (GCD) of natural numbers.

	2						5
	2						5
	3						3
	5

60=2*2*3*5
75=3*5*5
2) We write out the factors included in the expansion of the first of these numbers and add to them the missing factor 5 from the expansion of the second number. We get: 2*2*3*5*5=300. Found NOC, i.e. this sum = 300. Do not forget the dimension and write the answer:
Answer: Mom gives 300 rubles each.

Definition of GCD: Greatest Common Divisor (GCD) natural numbers a and in name the largest natural number c, to which and a, and b divided without remainder. Those. c is the smallest natural number for which and a and b are multiples.

Reminder: There are two approaches to the definition of natural numbers

numbers used in: enumeration (numbering) of items (first, second, third, ...); - in schools, usually.
indicating the number of items (no pokemon - zero, one pokemon, two pokemon, ...).

Negative and non-integer (rational, real, ...) numbers are not natural. Some authors include zero in the set of natural numbers, others do not. The set of all natural numbers is usually denoted by the symbol N

Reminder: Divisor of a natural number a call the number b, to which a divided without remainder. Multiple of natural number b called a natural number a, which is divided by b without a trace. If number b- number divisor a, then a multiple of b. Example: 2 is a divisor of 4 and 4 is a multiple of 2. 3 is a divisor of 12, and 12 is a multiple of 3.
Reminder: Natural numbers are called prime if they are divisible without remainder only by themselves and by 1. Coprime are numbers that have only one common divisor equal to 1.

Determining how to find GCD in general case: To find GCD (Greatest Common Divisor) Several natural numbers are needed:
1) Break them down into prime factors. (The Prime Number Chart can be very helpful for this.)
2) Write out the factors included in the expansion of one of them.
3) Delete those that are not included in the expansion of the remaining numbers.
4) Multiply the factors obtained in paragraph 3).

Task 2 on (NOK): By the new year, Kolya Puzatov bought 48 hamsters and 36 coffee pots in the city. Fekla Dormidontova, as the most honest girl in the class, was given the task of dividing this property into the largest possible number of gift sets for teachers. What is the number of sets? What is the composition of the sets?

Example 2.1. solving the problem of finding GCD. Finding GCD by selection.
Decision: Each of the numbers 48 and 36 must be divisible by the number of gifts.
1) Write out the divisors 48: 48, 24, 16, 12 , 8, 6, 3, 2, 1
2) Write out the divisors 36: 36, 18, 12 , 9, 6, 3, 2, 1 Choose the greatest common divisor. Op-la-la! Found, this is the number of sets of 12 pieces.
3) Divide 48 by 12, we get 4, divide 36 by 12, we get 3. Do not forget the dimension and write the answer:
Answer: You will get 12 sets of 4 hamsters and 3 coffee pots in each set.

The material presented below is a logical continuation of the theory from the article under the heading LCM - least common multiple, definition, examples, relationship between LCM and GCD. Here we will talk about finding the least common multiple (LCM), and Special attention Let's take a look at the examples. Let us first show how the LCM of two numbers is calculated in terms of the GCD of these numbers. Next, consider finding the least common multiple by factoring numbers into prime factors. After that, we will focus on finding the LCM of three and more numbers, and also pay attention to the calculation of the LCM of negative numbers.

Page navigation.

Calculation of the least common multiple (LCM) through gcd

One way to find the least common multiple is based on the relationship between LCM and GCD. The existing relationship between LCM and GCD allows you to calculate the least common multiple of two positive integers through the known greatest common divisor. The corresponding formula has the form LCM(a, b)=a b: GCM(a, b) . Consider examples of finding the LCM according to the above formula.

Example.

Find the least common multiple of the two numbers 126 and 70 .

Decision.

In this example a=126 , b=70 . Let us use the relationship between LCM and GCD expressed by the formula LCM(a, b)=a b: GCM(a, b). That is, first we have to find the greatest common divisor of the numbers 70 and 126, after which we can calculate the LCM of these numbers according to the written formula.

Find gcd(126, 70) using Euclid's algorithm: 126=70 1+56 , 70=56 1+14 , 56=14 4 , hence gcd(126, 70)=14 .

Now we find the required least common multiple: LCM(126, 70)=126 70: GCM(126, 70)= 126 70:14=630 .

Answer:

LCM(126, 70)=630 .

Example.

What is LCM(68, 34) ?

Decision.

As 68 is evenly divisible by 34 , then gcd(68, 34)=34 . Now we calculate the least common multiple: LCM(68, 34)=68 34: LCM(68, 34)= 68 34:34=68 .

Answer:

LCM(68, 34)=68 .

Note that the previous example fits the following rule for finding the LCM for positive integers a and b : if the number a is divisible by b , then the least common multiple of these numbers is a .

Finding the LCM by Factoring Numbers into Prime Factors

Another way to find the least common multiple is based on factoring numbers into prime factors. If we make a product of all prime factors of these numbers, after which we exclude from this product all common prime factors that are present in the expansions of these numbers, then the resulting product will be equal to the least common multiple of these numbers.

The announced rule for finding the LCM follows from the equality LCM(a, b)=a b: GCM(a, b). Indeed, the product of the numbers a and b is equal to the product of all the factors involved in the expansions of the numbers a and b. In turn, gcd(a, b) is equal to the product all prime factors that are simultaneously present in the expansions of the numbers a and b (which is described in the section on finding GCD using the decomposition of numbers into prime factors).

Let's take an example. Let we know that 75=3 5 5 and 210=2 3 5 7 . Compose the product of all factors of these expansions: 2 3 3 5 5 5 7 . Now we exclude from this product all the factors that are present both in the expansion of the number 75 and in the expansion of the number 210 (such factors are 3 and 5), then the product will take the form 2 3 5 5 7 . The value of this product is equal to the least common multiple of the numbers 75 and 210, that is, LCM(75, 210)= 2 3 5 5 7=1 050.

Example.

After factoring the numbers 441 and 700 into prime factors, find the least common multiple of these numbers.

Decision.

Let's decompose the numbers 441 and 700 into prime factors:

We get 441=3 3 7 7 and 700=2 2 5 5 7 .

Now let's make a product of all the factors involved in the expansions of these numbers: 2 2 3 3 5 5 7 7 7 . Let us exclude from this product all the factors that are simultaneously present in both expansions (there is only one such factor - this is the number 7): 2 2 3 3 5 5 7 7 . Thus, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

Answer:

LCM(441, 700)= 44 100 .

The rule for finding the LCM using the decomposition of numbers into prime factors can be formulated a little differently. If we add the missing factors from the expansion of the number b to the factors from the decomposition of the number a, then the value of the resulting product will be equal to the least common multiple of the numbers a and b.

For example, let's take all the same numbers 75 and 210, their expansions into prime factors are as follows: 75=3 5 5 and 210=2 3 5 7 . To the factors 3, 5 and 5 from the decomposition of the number 75, we add the missing factors 2 and 7 from the decomposition of the number 210, we get the product 2 3 5 5 7 , the value of which is LCM(75, 210) .

Example.

Find the least common multiple of 84 and 648.

Decision.

We first obtain the decomposition of the numbers 84 and 648 into prime factors. They look like 84=2 2 3 7 and 648=2 2 2 3 3 3 3 . To the factors 2 , 2 , 3 and 7 from the decomposition of the number 84 we add the missing factors 2 , 3 , 3 and 3 from the decomposition of the number 648 , we get the product 2 2 2 3 3 3 3 7 , which is equal to 4 536 . Thus, the desired least common multiple of the numbers 84 and 648 is 4,536.

Answer:

LCM(84, 648)=4 536 .

Finding the LCM of three or more numbers

The least common multiple of three or more numbers can be found by successively finding the LCM of two numbers. Recall the corresponding theorem, which gives a way to find the LCM of three or more numbers.

Theorem.

Let positive integers a 1 , a 2 , …, a k be given, the least common multiple m k of these numbers is found in the sequential calculation m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , a k) .

Consider the application of this theorem on the example of finding the least common multiple of four numbers.

Example.

Find the LCM of the four numbers 140 , 9 , 54 and 250 .

Decision.

In this example a 1 =140 , a 2 =9 , a 3 =54 , a 4 =250 .

First we find m 2 \u003d LCM (a 1, a 2) \u003d LCM (140, 9). To do this, using the Euclidean algorithm, we determine gcd(140, 9) , we have 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , therefore, gcd(140, 9)=1 , whence LCM(140, 9)=140 9: LCM(140, 9)= 140 9:1=1 260 . That is, m 2 =1 260 .

Now we find m 3 \u003d LCM (m 2, a 3) \u003d LCM (1 260, 54). Let's calculate it through gcd(1 260, 54) , which is also determined by the Euclid algorithm: 1 260=54 23+18 , 54=18 3 . Then gcd(1 260, 54)=18 , whence LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . That is, m 3 \u003d 3 780.

Left to find m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250). To do this, we find GCD(3 780, 250) using the Euclid algorithm: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Therefore, gcd(3 780, 250)=10 , whence gcd(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . That is, m 4 \u003d 94 500.

So the least common multiple of the original four numbers is 94,500.

Answer:

LCM(140, 9, 54, 250)=94,500.

In many cases, the least common multiple of three or more numbers is conveniently found using prime factorizations of given numbers. In this case, the following rule should be followed. The least common multiple of several numbers is equal to the product, which is composed as follows: the missing factors from the expansion of the second number are added to all the factors from the expansion of the first number, the missing factors from the expansion of the third number are added to the obtained factors, and so on.

Consider an example of finding the least common multiple using the decomposition of numbers into prime factors.

Example.

Find the least common multiple of five numbers 84 , 6 , 48 , 7 , 143 .

Decision.

First, we obtain the expansions of these numbers into prime factors: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 prime factors) and 143=11 13 .

To find the LCM of these numbers, to the factors of the first number 84 (they are 2 , 2 , 3 and 7 ) you need to add the missing factors from the expansion of the second number 6 . The expansion of the number 6 does not contain missing factors, since both 2 and 3 are already present in the expansion of the first number 84 . Further to the factors 2 , 2 , 3 and 7 we add the missing factors 2 and 2 from the expansion of the third number 48 , we get a set of factors 2 , 2 , 2 , 2 , 3 and 7 . There is no need to add factors to this set in the next step, since 7 is already contained in it. Finally, to the factors 2 , 2 , 2 , 2 , 3 and 7 we add the missing factors 11 and 13 from the expansion of the number 143 . We get the product 2 2 2 2 3 7 11 13 , which is equal to 48 048 .

Consider three ways to find the least common multiple.

Finding by Factoring

The first way is to find the least common multiple by factoring the given numbers into prime factors.

Suppose we need to find the LCM of numbers: 99, 30 and 28. To do this, we decompose each of these numbers into prime factors:

For the desired number to be divisible by 99, 30 and 28, it is necessary and sufficient that it includes all the prime factors of these divisors. To do this, we need to take all the prime factors of these numbers to the highest occurring power and multiply them together:

2 2 3 2 5 7 11 = 13 860

So LCM (99, 30, 28) = 13,860. No other number less than 13,860 is evenly divisible by 99, 30, or 28.

To find the least common multiple of given numbers, you need to decompose them into prime factors, then take each prime factor with the largest exponent with which it occurs, and multiply these factors together.

Since coprime numbers have no common prime factors, their least common multiple is equal to the product of these numbers. For example, three numbers: 20, 49 and 33 are coprime. So

LCM (20, 49, 33) = 20 49 33 = 32,340.

The same should be done when looking for the least common multiple of various primes. For example, LCM (3, 7, 11) = 3 7 11 = 231.

Finding by selection

The second way is to find the least common multiple by fitting.

Example 1. When the largest of the given numbers is evenly divisible by other given numbers, then the LCM of these numbers is equal to the larger of them. For example, given four numbers: 60, 30, 10 and 6. Each of them is divisible by 60, therefore:

NOC(60, 30, 10, 6) = 60

In other cases, to find the least common multiple, the following procedure is used:

Determine the largest number from the given numbers.
Next, find numbers that are multiples the largest number, multiplying it by integers in ascending order and checking whether the remaining given numbers are divisible by the resulting product.

Example 2. Given three numbers 24, 3 and 18. Determine the largest of them - this is the number 24. Next, find the numbers that are multiples of 24, checking whether each of them is divisible by 18 and by 3:

24 1 = 24 is divisible by 3 but not divisible by 18.

24 2 = 48 - divisible by 3 but not divisible by 18.

24 3 \u003d 72 - divisible by 3 and 18.

So LCM(24, 3, 18) = 72.

Finding by Sequential Finding LCM

The third way is to find the least common multiple by successively finding the LCM.

The LCM of two given numbers is equal to the product of these numbers divided by their greatest common divisor.

Example 1. Find the LCM of two given numbers: 12 and 8. Determine their greatest common divisor: GCD (12, 8) = 4. Multiply these numbers:

We divide the product into their GCD:

So LCM(12, 8) = 24.

To find the LCM of three or more numbers, the following procedure is used:

First, the LCM of any two of the given numbers is found.
Then, the LCM of the found least common multiple and the third given number.
Then, the LCM of the resulting least common multiple and the fourth number, and so on.
Thus the LCM search continues as long as there are numbers.

Example 2. Find the LCM three data numbers: 12, 8 and 9. The LCM of the numbers 12 and 8 we have already found in the previous example (this is the number 24). It remains to find the least common multiple of 24 and the third given number - 9. Determine their greatest common divisor: gcd (24, 9) = 3. Multiply LCM with the number 9:

We divide the product into their GCD:

So LCM(12, 8, 9) = 72.

GCD is the greatest common divisor.

To find the greatest common divisor of several numbers:

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

An example of finding a GCD:

Find the GCD of the numbers 315 and 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Write out 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:

decompose numbers into prime factors;
write out the factors included in the expansion of one of the numbers;
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 NOC:

Find the LCM of the numbers 236 and 328:

1. We decompose the numbers into prime factors:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. 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:

LCM(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Answer: LCM(236; 328) = 19352.

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

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

3. Find the product of common prime factors.

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

1. Decompose these numbers into prime factors.

2. Supplement the expansion of one of them with those factors of the expansion of the other number, which are not in the expansion of the first.

3. Calculate the product of the obtained factors.