Finding a common multiple of two numbers. Least common multiple (LCM)
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 the number $a$ is called a multiple of $b$.
Let $a$ and $b$ be natural numbers. The number $c$ is called a common divisor for 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 the largest one, which is called the greatest common divisor of the numbers $a$ and $b$, and the notation is used to denote it:
$gcd \ (a;b) \ or \ D \ (a;b)$
To find the greatest common divisor of two numbers:
- 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 monomials $63$ and $81$.
We will find according to the presented algorithm. For this:
Let's decompose 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 the set of divisors of numbers.
Example 3
Find the gcd of the numbers $48$ and $60$.
Solution:
Find the set of divisors of $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$
Now let's find the set of divisors of $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$. So the greatest common divisor of $48$ and $60$ is $12$.
Definition of NOC
Definition 3
common multiple of 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 without a remainder. For example, for the numbers $25$ and $50$, the common multiples will be the numbers $50,100,150,200$, etc.
The least common multiple will be called the least common multiple and denoted by LCM$(a;b)$ or K$(a;b).$
To find the LCM of two numbers, you need:
- Decompose numbers into prime factors
- Write out the factors that are part of the first number and add to them the factors that are part of the second and do not go to the first
Example 4
Find the LCM of the numbers $99$ and $77$.
We will find according to the presented algorithm. For this
Decompose numbers into prime factors
$99=3\cdot 3\cdot 11$
Write down the factors included in the first
add to them factors that are part of the second and do not go to the first
Find the product of the numbers found in step 2. The resulting number will be the desired least common multiple
$LCC=3\cdot 3\cdot 11\cdot 7=693$
Compiling lists of divisors of numbers is often very time consuming. There is a way to find GCD called Euclid's algorithm.
Statements on which Euclid's 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 decrease 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 K$(a;b)=a$
If K$(a;b)=k$ and $m$-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 a common multiple of $a$ and $b$
For any natural numbers $a$ and $b$ the equality
$D(a;b)\cdot K(a;b)=ab$
Any common divisor of $a$ and $b$ is a divisor of $D(a;b)$
The greatest common divisor and the least common multiple are key arithmetic concepts that allow you to operate effortlessly ordinary fractions. LCM and are most often used to find the common denominator of several fractions.
Basic concepts
The divisor of an integer X is another integer Y by which X is divisible without a remainder. For example, the divisor of 4 is 2, and 36 is 4, 6, 9. A multiple of the integer X is a number Y that is divisible by X without a remainder. For example, 3 is a multiple of 15, and 6 is a multiple of 12.
For any pair of numbers, we can find their common divisors and multiples. For example, for 6 and 9, the common multiple is 18, and the common divisor is 3. Obviously, pairs can have several divisors and multiples, so the largest divisor of the GCD and the smallest multiple of the LCM are used in the calculations.
The smallest divisor does not make sense, since for any number it is always one. The largest multiple is also meaningless, since the sequence of multiples tends to infinity.
Finding GCD
There are many methods for finding the greatest common divisor, the most famous of which are:
- sequential enumeration of divisors, selection of common ones for a pair and search for the largest of them;
- decomposition of numbers into indivisible factors;
- Euclid's algorithm;
- binary algorithm.
Today at educational institutions the most popular are prime factorization methods and Euclid's algorithm. The latter, in turn, is used in solving Diophantine equations: the search for GCD is required to check the equation for the possibility of resolving it in integers.
Finding the NOC
The least common multiple is also exactly determined by iterative enumeration or factorization into indivisible factors. In addition, it is easy to find the LCM if the largest divisor has already been determined. For numbers X and Y, LCM and GCD are related by the following relation:
LCM(X,Y) = X × Y / GCM(X,Y).
For example, if gcd(15,18) = 3, then LCM(15,18) = 15 × 18 / 3 = 90. The most obvious use of LCM is to find the common denominator, which is the least common multiple of the given fractions.
Coprime numbers
If a pair of numbers has no common divisors, then such a pair is called coprime. The GCM for such pairs is always equal to one, and based on the connection of divisors and multiples, the GCM for coprime is equal to their product. For example, the numbers 25 and 28 are coprime, because they have no common divisors, and LCM(25, 28) = 700, which corresponds to their product. Any two indivisible numbers will always be coprime.
Common Divisor and Multiple Calculator
With our calculator you can calculate GCD and LCM for any number of numbers to choose from. Tasks for calculating common divisors and multiples are found in arithmetic of grades 5, 6, however, GCD and LCM - key concepts mathematics and are used in number theory, planimetry and communicative algebra.
Real life examples
Common denominator of fractions
The least common multiple is used when finding the common denominator of several fractions. Suppose in an arithmetic problem it is required to sum 5 fractions:
1/8 + 1/9 + 1/12 + 1/15 + 1/18.
To add fractions, the expression must be reduced to a common denominator, which reduces to the problem of finding the LCM. To do this, select 5 numbers in the calculator and enter the denominator values in the appropriate cells. The program will calculate LCM (8, 9, 12, 15, 18) = 360. Now you need to calculate additional factors for each fraction, which are defined as the ratio of LCM to the denominator. So the extra multipliers would look like:
- 360/8 = 45
- 360/9 = 40
- 360/12 = 30
- 360/15 = 24
- 360/18 = 20.
After that, we multiply all the fractions by the corresponding additional factor and get:
45/360 + 40/360 + 30/360 + 24/360 + 20/360.
We can easily add such fractions and get the result in the form of 159/360. We reduce the fraction by 3 and see the final answer - 53/120.
Solution of linear diophantine equations
Linear Diophantine equations are expressions of the form ax + by = d. If the ratio d / gcd(a, b) is an integer, then the equation is solvable in integers. Let's check a couple of equations for the possibility of an integer solution. First, check the equation 150x + 8y = 37. Using a calculator, we find gcd (150.8) = 2. Divide 37/2 = 18.5. The number is not an integer, therefore, the equation does not have integer roots.
Let's check the equation 1320x + 1760y = 10120. Use the calculator to find gcd(1320, 1760) = 440. Divide 10120/440 = 23. As a result, we get an integer, therefore, the Diophantine equation is solvable in integer coefficients.
Conclusion
GCD and LCM play an important role in number theory, and the concepts themselves are widely used in various areas of mathematics. Use our calculator to calculate the largest divisors and smallest multiples of any number of numbers.
The least common multiple of two numbers is directly related to the greatest common divisor of those numbers. This link between GCD and NOC is defined 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: GCM(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.
Denote gcd(a, b) as d . Then we can write down the equalities a=a 1 ·d and b=b 1 ·d, and a 1 =a:d and b 1 =b:d will be coprime numbers. Therefore, the condition obtained in the previous paragraph that a k is divisible by b can be reformulated as follows: a 1 d k is divisible 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 .
We also need to write down two important corollaries from the considered theorem.
Common multiples of two numbers are the same as multiples of their least common multiple.
This is true, since any common multiple of M numbers a and b is defined by the equality M=LCM(a, b) t for some integer value t .
Least common multiple of coprime positive numbers a and b is equal to their product.
The rationale for this fact is quite obvious. Since a and b are coprime, then gcd(a, b)=1 , therefore, LCM(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 successively finding the LCM of two numbers. How this is done is indicated in the following theorem. a 1 , a 2 , …, a k coincide with common multiples of numbers m k-1 and a k , therefore, coincide with multiples of m k . And since the least positive multiple of the number m k is the number m k itself, then the least common multiple of the numbers a 1 , a 2 , …, a k is m k .
Bibliography.
- Vilenkin N.Ya. etc. Mathematics. Grade 6: textbook for educational institutions.
- Vinogradov I.M. Fundamentals of number theory.
- Mikhelovich Sh.Kh. 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 should first determine the meaning of the term "multiple".
A multiple of A is a natural number that is divisible by A without remainder. Thus, 15, 20, 25, and so on can be considered multiples of 5.
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 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 evenly divisible by all these numbers.
To find the NOC, you can use several methods.
For small numbers, it is convenient to write out in a line all the multiples of these numbers until a common one is found among them. Multiples denote in the record 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, ...)
So, you can see that the least common multiple of the numbers 4 and 6 is the number 24. This entry is performed 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 way to calculate the LCM.
To complete the task, it is necessary to decompose the proposed numbers into prime factors.
First you need to write out the expansion of the largest of the numbers in a line, and below it - the rest.
In the expansion of each number, there may be 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, factors that are absent in the expansion of the first one should be emphasized. a large number and then add them to it. In the presented example, a deuce is missing.
Now we 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, which are not included in the decomposition of the larger number, will be the least common multiple.
To find the LCM of three or more numbers, all of them should be decomposed 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 deuces from the decomposition of sixteen were not included in the factorization of a larger number (one is in the decomposition of twenty-four).
Thus, they need to be added to the decomposition 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, NOCs of twelve and twenty-four would be twenty-four.
If it is necessary to find the least common multiple of coprime numbers that do not have the same divisors, then their LCM will be equal to their product.
For example, LCM(10, 11) = 110.
Let's continue the discussion about the least common multiple that we started in the LCM - Least Common Multiple, Definition, Examples section. In this topic, we will look at ways to find the LCM for three numbers or more, we will analyze the question of how to find the LCM of a negative number.
Yandex.RTB R-A-339285-1
Calculation of the least common multiple (LCM) through gcd
We have already established the relationship between the least common multiple and the greatest common divisor. Now let's learn how to define the LCM through the 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) \u003d a b: GCD (a, b) .
Example 1
It is necessary to find the LCM of the numbers 126 and 70.
Solution
Let's take a = 126 , b = 70 . Substitute the values in 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 the numbers 70 and 126. For this we need the Euclid algorithm: 126 = 70 1 + 56 , 70 = 56 1 + 14 , 56 = 14 4 , hence gcd (126 , 70) = 14 .
Let's calculate the LCM: LCM (126, 70) = 126 70: GCD (126, 70) = 126 70: 14 = 630.
Answer: LCM (126, 70) = 630.
Example 2
Find the nok of the numbers 68 and 34.
Solution
GCD in this case Finding it is easy, since 68 is divisible by 34. 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, then the LCM of these numbers will be equal to the first number.
Finding the LCM by Factoring Numbers into Prime Factors
Now let's look at a way to find the LCM, which is based on the decomposition of numbers into prime factors.
Definition 2
To find the least common multiple, we need to perform a number of simple steps:
- we make up the product of all prime factors of numbers for which we need to find the LCM;
- we exclude all prime factors from their obtained products;
- the product obtained after eliminating the common prime factors will be equal to the LCM of the given numbers.
This way 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 factors that are involved in the expansion 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 out like this: 75 = 3 5 5 And 210 = 2 3 5 7. If you make 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 , decomposing 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 the factors that participated in the expansion of these numbers will look like: 2 2 3 3 5 5 7 7 7. Let's find the common factors. This number is 7 . Let's exclude it from common 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: LCM (441 , 700) = 44 100 .
Let us give one more 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 decompose 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 get the product, which will be the desired LCM of two numbers.
Example 5
Let's go back 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 number 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 decompose the numbers from the condition into prime factors: 84 = 2 2 3 7 And 648 = 2 2 2 3 3 3 3. Add to the product of 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) = 4536.
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 consistently find the LCM of two numbers. There is a theorem for this case.
Theorem 1
Suppose we have integers a 1 , a 2 , … , a k. NOC m k of these numbers is found in sequential calculation 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 specific problems.
Example 7
You need to calculate the least common multiple of the four numbers 140 , 9 , 54 and 250 .
Solution
Let's introduce the notation: a 1 \u003d 140, a 2 \u003d 9, a 3 \u003d 54, a 4 \u003d 250.
Let's start by calculating m 2 = LCM (a 1 , a 2) = LCM (140 , 9) . Let's use 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, LCM(140, 9) = 140 9: GCD(140, 9) = 140 9: 1 = 1260. Therefore, m 2 = 1 260 .
Now let's calculate according to the same algorithm m 3 = LCM (m 2 , a 3) = LCM (1 260 , 54) . In the course of calculations, we get m 3 = 3 780.
It remains for us to calculate m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250) . We act according to the same algorithm. We get m 4 \u003d 94 500.
The LCM of the four numbers from the example condition is 94500 .
Answer: LCM (140, 9, 54, 250) = 94,500.
As you can see, the calculations are simple, but quite laborious. To save time, you can go the other way.
Definition 4
We offer you the following algorithm of actions:
- decompose all numbers into prime factors;
- to the product of the factors of the first number, add the missing factors from the product of the second number;
- add the missing factors of the third number to the product obtained at the previous stage, etc.;
- the resulting product will be the least common multiple of all numbers from the condition.
Example 8
It is necessary to find the LCM of five numbers 84 , 6 , 48 , 7 , 143 .
Solution
Let's decompose 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 have 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. We turn to the number 48, from the product of prime factors of which we take 2 and 2. Then we add a simple factor of 7 from the fourth number and 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 five original 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 should be carried out according to 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 it is accepted that a And − a- opposite numbers
then the set of multiples a coincides with 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 change 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 Euclid algorithm.
We get that the LCM of numbers − 145 and − 45 equals 1 305 .
Answer: LCM (− 145 , − 45) = 1 305 .
If you notice a mistake in the text, please highlight it and press Ctrl+Enter
