Ticket number 45. Least common multiple of numbers. Its properties and methods of finding. Examples.

Calculating the least common multiple (LCM) using GCD (least common divisor)

One way to find the least common multiple is based on the relationship between LCM and GCD. The existing connection between LCM and GCD allows us to calculate the least common multiple of two positive integers through a known greatest common divisor. The corresponding formula is LCM(a, b)=a b:GCD(a, b) . Let's look at examples of finding the LCM using the given formula.

Example.

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

Solution.

In this example a=126, b=70. Let us use the connection between LCM and GCD, expressed by the formula LCM(a, b)=a b:GCD(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 using the written formula.

We'll find GCD(126, 70) using the Euclidean 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: GCD(126, 70)=126·70:GCD(126, 70)=126·70:14=630.

Answer:

LCM(126, 70)=630.

Example.

What is equal to NOC(68, 34)?

Solution.

Because 68 divisible by 34 , That gcd(68, 34)=34. Now we calculate the least common multiple: GCD(68, 34)=68 34:GCD(68, 34)=68 34:34=68.

Answer:

LCM(68, 34)=68.

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

Finding LCM by factoring numbers

Another way to find the least common multiple is based on factoring numbers into prime factors. If you compose a product from all the prime factors of given numbers, and then exclude from this product all the common prime factors present in the decompositions of the given numbers, then the resulting product will be equal to the least common multiple of the given numbers.

The stated rule for finding the LCM follows from the equality LCM(a, b)=a b:GCD(a, b). Indeed, the product of numbers a And b equal to the product of all factors involved in the expansion of numbers a And b. In turn GCD(a, b) equal to the product of all prime factors simultaneously present in the expansions of numbers a And b(which is written about in the section on finding gcd using factorization of numbers into prime factors).

Let's give an example. Let us know that 75=3·5·5 And 210=2·3·5·7. Let's compose a product from all the factors of these expansions: 2·3·3·5·5·5·7. Now from this product we exclude all the factors present in the expansion of the number 75 and in the expansion of numbers 210 (such multipliers 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, NOC(75, 210)= 2·3·5·5·7=1,050.

Example.

Breaking down the numbers 441 And 700 for prime factors, find the least common multiple of these numbers.

Solution.

Let's break down 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 create a product of all the factors involved in the expansion of these numbers: 2·2·3·3·5·5·7·7·7. Let us exclude from this product all factors that are simultaneously present in both expansions (there is only one such factor - this 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:

NOC(441, 700)= 44 100.

The rule for finding the LCM using factorization of numbers into prime factors can be formulated a little differently. If to the factors from the expansion of a number a add missing factors from number expansion b, 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 factorizations into prime factors are as follows: 75=3·5·5 And 210=2·3·5·7. To factors 3 , 5 And 5 from the expansion of a number 75 2 And 7 from the expansion of a number 210 , we get the product 2·3·5·5·7, whose value is NOC(75, 210).

Example.

Find the least common multiple of numbers 84 And 648 .

Solution.

We first obtain the decompositions of 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 multipliers 2 , 2 , 3 And 7 from the expansion of a number 84 add missing multipliers 2 , 3 , 3 And 3 from the expansion of a number 648 , we get the product 2·2·2·3·3·3·3·7, which is equal 4 536 . Thus, the desired least common multiple of the numbers 84 And 648 equals 4 536 .

Answer:

LCM(84, 648)=4,536.

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

Yandex.RTB R-A-339285-1

Euclidean algorithm for finding GCD

Euclidean's 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, while 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. This 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 Euclid 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

Representation of a number as a product of prime numbers is called by factoring this number into prime factors.

For example, writing 110 = 2 5 11 means that the number 110 is factored into prime factors 2, 5, and 11.

In general, any composite number can be decomposed into prime factors, and with any method the same decomposition is obtained, if you do not take into account the order of the factors. Therefore, representations of the number 110 in the form of a product of 2 · 5 · 11 or a product of 5 · 2 · 11 are, in essence, the same decomposition of the number 110 into prime factors.

When decomposing numbers into prime factors, using the signs of division by 2, 3, 5, etc., let us remember the way to write the decomposition of a number into prime factors. Let us, for example, decompose the number 720 into prime factors. The number 720 is divisible by 2. This means that 2 is one of the prime factors in the decomposition of the number 720. Divide 720 by 2. The number 2 is written to the right of the equal sign, and the quotient 360 is written under the number 720. Number Divide 360 ​​by 2, we get 180. Divide 180 by 2, we get 90, divide 90 by 2, we get 45, divide 45 by 3, we get 15, divide 15 by 3, we get 5. The number 5 is prime, when we divide it by 5 we get 1. Factorization is complete.

720 = 2 2 2 2 3 3 5

The product of identical factors is usually replaced by a power: 720 = 5. This representation of the number 720 is called canonical view this number.

Factoring a number into prime factors is used to find its greatest common divisor and least common multiple.

Let's find, for example, the greatest common divisor and least common multiple of the numbers 3600 and 288.

Let's represent each of these numbers in canonical form.

3600 = 2 · 2 · 2 · 2 · 3 · 3 · 5 · 5 = · · ; 288 = 2 2 2 2 2 3 3 =

In the prime factorization of the greatest common divisor of the numbers 3600 and 288, all must be included multiply common primes, which are contained in the expansions of these numbers, and each of them must be taken from the lowest rate with which it enters both expansions. Therefore, the expansion of the greatest common divisor of the numbers 3600 and 288 will include the factors and . So D (3600? 288) = · = 144.

The prime factorization of the least common multiple of 3600 and 288 must include all the prime factors contained in at least in one from the expansions of the numbers 3600 and 288 and each of them must be taken with the highest rate included in both expansions of these numbers. Therefore, the expansion of the least common multiple of 3600 and 288 will include the factors , , 5. This means



K (3600, 288) = · · 5 = 7200.

In general, to find the greatest common divisor of given numbers:

2) We form the product of prime factors common to all given numbers, and take each of them with the smallest exponent with which it is included in all expansions of these numbers;

3) Find the value of this product - it will be the greatest common divisor of these numbers.

To find the least common multiple of given numbers:

1) We represent each given number in canonical form;

2) We form a product from all the prime factors found in the expansions of these numbers, and take each one with the highest exponent with which it is included in all expansions of the given numbers;

3) Find the value of this product - it will be the least common multiple of these numbers.