How to find the LCM (least common multiple)

A common multiple of two integers is an integer that is evenly divisible by both given numbers.

The least common multiple of two integers is the smallest of all integers that is evenly divisible by both given numbers.

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 18.

This method is convenient when both numbers are small and easy to multiply by a sequence of integers. However, there are times when you need to find the LCM for two-digit or three-digit numbers, as well as when the original numbers are three or even more.

Method 2... You can find the LCM by expanding the original numbers into prime factors.
After the expansion, it is necessary to cross out the same numbers from the resulting series of prime factors. The remaining numbers of the first number will be a factor for the second, and the remaining numbers of the second will be a factor for the first.

Example for the number 75 and 60.
The least common multiple of the numbers 75 and 60 can be found without writing out the multiples of these numbers in a row. To do this, we decompose 75 and 60 into prime factors:
75 = 3 * 5 * 5, a
60 = 2 * 2 * 3 * 5 .
As you can see, factors 3 and 5 are found in both lines. Mentally we "cross out" them.
Let us write out the remaining factors included in the decomposition of each of these numbers. When expanding the number 75, we have the number 5 left, and when expanding the number 60, we have 2 * 2
So, to determine the LCM for the numbers 75 and 60, we need to multiply the remaining numbers from the decomposition of 75 (this is 5) by 60, and the numbers remaining from the decomposition of the number 60 (this is 2 * 2) multiply 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 numbers 12, 16, 24
In this case, our actions will be somewhat more complicated. But, first, as always, we factor all the numbers into prime factors
12 = 2 * 2 * 3
16 = 2 * 2 * 2 * 2
24 = 2 * 2 * 2 * 3
To correctly determine the LCM, we choose the smallest of all numbers (this is the number 12) and sequentially go through its factors, crossing them out if at least one of the other series of numbers contains the same, not yet crossed out factor.

Step 1 . We see that 2 * 2 occurs in all rows of numbers. 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. Cross out the number 3 from both rows, while for the number 16 no action is assumed.
12 = 2 * 2 * 3
16 = 2 * 2 * 2 * 2
24 = 2 * 2 * 2 * 3

As you can see, when expanding the number 12, we "crossed out" all the numbers. This means that the finding of the NOC is completed. It remains only to calculate its value.
For the number 12, we take the remaining factors of the number 16 (the closest 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.

Greatest Common Divisor and Least Common Multiple are key arithmetic concepts that make it easy to manipulate fractions. LCM and are most often used to find the common denominator of multiple fractions.

Basic concepts

The divisor of an integer X is another integer Y that divides X without a remainder. For example, the divisor of 4 is 2, and 36 is 4, 6, 9. An integer multiple of X is the number Y that is divisible by X without a remainder. For example, 3 is a multiple of 15, and 6 is 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, therefore, 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, the choice of common for a pair and the search for the largest of them;
• decomposition of numbers into indivisible factors;
• Euclid's algorithm;
• binary algorithm.

Today, the most popular in educational institutions are the prime factorization methods and the Euclidean 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 determined by sequential enumeration or factorization 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, LCM and GCD are related by the following relationship:

LCM (X, Y) = X × Y / GCD (X, Y).

For example, if GCD (15.18) = 3, then LCM (15.18) = 15 × 18/3 = 90. The most obvious example of using LCM is finding a common denominator, which is the least common multiple for given fractions.

Mutually prime numbers

If a pair of numbers has no common divisors, then such a pair is called coprime. GCD for such pairs is always equal to one, and based on the connection of divisors and multiples, the LCM for coprime is equal to their product. For example, the numbers 25 and 28 are relatively prime, because they have no common divisors, and the LCM (25, 28) = 700, which corresponds to their product. Any two indivisible numbers will always be mutually prime.

Common divisor and multiple calculator

With our calculator, you can calculate the GCD and LCM for an arbitrary number of numbers to choose from. Tasks for calculating common divisors and multiples are found in arithmetic in grades 5, 6, however, 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

The least common multiple is used to find the common denominator of multiple fractions. Suppose that 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 is reduced to the problem of finding the LCM. To do this, select 5 numbers in the calculator and enter the denominator values ​​in the corresponding cells. The program will calculate the LCM (8, 9, 12, 15, 18) = 360. Now you need to calculate the additional factors for each fraction, which are defined as the ratio of the LCM to the denominator. Thus, additional factors will look like:

• 360/8 = 45
• 360/9 = 40
• 360/12 = 30
• 360/15 = 24
• 360/18 = 20.

After that, we multiply all 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 159/360. We reduce the fraction by 3 and we 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 for integer solutions. First, check the equation 150x + 8y = 37. Using the calculator, find the GCD (150.8) = 2. Divide 37/2 = 18.5. The number is not an integer, therefore, the equation has no integer roots.

Let's check the equation 1320x + 1760y = 10120. Use the calculator to find the 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 greatest divisors and least multiples of any number of numbers.

How do I find the least common multiple?

It is necessary to find each factor of each of the two numbers for which we find the smallest common multiple, and then multiply the factors that coincide in the first and second numbers by each other. The result of the product will be the desired multiple.

For example, we have numbers 3 and 5 and we need to find the LCM (least common multiple). US need to multiply and three and five to all numbers starting from 1 2 3 ... and so on until we see the same number both there and there.

We multiply three and get: 3, 6, 9, 12, 15

We multiply the heel and get: 5, 10, 15

The prime factorization method is the most classic for finding the least common multiple (LCM) for multiple numbers. This method is clearly and simply demonstrated in the following video:

Adding, multiplying, dividing, reducing to a common denominator and other arithmetic operations is a very exciting exercise, especially the examples that take up a whole sheet are fascinating.

So find the common multiple of two numbers, which will be the smallest number that divides two numbers. I want 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 mind (and this can be trained), then the numbers themselves pop up in your head and then the fractions click like nuts.

To begin with, let's learn that you can multiply two numbers by each other, and then reduce this figure and divide it 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 clearly a larger number. Moreover, 15 is divided by 3 and 6 is divided by 3, so 90 is also divided by 3. We get 30. Trying 30 to divide 15 is 2. And 30 divide 6 is 5. Since 2 is the limit, it turns out that the smallest multiple for numbers 15 and 6 will be 30.

Bigger numbers 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 big difficulties.

• How to find the NOC

  Here's a video that shows you two ways to find the least common multiple (LCM). By practicing using the first of these methods, you can better understand what the least common multiple is.

Here's another way to find the least common multiple. Let's consider it with an illustrative example.

It is necessary to find the LCM of three numbers at once: 16, 20 and 28.

• We represent each number as the product of its prime factors:
• We write down the powers of all prime factors:

16 = 224 = 2^24^1

20 = 225 = 2^25^1

28 = 227 = 2^27^1

• We select all prime divisors (factors) with the highest powers, multiply them and find the LCM:

LCM = 2 ^ 24 ^ 15 ^ 17 ^ 1 = 4457 = 560.

LCM (16, 20, 28) = 560.

Thus, as a result of the calculation, the number 560 was obtained. It is the smallest common multiple, that is, it is divided by each of the three numbers without a remainder.

The smallest common multiple is a number that can be divided into several suggested numbers without a remainder. In order to calculate such a figure, you need to take each number and decompose it into prime factors. We remove those numbers that match. 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, which is divisible by each of these numbers without a remainder.

Here's an example of how to find the least common multiple of 30 and 42.

• The first step is to factor these numbers into prime factors.

For 30, this is 2 x 3 x 5.

For 42 - this is 2 x 3 x 7. Since 2 and 3 are in the decomposition of the number 30, we delete them.

• We write out the factors that are included in the decomposition of the number 30. This is 2 x 3 x 5.
• Now you need to multiply them by the missing factor, which we have in the decomposition of 42, and this is 7. We get 2 x 3 x 5 x 7.
• Find what is 2 x 3 x 5 x 7 and get 210.

As a result, we get that the LCM of numbers 30 and 42 is 210.

To find the least common multiple, you need to follow a few simple steps in sequence. Consider this using two numbers as an example: 8 and 12

1. We decompose both numbers into prime factors: 8 = 2 * 2 * 2 and 12 = 3 * 2 * 2
2. Reduce the same factors for one of the numbers. In our case, 2 * 2 coincide, we will reduce them for the number 12, then 12 will have one factor: 3.
3. Find the product of all remaining factors: 2 * 2 * 2 * 3 = 24

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 will try to explain it using the example of the numbers 6 and 8. The smallest 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 begin to multiply first 6 by 1, 2, 3, etc. and 8 by 1, 2, 3, etc.

The least common multiple of two numbers is directly related to the greatest common divisor of those numbers. This the relationship between the GCD and the 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: gcd (a, b).

Proof.

Let be M - any multiple of 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 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 coprime 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 divisible 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 consequences of the considered theorem.

Common multiples of two numbers are the same as multiples of their least common multiple.

This is indeed so, since any common multiple M of the numbers a and b is determined by the equality M = LCM (a, b) t for some integer value of t.

The least common multiple of coprime positive numbers a and b is equal to their product.

The rationale for this fact is fairly 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 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 common multiples of m k-1 and a k, therefore, coincide with multiples of m k. And since the smallest 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. and other 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: a textbook for students of physics and mathematics. specialties of pedagogical institutes.

The online calculator allows you to quickly find the greatest common factor and least common multiple for two or any other number of numbers.

Calculator for finding GCD and LCM

Find GCD and LCM

Found GCD and NOC: 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 button "Find GCD and LCM"

How to enter numbers

• Numbers are entered separated by a space, period or comma
• The length of the entered numbers is not limited, so finding the GCD and LCM of long numbers will not be difficult

What are GCD and NOC?

Greatest common divisor multiple numbers - this is the largest natural integer by which all original numbers are divisible without a remainder. The greatest common factor is abbreviated as Gcd.
Least common multiple multiple 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 of the divisibility properties of numbers. Then, by combining them, one can check divisibility into some of them and their combinations.

Some signs of divisibility of numbers

1. The criterion for divisibility of 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 0, 2, 4, 6, or 8, then the number is even, which means it is divisible by 2.
Example: determine if 34938 is divisible by 2.
Solution: look at the last digit: 8 - so the number is divisible by two.

2. The sign of divisibility of a number by 3
A number is divisible by 3 when the sum of its digits is divisible by three. Thus, to determine if a number is divisible by 3, you need to calculate the sum of the digits and check if it is divisible by 3. Even if the sum of the digits is very large, you can repeat the same process again.
Example: determine if 34938 is divisible by 3.
Solution: we count the sum of the digits: 3 + 4 + 9 + 3 + 8 = 27.27 is divisible by 3, which means that the number is divisible by three.

3. The sign of divisibility of a number by 5
A number is divisible by 5 when its last digit is zero or five.
Example: determine if 34938 is divisible by 5.
Solution: look at the last digit: 8 means the number is NOT divisible by five.

4. The sign of divisibility of a number by 9
This feature is very similar to the divisibility by three: a number is divisible by 9 when the sum of its digits is divisible by 9.
Example: determine if 34938 is divisible by 9.
Solution: we count the sum of the digits: 3 + 4 + 9 + 3 + 8 = 27.27 is divisible by 9, which means that the number is divisible by nine.

How to find gcd and LCM of two numbers

How to find the gcd of two numbers

The easiest way to calculate the greatest common divisor of two numbers is to find all possible divisors of those numbers and choose the largest one.

Let us consider this method using the example of finding the GCD (28, 36):

1. Factor both numbers: 28 = 1 2 2 7, 36 = 1 2 2 3 3
2. We find the common factors, that is, those that both numbers have: 1, 2 and 2.
3. 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 way is that you can write out the first multiples of two numbers, and then choose among them such 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. Find the LCM for the same numbers 28 and 36:

1. Find the product of the numbers 28 and 36: 28 36 = 1008
2. GCD (28, 36), as is already known, is equal to 4
3. LCM (28, 36) = 1008/4 = 252.

Finding GCD and LCM for several numbers

The greatest common factor can be found for several numbers, not just two. For this, the numbers to be searched for the greatest common factor are decomposed into prime factors, then the product of the common prime factors of these numbers is found. Also, to find the GCD of several numbers, you can use the following relationship: 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.

1. First, factor the numbers: 12 = 1 2 2 3, 32 = 1 2 2 2 2 2 2, 36 = 1 2 2 3 3 3.
2. Let's find the common factors: 1, 2 and 2.
3. Their product will give GCD: 1 2 2 = 4
4. Let us now find the LCM: for this, we first find the LCM (12, 32): 12 · 32/4 = 96.
5. To find the LCM of all three numbers, you need to find the GCD (96, 36): 96 = 1 2 2 2 2 2 2 3, 36 = 1 2 2 3 3, GCD = 1 2 2 3 = 12.
6. LCM (12, 32, 36) = 96 36/12 = 288.