The least common multiple of two integers is the smallest of all integers that is divisible by both given numbers without leaving a remainder.
Method 1. You can find the LCM, in turn, for each of the given numbers, writing out in ascending order all the numbers that are obtained by multiplying them by 1, 2, 3, 4, and so on.
Example for numbers 6 and 9.
We multiply the number 6, sequentially, by 1, 2, 3, 4, 5.
We get: 6, 12, 18
, 24, 30
We multiply the number 9, sequentially, by 1, 2, 3, 4, 5.
We get: 9, 18
, 27, 36, 45
As you can see, the LCM for numbers 6 and 9 will be equal to 18.
This method is convenient when both numbers are small and it is easy to multiply them by a sequence of integers. However, there are times when you need to find the LCM for two-digit or three-digit numbers, and also when there are three or even more initial numbers.
Method 2. You can find the LCM by factoring the original numbers into prime factors.
After decomposition, it is necessary to cross out identical numbers from the resulting series of prime factors. The remaining numbers of the first number will be a multiplier for the second, and the remaining numbers of the second will be a multiplier for the first.
Example for numbers 75 and 60.
The least common multiple 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 simple factors:
75 = 3
* 5
* 5, a
60 = 2 * 2 * 3
* 5
.
As you can see, factors 3 and 5 appear in both rows. We mentally “cross out” them.
Let us write down the remaining factors included in the expansion of each of these numbers. When decomposing the number 75, we are left with the number 5, and when decomposing the number 60, we are left with 2 * 2
This means that in order to determine the LCM for the numbers 75 and 60, we need to multiply the remaining numbers from the expansion of 75 (this is 5) by 60, and multiply the numbers remaining from the expansion of 60 (this is 2 * 2) by 75. That is, for ease of understanding , we say that we are multiplying “crosswise”.
75 * 2 * 2 = 300
60 * 5 = 300
This is how we found the LCM for the numbers 60 and 75. This is the number 300.
Example. Determine the LCM for the numbers 12, 16, 24
IN in this case, our actions will be somewhat more complicated. But first, as always, let’s factorize all the numbers
12 = 2 * 2 * 3
16 = 2 * 2 * 2 * 2
24 = 2 * 2 * 2 * 3
To correctly determine the LCM, we select the smallest of all numbers (this is the number 12) and sequentially go through its factors, crossing them out if in at least one of the other rows of numbers we encounter the same factor that has not yet been crossed out.
Step 1. We see that 2 * 2 occurs in all series of numbers. Let's cross them out.
12 = 2
* 2
* 3
16 = 2
* 2
* 2 * 2
24 = 2
* 2
* 2 * 3
Step 2. In the prime factors of the number 12, only the number 3 remains. But it is present in the prime factors of the number 24. We cross out the number 3 from both rows, while no actions are required for the number 16.
12 = 2
* 2
* 3
16 = 2
* 2
* 2 * 2
24 = 2
* 2
* 2 * 3
As you can see, when decomposing the number 12, we “crossed out” all the numbers. This means that the finding of the LOC is completed. All that remains is to calculate its value.
For the number 12, take the remaining factors of the number 16 (next in ascending order)
12 * 2 * 2 = 48
This is the NOC
As you can see, in this case, finding the LCM was somewhat more difficult, but when you need to find it for three or more numbers, this method allows you to do it faster. However, both methods of finding the LCM are correct.
Let's look at three ways to find the least common multiple.
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.
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:
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.
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:
Example 2. Find the LCM three data numbers: 12, 8 and 9. We have 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.
Signs of divisibility natural numbers.
Numbers divisible by 2 without a remainder are calledeven .
Numbers that are not evenly divisible by 2 are calledodd .
Test for divisibility by 2
If a natural number ends with an even digit, then this number is divisible by 2 without a remainder, and if a number ends with an odd digit, then this number is not evenly divisible by 2.
For example, the numbers 60 , 30 8 , 8 4 are divisible by 2 without remainder, and the numbers are 51 , 8 5 , 16 7 are not divisible by 2 without a remainder.
Test for divisibility by 3
If the sum of the digits of a number is divisible by 3, then the number is divisible by 3; If the sum of the digits of a number is not divisible by 3, then the number is not divisible by 3.
For example, let’s find out whether the number 2772825 is divisible by 3. To do this, let’s calculate the sum of the digits of this number: 2+7+7+2+8+2+5 = 33 - divisible by 3. This means the number 2772825 is divisible by 3.
Divisibility test by 5
If the record of a natural number ends with the digit 0 or 5, then this number is divisible by 5 without a remainder. If the record of a number ends with another digit, then the number is not divisible by 5 without a remainder.
For example, the numbers 15 , 3 0 , 176 5 , 47530 0 are divisible by 5 without remainder, and the numbers are 17 , 37 8 , 9 1 don't share.
Divisibility test by 9
If the sum of the digits of a number is divisible by 9, then the number is divisible by 9; If the sum of the digits of a number is not divisible by 9, then the number is not divisible by 9.
For example, let’s find out whether the number 5402070 is divisible by 9. To do this, let’s calculate the sum of the digits of this number: 5+4+0+2+0+7+0 = 16 - not divisible by 9. This means the number 5402070 is not divisible by 9.
Divisibility test by 10
If a natural number ends with the digit 0, then this number is divisible by 10 without a remainder. If a natural number ends with another digit, then it is not evenly divisible by 10.
For example, the numbers 40 , 17 0 , 1409 0 are divisible by 10 without remainder, and the numbers 17 , 9 3 , 1430 7 - don't share.
The rule for finding the greatest common divisor (GCD).
To find the greatest common divisor of several natural numbers, you need to:
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.
Example. Let's find GCD (48;36). Let's use the rule.
1. Let's factor the numbers 48 and 36 into prime factors.
48 = 2 · 2 · 2 · 2 · 3
36 = 2 · 2 · 3 · 3
2. From the factors included in the expansion of the number 48, we delete those that are not included in the expansion of the number 36.
48 = 2 · 2 · 2 · 2 · 3
The remaining factors are 2, 2 and 3.
3. Multiply the remaining factors and get 12. This number is the largest common divisor numbers 48 and 36.
GCD (48;36) = 2· 2 · 3 = 12.
The rule for finding the least common multiple (LCM).
To find the least common multiple of several natural numbers, you need to:
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.
Example. Let's find the LOC (75;60). Let's use the rule.
1. Let's factor the numbers 75 and 60 into prime factors.
75 = 3 · 5 · 5
60 = 2 · 2 · 3 · 3
2. Let’s write down the factors included in the expansion of the number 75: 3, 5, 5.
LCM(75;60) = 3 · 5 · 5 · …
3. Add to them the missing factors from the expansion of the number 60, i.e. 2, 2.
LCM(75;60) = 3 · 5 · 5 · 2 · 2
4. Find the product of the resulting factors
LCM(75;60) = 3 · 5 · 5 · 2 · 2 = 300.
The material presented below is a logical continuation of the theory from the article entitled LCM - least common multiple, definition, examples, connection between LCM and GCD. Here we will talk about finding the least common multiple (LCM), And special attention Let's focus on solving examples. First, we will show how the LCM of two numbers is calculated using the GCD of these numbers. Next, we'll look at finding the least common multiple by factoring numbers into prime factors. After this, we will focus on finding the LCM of three or more numbers, and also pay attention to calculating the LCM of negative numbers.
Page navigation.
One way to find the least common multiple is based on the relationship between LCM and GCD. Existing connection between LCM and GCD allows you to calculate the least common multiple of two positive integers using 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.
Let's find GCD(126, 70) using the Euclidean algorithm: 126=70·1+56, 70=56·1+14, 56=14·4, therefore, 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 LCM(68, 34) equal to?
Solution.
Because 68 is divisible by 34, then 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 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.
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 is equal to the product of all factors involved in the expansion of numbers a and b. In turn, GCD(a, b) is equal to the product of all prime factors simultaneously present in the expansions of numbers a and b (as described in the section on finding GCD using the expansion 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 the 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 both the expansion of the number 75 and the expansion of the number 210 (these 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 75 and 210, that is, NOC(75, 210)= 2·3·5·5·7=1,050.
Example.
Factor the numbers 441 and 700 into prime factors and find the least common multiple of these numbers.
Solution.
Let's factor 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 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 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:
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 the missing factors from the expansion of number b are added to the factors from the expansion 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 the same numbers 75 and 210, their decompositions 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 expansion of the number 75 we add the missing factors 2 and 7 from the expansion of the number 210, we obtain the product 2·3·5·5·7, the value of which is equal to LCM(75, 210).
Example.
Find the least common multiple of 84 and 648.
Solution.
We first obtain the decompositions 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 expansion of the number 84 we add the missing factors 2, 3, 3 and 3 from the expansion of the number 648, we obtain the product 2 2 2 3 3 3 3 7, which is equal to 4 536 . Thus, the desired least common multiple of 84 and 648 is 4,536.
Answer:
LCM(84, 648)=4,536 .
The least common multiple of three or more numbers can be found by sequentially finding the LCM of two numbers. Let us recall the corresponding theorem, which gives a way to find the LCM of three or more numbers.
Theorem.
Let the integers be given positive numbers a 1 , a 2 , …, a k , the least common multiple m k of these numbers is 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) .
Let's consider the application of this theorem using the example of finding the least common multiple of four numbers.
Example.
Find the LCM of four numbers 140, 9, 54 and 250.
Solution.
In this example, a 1 =140, a 2 =9, a 3 =54, a 4 =250.
First we find m 2 = LOC(a 1 , a 2) = LOC(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 , from where GCD(140, 9)=140 9:GCD(140, 9)= 140·9:1=1,260. That is, m 2 =1 260.
Now we find m 3 = LOC (m 2 , a 3) = LOC (1 260, 54). Let's calculate it through GCD(1 260, 54), which we also determine using the Euclidean algorithm: 1 260=54·23+18, 54=18·3. Then gcd(1,260, 54)=18, from which gcd(1,260, 54)= 1,260·54:gcd(1,260, 54)= 1,260·54:18=3,780. That is, m 3 =3 780.
All that remains is to find m 4 = LOC(m 3, a 4) = LOC(3 780, 250). To do this, we find GCD(3,780, 250) using the Euclidean algorithm: 3,780=250·15+30, 250=30·8+10, 30=10·3. Therefore, GCM(3,780, 250)=10, whence GCM(3,780, 250)= 3 780 250: GCD(3 780, 250)= 3,780·250:10=94,500. That is, m 4 =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, it is convenient to find the least common multiple of three or more numbers using prime factorizations of the given numbers. In this case, you should adhere to the following rule. 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 resulting factors, and so on.
Let's look at an example of finding the least common multiple using prime factorization.
Example.
Find the least common multiple of the five numbers 84, 6, 48, 7, 143.
Solution.
First, we obtain decompositions of these numbers into prime factors: 84=2·2·3·7, 6=2·3, 48=2·2·2·2·3, 7 (7 is a prime number, it coincides with its decomposition into 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 decomposition of the number 6 does not contain missing factors, since both 2 and 3 are already present in the decomposition of the first number 84. Next, 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 will be no need to add multipliers 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.
Definition. The largest natural number that can be divided without a remainder by numbers a and b 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 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.
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 out 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 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 are multiples of 3, i.e. 6, 9, 12, etc.) were crossed out. in the end only the prime numbers remained uncrossed.
