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 decomposing 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 looking for the least common multiple of different 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 the 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 largest 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.
Greatest common divisor
Definition 2
If a natural number a is divisible by a natural number $b$, then $b$ is called a divisor of $a$, and $a$ is called a multiple of $b$.
Let $a$ and $b$ be natural numbers. The number $c$ is called the common divisor of both $a$ and $b$.
The set of common divisors of the numbers $a$ and $b$ is finite, since none of these divisors can be greater than $a$. This means that among these divisors there is a largest one, which is called the greatest common divisor of the numbers $a$ and $b$ and is denoted by the following notations:
$GCD\(a;b)\ or \D\(a;b)$
To find the greatest common divisor of two numbers you need:
- Find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.
Example 1
Find the gcd of the numbers $121$ and $132.$
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Choose the numbers that are included in the expansion of these numbers
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.
$GCD=2\cdot 11=22$
Example 2
Find the gcd of the monomials $63$ and $81$.
We will find according to the presented algorithm. To do this:
Let's factor the numbers into prime factors
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
We select the numbers that are included in the expansion of these numbers
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Let's find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.
$GCD=3\cdot 3=9$
You can find the gcd of two numbers in another way, using a set of divisors of numbers.
Example 3
Find the gcd of the numbers $48$ and $60$.
Solution:
Let's find the set of divisors of the number $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$
Now let's find the set of divisors of the number $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$
Let's find the intersection of these sets: $\left\((\rm 1,2,3,4,6,12)\right\)$ - this set will determine the set of common divisors of the numbers $48$ and $60$. The largest element in this set will be the number $12$. This means that the greatest common divisor of the numbers $48$ and $60$ is $12$.
Definition of NPL
Definition 3
Common multiples natural numbers $a$ and $b$ is a natural number that is a multiple of both $a$ and $b$.
Common multiples of numbers are numbers that are divisible by the original numbers without a remainder. For example, for the numbers $25$ and $50$, the common multiples will be the numbers $50,100,150,200$, etc.
The smallest common multiple will be called the least common multiple and will be denoted LCM$(a;b)$ or K$(a;b).$
To find the LCM of two numbers, you need to:
- Factor numbers into prime factors
- Write down the factors that are part of the first number and add to them the factors that are part of the second and are not part of the first
Example 4
Find the LCM of the numbers $99$ and $77$.
We will find according to the presented algorithm. For this
Factor numbers into prime factors
$99=3\cdot 3\cdot 11$
Write down the factors included in the first
add to them multipliers that are part of the second and not part of the first
Find the product of the numbers found in step 2. The resulting number will be the desired least common multiple
$NOK=3\cdot 3\cdot 11\cdot 7=693$
Compiling lists of divisors of numbers is often a very labor-intensive task. There is a way to find GCD called the Euclidean algorithm.
Statements on which the Euclidean algorithm is based:
If $a$ and $b$ are natural numbers, and $a\vdots b$, then $D(a;b)=b$
If $a$ and $b$ are natural numbers such that $b
Using $D(a;b)= D(a-b;b)$, we can successively reduce the numbers under consideration until we reach a pair of numbers such that one of them is divisible by the other. Then the smaller of these numbers will be the desired greatest common divisor for the numbers $a$ and $b$.
Properties of GCD and LCM
- Any common multiple of $a$ and $b$ is divisible by K$(a;b)$
- If $a\vdots b$ , then К$(a;b)=a$
If K$(a;b)=k$ and $m$ is a natural number, then K$(am;bm)=km$
If $d$ is a common divisor for $a$ and $b$, then K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d) $
If $a\vdots c$ and $b\vdots c$ , then $\frac(ab)(c)$ is the common multiple of $a$ and $b$
For any natural numbers $a$ and $b$ the equality holds
$D(a;b)\cdot К(a;b)=ab$
Any common divisor of the numbers $a$ and $b$ is a divisor of the number $D(a;b)$
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 this case it 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.
Least common multiple (LCM). Properties.
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 of the 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.
Finding the least common multiple (LCM).
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 expansion (the product of the factors of the desired product) into the factors of the desired product large number from the given ones), and then add factors from the expansion 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.
Prime factors more 30 was supplemented with 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 is the smallest possible product (150, 250, 300...) that is a multiple of all given numbers.
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 numbers is directly related to the greatest common divisor of those numbers. This connection between GCD and NOC is determined by the following theorem.
Theorem.
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).
Proof.
Let M is some multiple of the numbers a and b. That is, M is divisible by a, and by the definition of divisibility, there is some integer k such that the equality M=a·k is true. But M is also divisible by b, then a·k is divisible by b.
Let's denote gcd(a, b) as d. Then we can write the equalities a=a 1 ·d and b=b 1 ·d, and a 1 =a:d and b 1 =b:d will be relatively prime numbers. Consequently, the condition obtained in the previous paragraph that a · k is divisible by b can be reformulated as follows: a 1 · d · k is divided by b 1 · d , and this, due to the properties of divisibility, is equivalent to the condition that a 1 · k is divisible by b 1.
You also need to write down two important corollaries from the theorem considered.
The common multiples of two numbers are the same as the multiples of their least common multiple.
This is indeed the case, since any common multiple of M of the numbers a and b is determined by the equality M=LMK(a, b)·t for some integer value t.
The least common multiple of mutually prime positive numbers a and b is equal to their product.
The rationale for this fact is quite obvious. 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.
Least common multiple of three or more numbers
Finding the least common multiple of three or more numbers can be reduced to sequentially finding the LCM of two numbers. How this is done is indicated in the following theorem. a 1 , a 2 , …, a k coincide with the common multiples of the numbers m k-1 and a k , therefore, coincide with the common multiples of the number m k . And since the smallest positive multiple of the number m k is the number m k itself, then the smallest common multiple of the numbers a 1, a 2, ..., a k is m k.
References.
- Vilenkin N.Ya. and others. Mathematics. 6th grade: textbook for general education institutions.
- Vinogradov I.M. Fundamentals of number theory.
- Mikhelovich Sh.H. Number theory.
- Kulikov L.Ya. and others. Collection of problems in algebra and number theory: Tutorial for students of physics and mathematics. specialties of pedagogical institutes.
To understand how to calculate the LCM, you must first determine the meaning of the term “multiple”.
A multiple of A is a natural number that is divisible by A without a remainder. Thus, numbers that are multiples of 5 can be considered 15, 20, 25, and so on.
There can be a limited number of divisors of a particular number, but there are an infinite number of multiples.
A common multiple of natural numbers is a number that is divisible by them without leaving a remainder.
How to find the least common multiple of numbers
The least common multiple (LCM) of numbers (two, three or more) is the smallest natural number that is divisible by all these numbers.
To find the LOC, you can use several methods.
For small numbers, it is convenient to write down all the multiples of these numbers on a line until you find something common among them. Multiples are indicated in the notation capital letter TO.
For example, multiples of 4 can be written like this:
K (4) = (8,12, 16, 20, 24, ...)
K (6) = (12, 18, 24, ...)
Thus, you can see that the least common multiple of the numbers 4 and 6 is the number 24. This notation is done as follows:
LCM(4, 6) = 24
If the numbers are large, find the common multiple of three or more numbers, then it is better to use another method of calculating the LCM.
To complete the task, you need to factor the given numbers into prime factors.
First you need to write down the decomposition of the largest number on a line, and below it - the rest.
The decomposition of each number may contain a different number of factors.
For example, let's factor the numbers 50 and 20 into prime factors.
In the expansion of the smaller number, you should highlight the factors that are missing in the expansion of the first largest number, and then add them to it. In the example presented, a two is missing.
Now you can calculate the least common multiple of 20 and 50.
LCM(20, 50) = 2 * 5 * 5 * 2 = 100
Thus, the product of the prime factors of the larger number and the factors of the second number that were not included in the expansion of the larger number will be the least common multiple.
To find the LCM of three or more numbers, you should factor them all into prime factors, as in the previous case.
As an example, you can find the least common multiple of the numbers 16, 24, 36.
36 = 2 * 2 * 3 * 3
24 = 2 * 2 * 2 * 3
16 = 2 * 2 * 2 * 2
Thus, only two twos from the expansion of sixteen were not included in the factorization of a larger number (one is in the expansion of twenty-four).
Thus, they need to be added to the expansion of a larger number.
LCM(12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9
There are special cases of determining the least common multiple. So, if one of the numbers can be divided without a remainder by another, then the larger of these numbers will be the least common multiple.
For example, the LCM of twelve and twenty-four is twenty-four.
If it is necessary to find the least common multiple of coprime numbers that do not have identical divisors, then their LCM will be equal to their product.
For example, LCM (10, 11) = 110.
