Let's start studying the least common multiple of two or more numbers. In this section we will define the term, consider the theorem that establishes the connection between the least common multiple and the greatest common divisor, and give examples of solving problems.
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, the common multiples of the number 12 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 of numbers 2 and 3 will be the numbers 12, 6, − 24, 72, 468, − 100,010,004 and a whole series of 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 numbers 2 and 3, the numbers 16, − 27, 5009, 27001 will not be common multiples.
0 is a common multiple of any set of integers other than zero.
If we recall the property of divisibility with respect to opposite numbers, it turns out that some integer k will be a common multiple of these numbers, just like the number - k. This means that common divisors can be either positive or negative.
The common multiple can be found for any integer.
Example 2
Suppose we are given k integers a 1 , a 2 , … , a k. The number we get when multiplying numbers a 1 · a 2 · … · a k according to the property of divisibility, it will be divided into each of the factors that were included in the original product. This means that the product of numbers a 1 , a 2 , … , a k is the least common multiple of these numbers.
A group of integers can have large number 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, the number of common multiples is infinite.
Recall the concept of the smallest number from a given set of numbers, which we discussed in the section “Comparing Integers.” Taking this concept into account, 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 smallest positive common multiple of these numbers.
A least common multiple exists for any number of given numbers. The most commonly used abbreviation for the concept in reference literature is NOC. Short notation for least common multiple of numbers a 1 , a 2 , … , a k will have the form LOC (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 the four numbers 2, 12, 15 and 3 is 60. A short notation will look like LCM (- 2, 12, 15, 3) = 60.
The least common multiple is not obvious for all groups of given numbers. Often it has to be calculated.
Least common multiple and greatest common divisor connected to each other. 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 a and b divided by the greatest common divisor of a and b, that is, LCM (a, b) = a · b: GCD (a, b).
Evidence 1
Suppose we have some number M, which is a multiple of the numbers a and b. If the number M is divisible by a, there also exists some integer z , under which the equality is true M = a k. According to the definition of divisibility, if M is divisible by b, 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 relatively prime 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 of coprime numbers, if a 1 And b 1– coprime numbers, a 1 not divisible by b 1 despite the fact that a 1 k divided by b 1, That b 1 must be shared k.
In this case, it would be appropriate to assume that there is a number t, for which k = b 1 t, and since b 1 = b: d, That k = b: d t.
Now instead k let's substitute into equality M = a k expression of the form b: d t. This allows us to achieve 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 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:
It is not difficult to substantiate these two facts. Any common multiple of M of numbers a and b is defined by the equality M = LCM (a, b) · t for some integer value t. Since a and b are relatively prime, then gcd (a, b) = 1, therefore, gcd (a, b) = a · b: gcd (a, b) = a · b: 1 = a · b.
In order to find the least common multiple of several numbers, it is necessary to sequentially find the LCM of two numbers.
Theorem 2
Let's assume that a 1 , a 2 , … , a k- these are some integers positive numbers. In order 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) .
Evidence 2
The first corollary from the first theorem discussed in this topic will help us prove the validity of the second theorem. The reasoning is based on the following algorithm:
This is how we proved the theorem.
If you notice an error in the text, please highlight it and press Ctrl+Enter
The topic “Multiples” is studied in grade 5 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 the number 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 consider 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 that is divided by natural numbers, and the multiple is itself 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 prime factors and write them as a product of powers:
168=2³x3¹x7¹
2⁴х3³х5¹х7¹=15120
LCM(168, 180, 3024) = 15120.
But many natural numbers are also divisible by other natural numbers.
For example:
The number 12 is divisible by 1, by 2, by 3, by 4, by 6, by 12;
The number 36 is divisible by 1, by 2, by 3, by 4, by 6, by 12, by 18, by 36.
The numbers by which the number is divisible by a whole (for 12 these are 1, 2, 3, 4, 6 and 12) are called divisors of numbers. Divisor of a natural number a- is a natural number that divides a given number a without a trace. A natural number that has more than two divisors is called composite .
Please note that the numbers 12 and 36 have common factors. These numbers are: 1, 2, 3, 4, 6, 12. The greatest divisor of these numbers is 12. The common divisor of these two numbers a And b- this is the number by which both given numbers are divided without remainder a And b.
Common multiples several numbers is a number that is divisible by each of these numbers. For example, the numbers 9, 18 and 45 have a common multiple of 180. But 90 and 360 are also their common multiples. Among all common multiples there is always a smallest one, in in this case this is 90. This number is called the smallestcommon multiple (CMM).
The LCM is always a natural number that must be greater than the largest of the numbers for which it is defined.
Commutativity:
Associativity:
In particular, if and are coprime numbers, then:
Least common multiple of two integers m And n is a divisor of all other common multiples m And n. Moreover, the set of common multiples m, n coincides with the set of multiples for LCM( m, n).
The asymptotics for can be expressed in terms of some number-theoretic functions.
So, Chebyshev function. And also:
This follows from the definition and properties of the Landau function g(n).
What follows from the law of distribution of prime numbers.
NOC( a, b) can be calculated in several ways:
1. If the greatest common divisor is known, you can use its connection with the LCM:
2. Let the canonical decomposition of both numbers into prime factors be known:
Where p 1 ,...,p k- various prime numbers, and d 1 ,...,d k And e 1 ,...,e k— non-negative integers (they can be zeros if the corresponding prime is not in the expansion).
Then NOC ( a,b) is calculated by the formula:
In other words, the LCM decomposition contains all prime factors included in at least one of the decompositions of numbers a, b, and the largest of the two exponents of this multiplier is taken.
Example:
Calculating the least common multiple of several numbers can be reduced to several sequential calculations of the LCM of two numbers:
Rule. To find the LCM of a series of numbers, you need:
- decompose numbers into prime factors;
- transfer the largest decomposition (the product of the factors of the largest number of the given ones) to the factors of the desired product, and then add factors from the decomposition of other numbers that do not appear in the first number or appear in it fewer times;
— the resulting product of prime factors will be the LCM of the given numbers.
Any two or more natural numbers have their own LCM. If the numbers are not multiples of each other or do not have the same factors in the expansion, then their LCM is equal to the product of these numbers.
The prime factors of the number 28 (2, 2, 7) are supplemented with the factor 3 (the number 21), the resulting product (84) will be the smallest number, which is divisible by 21 and 28.
The prime factors of the largest number 30 are supplemented by the factor 5 of the number 25, the resulting product 150 is greater than the largest number 30 and is divisible by all given numbers without a remainder. This least product of the possible (150, 250, 300...), to which all given numbers are multiples.
The numbers 2,3,11,37 are prime numbers, so their LCM is equal to the product of the given numbers.
Rule. To calculate the LCM of prime numbers, you need to multiply all these numbers together.
Another option:
To find the least common multiple (LCM) of several numbers you need:
1) represent each number as a product of its prime factors, for example:
504 = 2 2 2 3 3 7,
2) write down the powers of all prime factors:
504 = 2 2 2 3 3 7 = 2 3 3 2 7 1,
3) write down all the prime divisors (multipliers) of each of these numbers;
4) choose the greatest degree of each of them, found in all expansions of these numbers;
5) multiply these powers.
Example. Find the LCM of the numbers: 168, 180 and 3024.
Solution. 168 = 2 2 2 3 7 = 2 3 3 1 7 1,
180 = 2 2 3 3 5 = 2 2 3 2 5 1,
3024 = 2 2 2 2 3 3 3 7 = 2 4 3 3 7 1.
We write down the greatest powers of all prime divisors and multiply them:
NOC = 2 4 3 3 5 1 7 1 = 15120.
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 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.
