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 divisibility properties, 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.
Bibliography.
- 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: Textbook for students of physics and mathematics. specialties of pedagogical institutes.
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.
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. For 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 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 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)$
Greatest common divisor and least common multiple are key arithmetic concepts that make working with fractions effortless. 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 divided without leaving a remainder. For example, the divisor of 4 is 2, and 36 is 4, 6, 9. A multiple of an 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 calculations use the largest divisor GCD and the smallest multiple LCM.
The least divisor is meaningless, since for any number it is always one. The greatest multiple is also meaningless, since the sequence of multiples goes to infinity.
Finding gcd
There are many methods for finding the greatest common divisor, the most famous of which are:
- sequential search of divisors, selection of common ones for a pair and search for the largest of them;
- decomposition of numbers into indivisible factors;
- Euclidean algorithm;
- binary algorithm.
Today in educational institutions the most popular methods are decomposition into prime factors and the Euclidean algorithm. The latter, in turn, is used when solving Diophantine equations: searching for GCD is required to check the equation for the possibility of resolution in integers.
Finding the NOC
The least common multiple is also determined by sequential search or decomposition into indivisible factors. In addition, it is easy to find the LCM if the greatest divisor has already been determined. For numbers X and Y, the LCM and GCD are related by the following relationship:
LCD(X,Y) = X × Y / GCD(X,Y).
For example, if GCM(15,18) = 3, then LCM(15,18) = 15 × 18 / 3 = 90. The most obvious example of using LCM is to find the common denominator, which is the least common multiple of given fractions.
Coprime numbers
If a pair of numbers has no common divisors, then such a pair is called coprime. The gcd for such pairs is always equal to one, and based on the connection between divisors and multiples, the gcd for coprime pairs is equal to their product. For example, the numbers 25 and 28 are relatively prime, because they have no common divisors, and LCM(25, 28) = 700, which corresponds to their product. Any two indivisible numbers will always be relatively prime.
Common divisor and multiple calculator
Using our calculator you can calculate GCD and LCM for an arbitrary number of numbers to choose from. Tasks on calculating common divisors and multiples are found in 5th and 6th grade arithmetic, but GCD and LCM are key concepts in mathematics and are used in number theory, planimetry and communicative algebra.
Real life examples
Common denominator of fractions
Least common multiple is used when finding the common denominator of several fractions. Let's say in an arithmetic problem you need 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 values of the denominators in the appropriate cells. The program will calculate the LCM (8, 9, 12, 15, 18) = 360. Now you need to calculate additional factors for each fraction, which are defined as the ratio of the LCM to the denominator. So the additional multipliers would look like:
- 360/8 = 45
- 360/9 = 40
- 360/12 = 30
- 360/15 = 24
- 360/18 = 20.
After this, 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 sum such fractions and get the result as 159/360. We reduce the fraction by 3 and see the final answer - 53/120.
Solving 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 to see if they have an integer solution. First, let's 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 a 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 a big role in number theory, and the concepts themselves are widely used in a wide variety of areas of mathematics. Use our calculator to calculate the greatest divisors and least multiples of any number of numbers.