Let's look at three ways to find the least common multiple.
Finding by factorization
The first method is to find the least common multiple by factoring the given numbers into prime factors.
Let's say we need to find the LCM of the numbers: 99, 30 and 28. To do this, let's factor 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 greatest possible power and multiply them together:
2 2 3 2 5 7 11 = 13,860
Thus, LCM (99, 30, 28) = 13,860. No other number less than 13,860 is divisible by 99, 30, or 28.
To find the least common multiple of given numbers, you factor them into their prime factors, then take each prime factor with the largest exponent it appears in, and multiply those factors together.
Since relatively prime numbers do not have common prime factors, their least common multiple is equal to the product of these numbers. For example, three numbers: 20, 49 and 33 are relatively prime. That's why
LCM (20, 49, 33) = 20 49 33 = 32,340.
The same must be done when finding the least common multiple of various prime numbers. For example, LCM (3, 7, 11) = 3 7 11 = 231.
Finding by selection
The second method is to find the least common multiple by selection.
Example 1. When the largest of given numbers is divided by another given number, then the LCM of these numbers is equal to the largest of them. For example, given four numbers: 60, 30, 10 and 6. Each of them is divisible by 60, therefore:
LCM(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, we find the numbers that are multiples of the largest number by multiplying it by natural numbers in increasing order and checking whether the resulting product is divisible by the remaining given numbers.
Example 2. Given three numbers 24, 3 and 18. We determine the largest of them - this is the number 24. Next, we find the numbers that are multiples of 24, checking whether each of them is divisible by 18 and 3:
24 · 1 = 24 - divisible by 3, but not divisible by 18.
24 · 2 = 48 - divisible by 3, but not divisible by 18.
24 · 3 = 72 - divisible by 3 and 18.
Thus, LCM (24, 3, 18) = 72.
Finding by sequentially finding the LCM
The third method is to find the least common multiple by sequentially 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 by their gcd:
Thus, LCM (12, 8) = 24.
To find the LCM of three or more numbers, use the following procedure:
- First, find the LCM of any two of these numbers.
- Then, 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, etc.
- Thus, the search for LCM continues as long as there are numbers.
Example 2. Let's find the LCM of three given numbers: 12, 8 and 9. We already found the LCM of the numbers 12 and 8 in the previous example (this is the number 24). It remains to find the least common multiple of the number 24 and the third given number - 9. Determine their greatest common divisor: GCD (24, 9) = 3. Multiply the LCM with the number 9:
We divide the product by their gcd:
Thus, LCM (12, 8, 9) = 72.
The topic “Multiple Numbers” is studied in the 5th grade of secondary school. Its goal is to improve written and oral mathematical calculation skills. In this lesson, new concepts are introduced - “multiple numbers” and “divisors”, the technique of finding divisors and multiples of a natural number, and the ability to find LCM in various ways are practiced.
This topic is very important. Knowledge of it can be applied when solving examples with fractions. To do this, you need to find the common denominator by calculating the least common multiple (LCM).
A multiple of A is an integer that is divisible by A without a remainder.
Every natural number has an infinite number of multiples of it. It is itself considered the smallest. The multiple cannot be less than the number itself.
You need to prove that the number 125 is a multiple of 5. To do this, you need to divide the first number by the second. If 125 is divisible by 5 without a remainder, then the answer is yes.
This method is applicable for small numbers.
There are special cases when calculating LOC.
1. If you need to find a common multiple of 2 numbers (for example, 80 and 20), where one of them (80) is divisible by the other (20), then this number (80) is the least multiple of these two numbers.
LCM(80, 20) = 80.
2. If two do not have a common divisor, then we can say that their LCM is the product of these two numbers.
LCM(6, 7) = 42.
Let's look at the last example. 6 and 7 in relation to 42 are divisors. They divide a multiple of a number without a remainder.
In this example, 6 and 7 are paired factors. Their product is equal to the most multiple number (42).
A number is called prime if it is divisible only by itself or by 1 (3:1=3; 3:3=1). The rest are called composite.
Another example involves determining whether 9 is a divisor of 42.
42:9=4 (remainder 6)
Answer: 9 is not a divisor of 42 because the answer has a remainder.
A divisor differs from a multiple in that the divisor is the number by which natural numbers are divided, and the multiple itself is divisible by this number.
Greatest common divisor of numbers a And b, multiplied by their least multiple, will give the product of the numbers themselves a And b.
Namely: gcd (a, b) x gcd (a, b) = a x b.
Common multiples for more complex numbers are found in the following way.
For example, find the LCM for 168, 180, 3024.
We factor these numbers into simple factors and write them as a product of powers:
168=2³x3¹x7¹
2⁴х3³х5¹х7¹=15120
LCM(168, 180, 3024) = 15120.
Second number: b=
Thousand separator Without space separator "´
Result:
Greatest common divisor gcd( a,b)=6
Least common multiple of LCM( a,b)=468
The largest natural number that can be divided without a remainder by numbers a and b is called greatest common divisor(GCD) of these numbers. Denoted by gcd(a,b), (a,b), gcd(a,b) or hcf(a,b).
Least common multiple The LCM of two integers a and b is the smallest natural number that is divisible by a and b without a remainder. Denoted LCM(a,b), or lcm(a,b).
The integers a and b are called mutually prime, if they have no common divisors other than +1 and −1.
Greatest common divisor
Let two positive numbers be given a 1 and a 2 1). It is required to find the common divisor of these numbers, i.e. find such a number λ , which divides numbers a 1 and a 2 at the same time. Let's describe the algorithm.
1) In this article, the word number will be understood as an integer.
Let a 1 ≥ a 2 and let
Where m 1 , a 3 are some integers, a 3 <a 2 (remainder of division a 1 per a 2 should be less a 2).
Let's pretend that λ divides a 1 and a 2 then λ divides m 1 a 2 and λ divides a 1 −m 1 a 2 =a 3 (Statement 2 of the article "Divisibility of numbers. Test of divisibility"). It follows that every common divisor a 1 and a 2 is the common divisor a 2 and a 3. The reverse is also true if λ common divisor a 2 and a 3 then m 1 a 2 and a 1 =m 1 a 2 +a 3 is also divisible by λ . Therefore the common divisor a 2 and a 3 is also a common divisor a 1 and a 2. Because a 3 <a 2 ≤a 1, then we can say that the solution to the problem of finding the common divisor of numbers a 1 and a 2 reduced to the simpler problem of finding the common divisor of numbers a 2 and a 3 .
If a 3 ≠0, then we can divide a 2 per a 3. Then
,
Where m 1 and a 4 are some integers, ( a 4 remainder from division a 2 per a 3 (a 4 <a 3)). By similar reasoning we come to the conclusion that common divisors of numbers a 3 and a 4 coincides with common divisors of numbers a 2 and a 3, and also with common divisors a 1 and a 2. Because a 1 , a 2 , a 3 , a 4, ... are numbers that are constantly decreasing, and since there is a finite number of integers between a 2 and 0, then at some step n, remainder of the division a n on a n+1 will be equal to zero ( a n+2 =0).
.
Every common divisor λ numbers a 1 and a 2 is also a divisor of numbers a 2 and a 3 , a 3 and a 4 , .... a n and a n+1 . The converse is also true, common divisors of numbers a n and a n+1 are also divisors of numbers a n−1 and a n , .... , a 2 and a 3 , a 1 and a 2. But the common divisor of numbers a n and a n+1 is a number a n+1 , because a n and a n+1 are divisible by a n+1 (remember that a n+2 =0). Hence a n+1 is also a divisor of numbers a 1 and a 2 .
Note that the number a n+1 is the largest divisor of numbers a n and a n+1 , since the greatest divisor a n+1 is itself a n+1 . If a n+1 can be represented as a product of integers, then these numbers are also common divisors of numbers a 1 and a 2. Number a n+1 is called greatest common divisor numbers a 1 and a 2 .
Numbers a 1 and a 2 can be either positive or negative numbers. If one of the numbers is equal to zero, then the greatest common divisor of these numbers will be equal to the absolute value of the other number. The greatest common divisor of zero numbers is undefined.
The above algorithm is called Euclidean algorithm to find the greatest common divisor of two integers.
An example of finding the greatest common divisor of two numbers
Find the greatest common divisor of two numbers 630 and 434.
- Step 1. Divide the number 630 by 434. The remainder is 196.
- Step 2. Divide the number 434 by 196. The remainder is 42.
- Step 3. Divide the number 196 by 42. The remainder is 28.
- Step 4. Divide the number 42 by 28. The remainder is 14.
- Step 5. Divide the number 28 by 14. The remainder is 0.
In step 5, the remainder of the division is 0. Therefore, the greatest common divisor of the numbers 630 and 434 is 14. Note that the numbers 2 and 7 are also divisors of the numbers 630 and 434.
Coprime numbers
Definition 1. Let the greatest common divisor of the numbers a 1 and a 2 is equal to one. Then these numbers are called coprime numbers, having no common divisor.
Theorem 1. If a 1 and a 2 coprime numbers, and λ some number, then any common divisor of numbers λa 1 and a 2 is also a common divisor of numbers λ And a 2 .
Proof. Consider the Euclidean algorithm for finding the greatest common divisor of numbers a 1 and a 2 (see above).
.
From the conditions of the theorem it follows that the greatest common divisor of the numbers a 1 and a 2 and therefore a n and a n+1 is 1. That is a n+1 =1.
Let's multiply all these equalities by λ , Then
.
Let the common divisor a 1 λ And a 2 yes δ . Then δ is included as a multiplier in a 1 λ , m 1 a 2 λ and in a 1 λ -m 1 a 2 λ =a 3 λ (cm. "Divisibility of numbers", Statement 2). Further δ is included as a multiplier in a 2 λ And m 2 a 3 λ , and, therefore, is a factor in a 2 λ -m 2 a 3 λ =a 4 λ .
Reasoning this way, we are convinced that δ is included as a multiplier in a n−1 λ And m n−1 a n λ , and therefore in a n−1 λ −m n−1 a n λ =a n+1 λ . Because a n+1 =1, then δ is included as a multiplier in λ . Therefore the number δ is the common divisor of numbers λ And a 2 .
Let us consider special cases of Theorem 1.
Consequence 1. Let a And c Prime numbers are relatively b. Then their product ac is a prime number with respect to b.
Really. From Theorem 1 ac And b have the same common divisors as c And b. But the numbers c And b relatively simple, i.e. have a single common divisor 1. Then ac And b also have a single common divisor 1. Therefore ac And b mutually simple.
Consequence 2. Let a And b coprime numbers and let b divides ak. Then b divides and k.
Really. From the approval condition ak And b have a common divisor b. By virtue of Theorem 1, b must be a common divisor b And k. Hence b divides k.
Corollary 1 can be generalized.
Consequence 3. 1. Let the numbers a 1 , a 2 , a 3 , ..., a m are prime relative to the number b. Then a 1 a 2 , a 1 a 2 · a 3 , ..., a 1 a 2 a 3 ··· a m, the product of these numbers is prime relative to the number b.
2. Let us have two rows of numbers
such that every number in the first series is prime in the ratio of every number in the second series. Then the product
You need to find numbers that are divisible by each of these numbers.
If a number is divisible by a 1, then it has the form sa 1 where s some number. If q is the greatest common divisor of numbers a 1 and a 2, then
Where s 1 is some integer. Then
is least common multiples of numbers a 1 and a 2 .
a 1 and a 2 are relatively prime, then the least common multiple of the numbers a 1 and a 2:
We need to find the least common multiple of these numbers.
From the above it follows that any multiple of numbers a 1 , a 2 , a 3 must be a multiple of numbers ε And a 3 and back. Let the least common multiple of the numbers ε And a 3 yes ε 1 . Next, multiples of numbers a 1 , a 2 , a 3 , a 4 must be a multiple of numbers ε 1 and a 4 . Let the least common multiple of the numbers ε 1 and a 4 yes ε 2. Thus, we found out that all multiples of numbers a 1 , a 2 , a 3 ,...,a m coincide with multiples of a certain number ε n, which is called the least common multiple of the given numbers.
In the special case when the numbers a 1 , a 2 , a 3 ,...,a m are relatively prime, then the least common multiple of the numbers a 1 , a 2, as shown above, has the form (3). Next, since a 3 prime in relation to numbers a 1 , a 2 then a 3 prime number a 1 · a 2 (Corollary 1). Means the least common multiple of numbers a 1 ,a 2 ,a 3 is a number a 1 · a 2 · a 3. Reasoning in a similar way, we arrive at the following statements.
Statement 1. Least common multiple of coprime numbers a 1 , a 2 , a 3 ,...,a m is equal to their product a 1 · a 2 · a 3 ··· a m.
Statement 2. Any number that is divisible by each of the coprime numbers a 1 , a 2 , a 3 ,...,a m is also divisible by their product a 1 · a 2 · a 3 ··· a m.
Let's continue the conversation about the least common multiple, which we started in the section “LCM - least common multiple, definition, examples.” In this topic, we will look at ways to find the LCM for three or more numbers, and we will look at the question of how to find the LCM of a negative number.
Yandex.RTB R-A-339285-1
Calculating Least Common Multiple (LCM) via GCD
We have already established the relationship between the least common multiple and the greatest common divisor. Now let's learn how to determine the LCM through GCD. First, let's figure out how to do this for positive numbers.
Definition 1
You can find the least common multiple through the greatest common divisor using the formula LCM (a, b) = a · b: GCD (a, b).
Example 1
You need to find the LCM of the numbers 126 and 70.
Solution
Let's take a = 126, b = 70. Let's substitute the values into the formula for calculating the least common multiple through the greatest common divisor LCM (a, b) = a · b: GCD (a, b) .
Finds the gcd of numbers 70 and 126. For this we need the Euclidean algorithm: 126 = 70 1 + 56, 70 = 56 1 + 14, 56 = 14 4, therefore GCD (126 , 70) = 14 .
Let's calculate the LCM: LCD (126, 70) = 126 70: GCD (126, 70) = 126 70: 14 = 630.
Answer: LCM(126, 70) = 630.
Example 2
Find the number 68 and 34.
Solution
GCD in this case is not difficult to find, since 68 is divisible by 34. Let's calculate the least common multiple using the formula: LCM (68, 34) = 68 34: GCD (68, 34) = 68 34: 34 = 68.
Answer: LCM(68, 34) = 68.
In this example, we used the rule for finding the least common multiple of positive integers a and b: if the first number is divisible by the second, the LCM of those numbers will be equal to the first number.
Finding the LCM by factoring numbers into prime factors
Now let's look at the method of finding the LCM, which is based on factoring numbers into prime factors.
Definition 2
To find the least common multiple, we need to perform a number of simple steps:
- we compose the product of all prime factors of the numbers for which we need to find the LCM;
- we exclude all prime factors from their resulting products;
- the product obtained after eliminating the common prime factors will be equal to the LCM of the given numbers.
This method of finding the least common multiple is based on the equality LCM (a, b) = a · b: GCD (a, b). If you look at the formula, it will become clear: the product of the numbers a and b is equal to the product of all the factors that participate in the decomposition of these two numbers. In this case, the gcd of two numbers is equal to the product of all prime factors that are simultaneously present in the factorizations of these two numbers.
Example 3
We have two numbers 75 and 210. We can factor them as follows: 75 = 3 5 5 And 210 = 2 3 5 7. If you compose the product of all the factors of the two original numbers, you get: 2 3 3 5 5 5 7.
If we exclude the factors common to both numbers 3 and 5, we get a product of the following form: 2 3 5 5 7 = 1050. This product will be our LCM for the numbers 75 and 210.
Example 4
Find the LCM of numbers 441 And 700 , factoring both numbers into prime factors.
Solution
Let's find all the prime factors of the numbers given in the condition:
441 147 49 7 1 3 3 7 7
700 350 175 35 7 1 2 2 5 5 7
We get two chains of numbers: 441 = 3 3 7 7 and 700 = 2 2 5 5 7.
The product of all factors that participated in the decomposition of these numbers will have the form: 2 2 3 3 5 5 7 7 7. Let's find common factors. This is the number 7. Let's exclude it from the total product: 2 2 3 3 5 5 7 7. It turns out that NOC (441, 700) = 2 2 3 3 5 5 7 7 = 44 100.
Answer: LOC(441, 700) = 44,100.
Let us give another formulation of the method for finding the LCM by decomposing numbers into prime factors.
Definition 3
Previously, we excluded from the total number of factors common to both numbers. Now we will do it differently:
- Let's factor both numbers into prime factors:
- add to the product of the prime factors of the first number the missing factors of the second number;
- we obtain the product, which will be the desired LCM of two numbers.
Example 5
Let's return to the numbers 75 and 210, for which we already looked for the LCM in one of the previous examples. Let's break them down into simple factors: 75 = 3 5 5 And 210 = 2 3 5 7. To the product of factors 3, 5 and 5 numbers 75 add the missing factors 2 And 7 numbers 210. We get: 2 · 3 · 5 · 5 · 7 . This is the LCM of the numbers 75 and 210.
Example 6
It is necessary to calculate the LCM of the numbers 84 and 648.
Solution
Let's factor the numbers from the condition into simple factors: 84 = 2 2 3 7 And 648 = 2 2 2 3 3 3 3. Let's add to the product the factors 2, 2, 3 and 7
numbers 84 missing factors 2, 3, 3 and
3
numbers 648. We get the product 2 2 2 3 3 3 3 7 = 4536. This is the least common multiple of 84 and 648.
Answer: LCM(84, 648) = 4,536.
Finding the LCM of three or more numbers
Regardless of how many numbers we are dealing with, the algorithm of our actions will always be the same: we will sequentially find the LCM of two numbers. There is a theorem for this case.
Theorem 1
Let's assume we have integers a 1 , a 2 , … , a k. NOC m k these numbers are found by sequentially calculating m 2 = LCM (a 1, a 2), m 3 = LCM (m 2, a 3), ..., m k = LCM (m k − 1, a k).
Now let's look at how the theorem can be applied to solve specific problems.
Example 7
You need to calculate the least common multiple of four numbers 140, 9, 54 and 250 .
Solution
Let us introduce the notation: a 1 = 140, a 2 = 9, a 3 = 54, a 4 = 250.
Let's start by calculating m 2 = LCM (a 1 , a 2) = LCM (140, 9). Let's apply the Euclidean algorithm to calculate the GCD of the numbers 140 and 9: 140 = 9 15 + 5, 9 = 5 1 + 4, 5 = 4 1 + 1, 4 = 1 4. We get: GCD (140, 9) = 1, GCD (140, 9) = 140 9: GCD (140, 9) = 140 9: 1 = 1,260. Therefore, m 2 = 1,260.
Now let’s calculate using the same algorithm m 3 = LCM (m 2 , a 3) = LCM (1 260, 54). During the calculations we obtain m 3 = 3 780.
We just have to calculate m 4 = LCM (m 3 , a 4) = LCM (3 780, 250). We follow the same algorithm. We get m 4 = 94 500.
The LCM of the four numbers from the example condition is 94500.
Answer: NOC (140, 9, 54, 250) = 94,500.
As you can see, the calculations are simple, but quite labor-intensive. To save time, you can go another way.
Definition 4
We offer you the following algorithm of actions:
- we decompose all numbers into prime factors;
- to the product of the factors of the first number we add the missing factors from the product of the second number;
- to the product obtained at the previous stage we add the missing factors of the third number, etc.;
- the resulting product will be the least common multiple of all numbers from the condition.
Example 8
You need to find the LCM of five numbers 84, 6, 48, 7, 143.
Solution
Let's factor all five numbers into prime factors: 84 = 2 2 3 7, 6 = 2 3, 48 = 2 2 2 2 3, 7, 143 = 11 13. Prime numbers, which is the number 7, cannot be factored into prime factors. Such numbers coincide with their decomposition into prime factors.
Now let's take the product of the prime factors 2, 2, 3 and 7 of the number 84 and add to them the missing factors of the second number. We decomposed the number 6 into 2 and 3. These factors are already in the product of the first number. Therefore, we omit them.
We continue to add the missing multipliers. Let's move on to the number 48, from the product of whose prime factors we take 2 and 2. Then we add the prime factor of 7 from the fourth number and the factors of 11 and 13 of the fifth. We get: 2 2 2 2 3 7 11 13 = 48,048. This is the least common multiple of the original five numbers.
Answer: LCM(84, 6, 48, 7, 143) = 48,048.
Finding the least common multiple of negative numbers
In order to find the least common multiple of negative numbers, these numbers must first be replaced by numbers with the opposite sign, and then the calculations must be carried out using the above algorithms.
Example 9
LCM (54, − 34) = LCM (54, 34) and LCM (− 622, − 46, − 54, − 888) = LCM (622, 46, 54, 888).
Such actions are permissible due to the fact that if we accept that a And − a– opposite numbers,
then the set of multiples of a number a matches the set of multiples of a number − a.
Example 10
It is necessary to calculate the LCM of negative numbers − 145 And − 45 .
Solution
Let's replace the numbers − 145 And − 45 to their opposite numbers 145 And 45 . Now, using the algorithm, we calculate the LCM (145, 45) = 145 · 45: GCD (145, 45) = 145 · 45: 5 = 1,305, having previously determined the GCD using the Euclidean algorithm.
We get that the LCM of the numbers is − 145 and − 45 equals 1 305 .
Answer: LCM (− 145, − 45) = 1,305.
If you notice an error in the text, please highlight it and press Ctrl+Enter