How to find the least common multiple?
How to find NOC
Here is a video that will give you two ways to find the least common multiple (LCM). After practicing using the first of the suggested methods, you can better understand what the least common multiple is.
- We represent each number as a product of its prime factors:
- We write down the powers of all prime factors:
- We select all prime divisors (multipliers) with the greatest powers, multiply them and find the LCM:
- The first step is to factor these numbers into prime factors.
- We write out the factors that are included in the expansion of the number 30. This is 2 x 3 x 5.
- Now we need to multiply them by the missing factor, which we have when expanding 42, which is 7. We get 2 x 3 x 5 x 7.
- We find what 2 x 3 x 5 x 7 is equal to and get 210.
- We factor both numbers into prime factors: 8=2*2*2 and 12=3*2*2
- We reduce the same factors of one of the numbers. In our case, 2 * 2 coincide, let’s reduce them for the number 12, then 12 will have one factor left: 3.
- Find the product of all remaining factors: 2*2*2*3=24
We need to find each factor of each of the two numbers for which we find the least common multiple, and then multiply by each other the factors that coincide in the first and second numbers. The result of the product will be the required multiple.
For example, we have the numbers 3 and 5 and we need to find the LCM (least common multiple). Us need to multiply and three and five for all numbers starting from 1 2 3 ... and so on until we see the same number in both places.
Multiply three and get: 3, 6, 9, 12, 15
Multiply by five and get: 5, 10, 15
The prime factorization method is the most classic method for finding the least common multiple (LCM) of several numbers. This method is clearly and simply demonstrated in the following video:
Adding, multiplying, dividing, reducing to a common denominator and other arithmetic operations are a very exciting activity; the examples that take up an entire sheet of paper are especially fascinating.
So find the common multiple of two numbers, which will be the smallest number by which the two numbers are divided. I would like to note that it is not necessary to resort to formulas in the future to find what you are looking for, if you can count in your head (and this can be trained), then the numbers themselves pop up in your head and then the fractions crack like nuts.
To begin with, let's learn that you can multiply two numbers by each other, and then reduce this figure and divide alternately by these two numbers, so we will find the smallest multiple.
For example, two numbers 15 and 6. Multiply and get 90. This is obvious larger number. Moreover, 15 is divisible by 3 and 6 is divisible by 3, which means we also divide 90 by 3. We get 30. We try 30 divide 15 equals 2. And 30 divide 6 equals 5. Since 2 is the limit, it turns out that the least multiple for numbers is 15 and 6 will be 30.
With larger numbers it will be a little more difficult. but if you know which numbers give a zero remainder when dividing or multiplying, then, in principle, there are no great difficulties.
I present another way to find the least common multiple. Let's look at it with a clear example.
You need to find the LCM of three numbers at once: 16, 20 and 28.
16 = 224 = 2^24^1
20 = 225 = 2^25^1
28 = 227 = 2^27^1
LCM = 2^24^15^17^1 = 4457 = 560.
LCM(16, 20, 28) = 560.
Thus, the result of the calculation was the number 560. It is the least common multiple, that is, it is divisible by each of the three numbers without a remainder.
The least common multiple is a number that can be divided into several given numbers without leaving a remainder. In order to calculate such a figure, you need to take each number and decompose it into simple factors. Those numbers that match are removed. Leaves everyone one at a time, multiply them among themselves in turn and get the desired one - the least common multiple.
NOC, or least common multiple, is the smallest natural number of two or more numbers that is divisible by each of the given numbers without a remainder.
Here is an example of how to find the least common multiple of 30 and 42.
For 30 it is 2 x 3 x 5.
For 42, this is 2 x 3 x 7. Since 2 and 3 are in the expansion of the number 30, we cross them out.
As a result, we find that the LCM of the numbers 30 and 42 is 210.
To find the least common multiple, you need to perform several simple steps in sequence. Let's look at this using two numbers as an example: 8 and 12
Checking, we make sure that 24 is divisible by both 8 and 12, and this is the smallest natural number that is divisible by each of these numbers. Here we are found the least common multiple.
I’ll try to explain using the numbers 6 and 8 as an example. The least common multiple is a number that can be divided by these numbers (in our case, 6 and 8) and there will be no remainder.
So, we first start multiplying 6 by 1, 2, 3, etc. and 8 by 1, 2, 3, etc.
The online calculator allows you to quickly find the greatest common divisor and least common multiple for two or any other number of numbers.
Calculator for finding GCD and LCM
Find GCD and LOC
Found GCD and LOC: 5806
How to use the calculator
- Enter numbers in the input field
- If you enter incorrect characters, the input field will be highlighted in red
- click the "Find GCD and LOC" button
How to enter numbers
- Numbers are entered separated by a space, period or comma
- The length of entered numbers is not limited, so finding GCD and LCM of long numbers is not difficult
What are GCD and NOC?
Greatest common divisor several numbers is the largest natural integer by which all original numbers are divisible without a remainder. The greatest common divisor is abbreviated as GCD.
Least common multiple several numbers is the smallest number that is divisible by each of the original numbers without a remainder. The least common multiple is abbreviated as NOC.
How to check that a number is divisible by another number without a remainder?
To find out whether one number is divisible by another without a remainder, you can use some properties of divisibility of numbers. Then, by combining them, you can check the divisibility of some of them and their combinations.
Some signs of divisibility of numbers
1. Divisibility test for a number by 2
To determine whether a number is divisible by two (whether it is even), it is enough to look at the last digit of this number: if it is equal to 0, 2, 4, 6 or 8, then the number is even, which means it is divisible by 2.
Example: determine whether the number 34938 is divisible by 2.
Solution: look at last digit: 8 means the number is divisible by two.
2. Divisibility test for a number by 3
A number is divisible by 3 when the sum of its digits is divisible by three. Thus, to determine whether a number is divisible by 3, you need to calculate the sum of the digits and check whether it is divisible by 3. Even if the sum of the digits is very large, you can repeat the same process again.
Example: determine whether the number 34938 is divisible by 3.
Solution: We count the sum of the numbers: 3+4+9+3+8 = 27. 27 is divisible by 3, which means the number is divisible by three.
3. Divisibility test for a number by 5
A number is divisible by 5 when its last digit is zero or five.
Example: determine whether the number 34938 is divisible by 5.
Solution: look at the last digit: 8 means the number is NOT divisible by five.
4. Divisibility test for a number by 9
This sign is very similar to the sign of divisibility by three: a number is divisible by 9 when the sum of its digits is divisible by 9.
Example: determine whether the number 34938 is divisible by 9.
Solution: We count the sum of the numbers: 3+4+9+3+8 = 27. 27 is divisible by 9, which means the number is divisible by nine.
How to find GCD and LCM of two numbers
How to find the gcd of two numbers
Most in a simple way Calculating the greatest common divisor of two numbers is to find all possible divisors of these numbers and select the largest of them.
Let's consider this method using the example of finding GCD(28, 36):
- We factor both numbers: 28 = 1·2·2·7, 36 = 1·2·2·3·3
- We find common factors, that is, those that both numbers have: 1, 2 and 2.
- We calculate the product of these factors: 1 2 2 = 4 - this is the greatest common divisor of the numbers 28 and 36.
How to find the LCM of two numbers
There are two most common ways to find the least multiple of two numbers. The first method is that you can write down the first multiples of two numbers, and then choose among them a number that will be common to both numbers and at the same time the smallest. And the second is to find the gcd of these numbers. Let's consider only it.
To calculate the LCM, you need to calculate the product of the original numbers and then divide it by the previously found GCD. Let's find the LCM for the same numbers 28 and 36:
- Find the product of numbers 28 and 36: 28·36 = 1008
- GCD(28, 36), as already known, is equal to 4
- LCM(28, 36) = 1008 / 4 = 252 .
Finding GCD and LCM for several numbers
The greatest common divisor can be found for several numbers, not just two. To do this, the numbers to be found for the greatest common divisor are decomposed into prime factors, then the product of the common prime factors of these numbers is found. You can also use the following relation to find the gcd of several numbers: GCD(a, b, c) = GCD(GCD(a, b), c).
A similar relationship applies to the least common multiple: LCM(a, b, c) = LCM(LCM(a, b), c)
Example: find GCD and LCM for numbers 12, 32 and 36.
- First, let's factorize the numbers: 12 = 1·2·2·3, 32 = 1·2·2·2·2·2, 36 = 1·2·2·3·3.
- Let's find the common factors: 1, 2 and 2.
- Their product will give GCD: 1·2·2 = 4
- Now let’s find the LCM: to do this, let’s first find the LCM(12, 32): 12·32 / 4 = 96 .
- To find the LCM of all three numbers, you need to find GCD(96, 36): 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , GCD = 1·2· 2 3 = 12.
- LCM(12, 32, 36) = 96·36 / 12 = 288.
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. Divider 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.
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:
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 a factor of 3 (the number 21), the resulting product (84) will be the smallest number that 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.
Common multiples
Simply put, any integer that is divisible by each of the given numbers is common multiple given integers.
You can find the common multiple of two or more integers.
Example 1
Calculate the common multiple of two numbers: $2$ and $5$.
Solution.
By definition, the common multiple of $2$ and $5$ is $10$, because it is a multiple of the number $2$ and the number $5$:
Common multiples of the numbers $2$ and $5$ will also be the numbers $–10, 20, –20, 30, –30$, etc., because all of them are divided into numbers $2$ and $5$.
Note 1
Zero is a common multiple of any number of non-zero integers.
According to the properties of divisibility, if a certain number is a common multiple of several numbers, then the number opposite in sign will also be a common multiple of the given numbers. This can be seen from the example considered.
For given integers, you can always find their common multiple.
Example 2
Calculate the common multiple of $111$ and $55$.
Solution.
Let's multiply the given numbers: $111\div 55=6105$. It is easy to verify that the number $6105$ is divisible by the number $111$ and the number $55$:
$6105\div 111=$55;
$6105\div 55=$111.
Thus, $6105$ is a common multiple of $111$ and $55$.
Answer: The common multiple of $111$ and $55$ is $6105$.
But, as we have already seen from the previous example, this common multiple is not one. Other common multiples would be $–6105, 12210, –12210, 61050, –61050$, etc. Thus, we came to the following conclusion:
Note 2
Any set of integers has an infinite number of common multiples.
In practice, they are limited to finding common multiples of only positive integer (natural) numbers, because set of multiples given number and its opposite coincide.
Determining Least Common Multiple
Of all the multiples of given numbers, the least common multiple (LCM) is used most often.
Definition 2
The least positive common multiple of given integers is least common multiple these numbers.
Example 3
Calculate the LCM of the numbers $4$ and $7$.
Solution.
Because these numbers don't have common divisors, then $NOK(4,7)=28$.
Answer: $NOK (4,7)=28$.
Finding NOC via GCD
Because there is a connection between LCM and GCD, with its help you can calculate LCM of two positive integers:
Note 3
Example 4
Calculate the LCM of the numbers $232$ and $84$.
Solution.
Let's use the formula to find the LCM through GCD:
$LCD (a,b)=\frac(a\cdot b)(GCD (a,b))$
Let's find the GCD of the numbers $232$ and $84$ using the Euclidean algorithm:
$232=84\cdot 2+64$,
$84=64\cdot 1+20$,
$64=20\cdot 3+4$,
Those. $GCD(232, 84)=4$.
Let's find $LCC (232, 84)$:
$NOK (232.84)=\frac(232\cdot 84)(4)=58\cdot 84=4872$
Answer: $NOK (232.84)=$4872.
Example 5
Compute $LCD(23, 46)$.
Solution.
Because $46$ is divisible by $23$, then $gcd (23, 46)=23$. Let's find the LOC:
$NOK (23.46)=\frac(23\cdot 46)(23)=46$
Answer: $NOK (23.46)=$46.
Thus, one can formulate rule:
Note 4
Greatest common divisor and 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 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 at educational institutions The most popular are the methods of prime factorization 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 in 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 greatest divisors and least multiples of any number of numbers.
Loading...