Least common multiple calculator. Why introduce the concepts of "Greatest Common Divisor (GCD)" and "Least Common Multiple (LCM)" of numbers in a school mathematics course

60=2*2*3*5
75=3*5*5
2) We write out the factors included in the expansion of the first of these numbers and add to them the missing factor 5 from the expansion of the second number. We get: 2*2*3*5*5=300. Found NOC, i.e. this sum = 300. Do not forget the dimension and write the answer:
Answer: Mom gives 300 rubles each.

Definition of GCD: Greatest Common Divisor (GCD) natural numbers a and in name the largest natural number c, to which and a, and b divided without remainder. Those. c is the smallest natural number for which and a and b are multiples.

Reminder: There are two approaches to the definition of natural numbers

• numbers used in: enumeration (numbering) of items (first, second, third, ...); - in schools, usually.
• indicating the number of items (no pokemon - zero, one pokemon, two pokemon, ...).

Negative and non-integer (rational, real, ...) numbers are not natural. Some authors include zero in the set of natural numbers, others do not. The set of all natural numbers is usually denoted by the symbol N

Reminder: Divisor of a natural number a call the number b, to which a divided without remainder. Multiple of natural number b called a natural number a, which is divided by b without a trace. If number b- number divisor a, then a multiple of b. Example: 2 is a divisor of 4 and 4 is a multiple of 2. 3 is a divisor of 12, and 12 is a multiple of 3.
Reminder: Natural numbers are called prime if they are divisible without remainder only by themselves and by 1. Coprime are numbers that have only one common divisor equal to 1.

Definition of how to find the GCD in the general case: To find GCD (Greatest Common Divisor) Several natural numbers are needed:
1) Decompose them into prime factors. (The Prime Number Chart can be very helpful for this.)
2) Write out the factors included in the expansion of one of them.
3) Delete those that are not included in the expansion of the remaining numbers.
4) Multiply the factors obtained in paragraph 3).

Task 2 on (NOK): By the new year, Kolya Puzatov bought 48 hamsters and 36 coffee pots in the city. Fekla Dormidontova, as the most honest girl in the class, was given the task of dividing this property into the largest possible number of gift sets for teachers. What is the number of sets? What is the composition of the sets?

Example 2.1. solving the problem of finding GCD. Finding GCD by selection.
Solution: Each of the numbers 48 and 36 must be divisible by the number of gifts.
1) Write out the divisors 48: 48, 24, 16, 12 , 8, 6, 3, 2, 1
2) Write out the divisors 36: 36, 18, 12 , 9, 6, 3, 2, 1 Choose the greatest common divisor. Op-la-la! Found, this is the number of sets of 12 pieces.
3) Divide 48 by 12, we get 4, divide 36 by 12, we get 3. Do not forget the dimension and write the answer:
Answer: You will get 12 sets of 4 hamsters and 3 coffee pots in each set.

The greatest common divisor and the least common multiple are key arithmetic concepts that allow you to easily operate with 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, in educational institutions, the most popular methods of decomposition into prime factors 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 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 relationship:

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 and 6, however, GCD and LCM are the key concepts of 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 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 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 material presented below is a logical continuation of the theory from the article under the heading LCM - least common multiple, definition, examples, relationship between LCM and GCD. Here we will talk about finding the least common multiple (LCM), and pay special attention to solving examples. Let us first show how the LCM of two numbers is calculated in terms of the GCD of these numbers. Next, consider finding the least common multiple by factoring numbers into prime factors. After that, we will focus on finding the LCM of three or more numbers, and also pay attention to the calculation of the LCM of negative numbers.

Page navigation.

Calculation of the least common multiple (LCM) through gcd

One way to find the least common multiple is based on the relationship between LCM and GCD. The existing relationship between LCM and GCD allows you to calculate the least common multiple of two positive integers through the known greatest common divisor. The corresponding formula has the form LCM(a, b)=a b: GCM(a, b) . Consider examples of finding the LCM according to the above formula.

Example.

Find the least common multiple of the two numbers 126 and 70 .

Solution.

In this example a=126 , b=70 . Let us use the relationship between LCM and GCD expressed by the formula LCM(a, b)=a b: GCM(a, b). That is, first we have to find the greatest common divisor of the numbers 70 and 126, after which we can calculate the LCM of these numbers according to the written formula.

Find gcd(126, 70) using Euclid's algorithm: 126=70 1+56 , 70=56 1+14 , 56=14 4 , hence gcd(126, 70)=14 .

Now we find the required least common multiple: LCM(126, 70)=126 70: GCM(126, 70)= 126 70:14=630 .

Answer:

LCM(126, 70)=630 .

Example.

What is LCM(68, 34) ?

Solution.

Because 68 is evenly divisible by 34 , then gcd(68, 34)=34 . Now we calculate the least common multiple: LCM(68, 34)=68 34: LCM(68, 34)= 68 34:34=68 .

Answer:

LCM(68, 34)=68 .

Note that the previous example fits the following rule for finding the LCM for positive integers a and b : if the number a is divisible by b , then the least common multiple of these numbers is a .

Finding the LCM by Factoring Numbers into Prime Factors

Another way to find the least common multiple is based on factoring numbers into prime factors. If we make a product of all prime factors of these numbers, after which we exclude from this product all common prime factors that are present in the expansions of these numbers, then the resulting product will be equal to the least common multiple of these numbers.

The announced rule for finding the LCM follows from the equality LCM(a, b)=a b: GCM(a, b). Indeed, the product of the numbers a and b is equal to the product of all the factors involved in the expansions of the numbers a and b. In turn, gcd(a, b) is equal to the product of all prime factors that are simultaneously present in the expansions of the numbers a and b (which is described in the section on finding the gcd using the decomposition of numbers into prime factors).

Let's take an example. Let we know that 75=3 5 5 and 210=2 3 5 7 . Compose the product of all factors of these expansions: 2 3 3 5 5 5 7 . Now we exclude from this product all the factors that are present both in the expansion of the number 75 and in the expansion of the number 210 (such factors are 3 and 5), then the product will take the form 2 3 5 5 7 . The value of this product is equal to the least common multiple of the numbers 75 and 210, that is, LCM(75, 210)= 2 3 5 5 7=1 050.

Example.

After factoring the numbers 441 and 700 into prime factors, find the least common multiple of these numbers.

Solution.

Let's decompose the numbers 441 and 700 into prime factors:

We get 441=3 3 7 7 and 700=2 2 5 5 7 .

Now let's make a product of all the factors involved in the expansions of these numbers: 2 2 3 3 5 5 7 7 7 . Let us exclude from this product all the factors that are simultaneously present in both expansions (there is only one such factor - this is the number 7): 2 2 3 3 5 5 7 7 . In this way, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

Answer:

LCM(441, 700)= 44 100 .

The rule for finding the LCM using the decomposition of numbers into prime factors can be formulated a little differently. If we add the missing factors from the expansion of the number b to the factors from the decomposition of the number a, then the value of the resulting product will be equal to the least common multiple of the numbers a and b.

For example, let's take all the same numbers 75 and 210, their expansions into prime factors are as follows: 75=3 5 5 and 210=2 3 5 7 . To the factors 3, 5 and 5 from the expansion of the number 75, we add the missing factors 2 and 7 from the expansion of the number 210, we get the product 2 3 5 5 7 , the value of which is LCM(75, 210) .

Example.

Find the least common multiple of 84 and 648.

Solution.

We first obtain the decomposition of the numbers 84 and 648 into prime factors. They look like 84=2 2 3 7 and 648=2 2 2 3 3 3 3 . To the factors 2 , 2 , 3 and 7 from the expansion of the number 84 we add the missing factors 2 , 3 , 3 and 3 from the expansion of the number 648 , we get the product 2 2 2 3 3 3 3 7 , which is equal to 4 536 . Thus, the desired least common multiple of the numbers 84 and 648 is 4,536.

Answer:

LCM(84, 648)=4 536 .

Finding the LCM of three or more numbers

The least common multiple of three or more numbers can be found by successively finding the LCM of two numbers. Recall the corresponding theorem, which gives a way to find the LCM of three or more numbers.

Theorem.

Let positive integers a 1 , a 2 , …, a k be given, the least common multiple m k of these numbers is found in the sequential calculation m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , a k) .

Consider the application of this theorem on the example of finding the least common multiple of four numbers.

Example.

Find the LCM of the four numbers 140 , 9 , 54 and 250 .

Solution.

In this example a 1 =140 , a 2 =9 , a 3 =54 , a 4 =250 .

First we find m 2 \u003d LCM (a 1, a 2) \u003d LCM (140, 9). To do this, using the Euclidean algorithm, we determine gcd(140, 9) , we have 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , therefore, gcd(140, 9)=1 , whence LCM(140, 9)=140 9: LCM(140, 9)= 140 9:1=1 260 . That is, m 2 =1 260 .

Now we find m 3 \u003d LCM (m 2, a 3) \u003d LCM (1 260, 54). Let's calculate it through GCD(1 260, 54) , which is also determined by the Euclidean algorithm: 1 260=54 23+18 , 54=18 3 . Then gcd(1 260, 54)=18 , whence LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . That is, m 3 \u003d 3 780.

Left to find m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250). To do this, we find GCD(3 780, 250) using the Euclid algorithm: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Therefore, gcd(3 780, 250)=10 , whence gcd(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . That is, m 4 \u003d 94 500.

So the least common multiple of the original four numbers is 94,500.

Answer:

LCM(140, 9, 54, 250)=94,500.

In many cases, the least common multiple of three or more numbers is conveniently found using prime factorizations of given numbers. In this case, the following rule should be followed. The least common multiple of several numbers is equal to the product, which is composed as follows: the missing factors from the expansion of the second number are added to all the factors from the expansion of the first number, the missing factors from the expansion of the third number are added to the obtained factors, and so on.

Consider an example of finding the least common multiple using the decomposition of numbers into prime factors.

Example.

Find the least common multiple of five numbers 84 , 6 , 48 , 7 , 143 .

Solution.

First, we obtain the expansions of these numbers into prime factors: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 prime factors) and 143=11 13 .

To find the LCM of these numbers, to the factors of the first number 84 (they are 2 , 2 , 3 and 7 ) you need to add the missing factors from the expansion of the second number 6 . The expansion of the number 6 does not contain missing factors, since both 2 and 3 are already present in the expansion of the first number 84 . Further to the factors 2 , 2 , 3 and 7 we add the missing factors 2 and 2 from the expansion of the third number 48 , we get a set of factors 2 , 2 , 2 , 2 , 3 and 7 . There is no need to add factors to this set in the next step, since 7 is already contained in it. Finally, to the factors 2 , 2 , 2 , 2 , 3 and 7 we add the missing factors 11 and 13 from the expansion of the number 143 . We get the product 2 2 2 2 3 7 11 13 , which is equal to 48 048 .

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:

1. 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:

1. Decompose numbers into prime factors
2. 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

1. Any common multiple of $a$ and $b$ is divisible by K$(a;b)$
2. 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)$

GCD is the greatest common divisor.

To find the greatest common divisor of several numbers:

• determine the factors common to both numbers;
• find the product of common factors.

An example of finding a GCD:

Find the GCD of the numbers 315 and 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Write out the factors common to both numbers:

3. Find the product of common factors:

gcd(315; 245) = 5 * 7 = 35.

Answer: GCD(315; 245) = 35.

Finding the NOC

LCM is the least common multiple.

To find the least common multiple of several numbers:

• decompose numbers into prime factors;
• write out the factors included in the expansion of one of the numbers;
• add to them the missing factors from the expansion of the second number;
• find the product of the resulting factors.

An example of finding the NOC:

Find the LCM of the numbers 236 and 328:

1. We decompose the numbers into prime factors:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Write down the factors included in the expansion of one of the numbers and add to them the missing factors from the expansion of the second number:

2; 2; 59; 2; 41.

3. Find the product of the resulting factors:

LCM(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Answer: LCM(236; 328) = 19352.

To find the GCD (greatest common divisor) of two numbers, you need:

2. Find (underline) all common prime factors in the obtained expansions.

3. Find the product of common prime factors.

To find the LCM (least common multiple) of two numbers, you need:

1. Decompose these numbers into prime factors.

2. Supplement the expansion of one of them with those factors of the expansion of the other number, which are not in the expansion of the first.

3. Calculate the product of the obtained factors.