Finding the least common multiple of three numbers. Nod and nod of three or more numbers

How to find LCM (least common multiple)

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

The least common multiple of two integers is the smallest of all integers that is divisible by both given numbers without leaving a remainder.

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

This method is convenient when both numbers are small and it is easy to multiply them by a sequence of integers. However, there are cases when you need to find the LCM for two-digit or three-digit numbers, and also when there are three or even more initial numbers.

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

Example for numbers 75 and 60.
The least common multiple of the numbers 75 and 60 can be found without writing down the multiples of these numbers in a row. To do this, let’s factor 75 and 60 into simple factors:
75 = 3 * 5 * 5, a
60 = 2 * 2 * 3 * 5 .
As you can see, factors 3 and 5 appear in both rows. We mentally “cross out” them.
Let us write down the remaining factors included in the expansion of each of these numbers. When decomposing the number 75, we are left with the number 5, and when decomposing the number 60, we are left with 2 * 2
This means that in order to determine the LCM for the numbers 75 and 60, we need to multiply the remaining numbers from the expansion of 75 (this is 5) by 60, and multiply the numbers remaining from the expansion of 60 (this is 2 * 2) 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 the numbers 12, 16, 24
In this case, our actions will be somewhat more complicated. But first, as always, let’s factorize all the numbers
12 = 2 * 2 * 3
16 = 2 * 2 * 2 * 2
24 = 2 * 2 * 2 * 3
To correctly determine the LCM, we select the smallest of all numbers (this is the number 12) and sequentially go through its factors, crossing them out if in at least one of the other rows of numbers we encounter the same factor that has not yet been crossed out.

Step 1 . We see that 2 * 2 occurs in all series of numbers. Let's 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. We cross out the number 3 from both rows, while no actions are expected for the number 16.
12 = 2 * 2 * 3
16 = 2 * 2 * 2 * 2
24 = 2 * 2 * 2 * 3

As you can see, when decomposing the number 12, we “crossed out” all the numbers. This means that the finding of the LOC is completed. All that remains is to calculate its value.
For the number 12, take the remaining factors of the number 16 (next 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.

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:

  1. Determine the largest number from the given numbers.
  2. 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:

  1. First, find the LCM of any two of these numbers.
  2. Then, LCM of the found least common multiple and the third given number.
  3. Then, the LCM of the resulting least common multiple and the fourth number, etc.
  4. 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 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.

We call numbers that are divisible by 10 multiples of 10. For example, 30 or 50 are multiples of 10. 28 is a multiple of 14. Numbers that are divisible by both 10 and 14 are naturally called common multiples of 10 and 14.

We can find as many common multiples as we want. For example, 140, 280, etc.

A natural question is: how to find the smallest common multiple, the least common multiple?

Of the multiples found for 10 and 14, the smallest so far is 140. But is it the least common multiple?

Let's factor our numbers:

Let's construct a number that is divisible by 10 and 14. To be divisible by 10, you need to have factors of 2 and 5. To be divisible by 14, you need to have factors of 2 and 7. But 2 is already there, all you have to do is add 7. The resulting number 70 is the common multiple of 10 and 14. However, it will not be possible to construct a number smaller than this so that it is also a common multiple.

So this is it least common multiple. For this we use the notation NOC.

Let's find GCD and LCM for numbers 182 and 70.

Calculate for yourself:

3.

We check:

To understand what GCD and LCM are, you cannot do without factorization. But, when we already understand what it is, it is no longer necessary to factor it every time.

For example:

You can easily verify that for two numbers, where one is divisible by the other, the smaller one is their GCD and the larger one is their LCM. Try to explain yourself why this is so.

The step length of a dad is 70 cm, and that of a little daughter is 15 cm. They start walking with their feet on the same mark. How far will they walk before their legs are level again?

Dad and daughter start moving. At first, the legs are on the same mark. After walking a few steps, their feet returned to the same level. This means that both dad and daughter got a whole number of steps to reach this mark. This means that the distance to her should be divided by the step length of both father and daughter.

That is, we must find:

That is, this will happen in 210 cm = 2 m 10 cm.

It is not difficult to understand that the father will take 3 steps, and the daughter will take 14 (Fig. 1).

Rice. 1. Illustration for the problem

Problem 1

Petya has 100 friends on the VKontakte network, and Vanya has 200. How many friends do Petya and Vanya have together, if they have 30 mutual friends?

Answer 300 is incorrect because they may have mutual friends.

Let's solve this problem like this. Let's depict a set of all Petya's friends around. Let's depict Vanya's many friends in another, larger circle.

These circles have a common part. There are mutual friends there. This common part is called the "intersection" of two sets. That is, the set of mutual friends is the intersection of the sets of everyone’s friends.

Rice. 2. Circles of many friends

If there are 30 mutual friends, then 70 on the left are friends only of Petina, and 170 are friends of only Vanina (see Fig. 2).

How much in total?

The entire large set consisting of two circles is called the union of two sets.

In fact, VK itself solves the problem of intersection of two sets for us; it immediately indicates many mutual friends when you visit another person’s page.

The situation with the GCD and LCM of two numbers is very similar.

Problem 2

Consider two numbers: 126 and 132.

We depict their prime factors in circles (see Fig. 3).

Rice. 3. Circles with prime factors

The intersection of sets is their common divisors. GCD consists of them.

The union of two sets gives us the LCM.

Bibliography

1. Vilenkin N.Ya., Zhokhov V.I., Chesnokov A.S., Shvartsburd S.I. Mathematics 6. - M.: Mnemosyne, 2012.

2. Merzlyak A.G., Polonsky V.V., Yakir M.S. Mathematics 6th grade. - Gymnasium. 2006.

3. Depman I.Ya., Vilenkin N.Ya. Behind the pages of a mathematics textbook. - M.: Education, 1989.

4. Rurukin A.N., Tchaikovsky I.V. Assignments for the mathematics course for grades 5-6. - M.: ZSh MEPhI, 2011.

5. Rurukin A.N., Sochilov S.V., Tchaikovsky K.G. Mathematics 5-6. A manual for 6th grade students at the MEPhI correspondence school. - M.: ZSh MEPhI, 2011.

6. Shevrin L.N., Gein A.G., Koryakov I.O., Volkov M.V. Mathematics: Textbook-interlocutor for 5-6 grades of secondary school. - M.: Education, Mathematics Teacher Library, 1989.

3. Website “School Assistant” ()

Homework

1. Three tourist boat voyages begin in the port city, the first of which lasts 15 days, the second - 20 and the third - 12 days. Having returned to the port, the ships set off again on the same day. Today, ships left the port on all three routes. In how many days will they go sailing together again for the first time? How many trips will each ship make?

2. Find the LCM of the numbers:

3. Find the prime factors of the least common multiple:

And if: , , .

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: 11074

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: We look at the last digit: 8 - that 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

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's consider this method using the example of finding GCD(28, 36):

  1. We factor both numbers: 28 = 1·2·2·7, 36 = 1·2·2·3·3
  2. We find 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 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:

  1. Find the product of numbers 28 and 36: 28·36 = 1008
  2. GCD(28, 36), as already known, is equal to 4
  3. 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.

  1. First, let's factorize the numbers: 12 = 1·2·2·3, 32 = 1·2·2·2·2·2, 36 = 1·2·2·3·3.
  2. Let's find the common factors: 1, 2 and 2.
  3. Their product will give GCD: 1·2·2 = 4
  4. Now let’s find the LCM: to do this, let’s first find the LCM(12, 32): 12·32 / 4 = 96 .
  5. 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.
  6. LCM(12, 32, 36) = 96·36 / 12 = 288.