Numbers for finding nok. How to find the least common multiple, nok for two or more numbers

Finding the NOC

In order to find common denominator When adding and subtracting fractions with different denominators, you must know and be able to calculate least common multiple (LCM).

A multiple of a is a number that is itself divisible by a without a remainder.
Numbers that are multiples of 8 (that is, these numbers are divisible by 8 without a remainder): these are the numbers 16, 24, 32...
Multiples of 9: 18, 27, 36, 45...

There are infinitely many multiples of a given number a, in contrast to the divisors of the same number. There is a finite number of divisors.

A common multiple of two natural numbers is a number that is divisible by both of these numbers.

The least common multiple (LCM) of two or more natural numbers is the smallest natural number that is itself divisible by each of these numbers.

How to find NOC
LCM can be found and written in two ways.

The first way to find the LOC
This method is usually used for small numbers.
1. Write down the multiples for each number on a line until you find a multiple that is the same for both numbers.
2. A multiple of a is denoted by the capital letter “K”.

K(a) = (...,...)
Example. Find LOC 6 and 8.
K (6) = (12, 18, 24, 30, ...)

K(8) = (8, 16, 24, 32, ...)

LCM(6, 8) = 24

The second way to find the LOC
This method is convenient to use to find the LCM for three or more numbers.
1. Divide the given numbers into simple multipliers. You can read more about the rules for factoring into prime factors in the topic of how to find the greatest common divisor (GCD).

2. Write down the factors included in the expansion on a line the biggest of numbers, and below it is the decomposition of the remaining numbers.

The number of identical factors in decompositions of numbers can be different.

60 = 2 . 2 . 3 . 5

24 = 2 . 2 . 2 . 3
3. Emphasize in decomposition less numbers (smaller numbers) factors that were not included in the expansion of the larger number (in our example it is 2) and add these factors to the expansion of the larger number.
LCM(24, 60) = 2. 2. 3. 5 . 2
4. Write down the resulting product as an answer.
Answer: LCM (24, 60) = 120

You can also formalize finding the least common multiple (LCM) as follows. Let's find the LCM (12, 16, 24).

24 = 2 . 2 . 2 . 3

16 = 2 . 2 . 2 . 2

12 = 2 . 2 . 3

As we see from the decomposition of numbers, all factors of 12 are included in the decomposition of 24 (the largest of the numbers), so we add only one 2 from the decomposition of the number 16 to the LCM.
LCM(12, 16, 24) = 2. 2. 2. 3. 2 = 48
Answer: LCM (12, 16, 24) = 48

Special cases of finding an NOC
1. If one of the numbers is divisible by the others, then the least common multiple of these numbers is equal to this number.
For example, LCM (60, 15) = 60
2. Since relatively prime numbers do not have common prime factors, their least common multiple is equal to the product of these numbers.
Example.
LCM(8, 9) = 72

Let's consider solving the following problem. The boy's step is 75 cm, and the girl's step is 60 cm. It is necessary to find the smallest distance at which they both take an integer number of steps.

Solution. The entire path that the guys will go through must be divisible by 60 and 70, since they must each take an integer number of steps. In other words, the answer must be a multiple of both 75 and 60.

First, we will write down all the multiples of the number 75. We get:

75, 150, 225, 300, 375, 450, 525, 600, 675, … .

Now let's write down the numbers that will be multiples of 60. We get:

60, 120, 180, 240, 300, 360, 420, 480, 540, 600, 660, … .

Now we find the numbers that are in both rows.

Common multiples of numbers would be 300, 600, etc.

The smallest of them is the number 300. In this case, it will be called the least common multiple of the numbers 75 and 60.

Returning to the condition of the problem, the shortest distance at which the guys will take an integer number of steps will be 300 cm. The boy will cover this path in 4 steps, and the girl will need to take 5 steps.

Determining Least Common Multiple

The least common multiple of two natural numbers a and b is the smallest natural number that is a multiple of both a and b.

In order to find the least common multiple of two numbers, it is not necessary to write down all the multiples of these numbers in a row.

You can use the following method.

How to find the least common multiple

First you need to factor these numbers into prime factors.

60 = 2*2*3*5,
75=3*5*5.

Now let’s write down all the factors that are in the expansion of the first number (2,2,3,5) and add to it all the missing factors from the expansion of the second number (5).

As a result, we get a series of prime numbers: 2,2,3,5,5. The product of these numbers will be the least common factor for these numbers. 2*2*3*5*5 = 300.

General scheme for finding the least common multiple

1. Divide numbers into prime factors.
2. Write down the prime factors that are part of one of them.
3. Add to these factors all those that are in the expansion of the others, but not in the selected one.
4. Find the product of all the written factors.

This method is universal. It can be used to find the least common multiple of any number of natural numbers.

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.

A multiple is a number that is divisible by a given number without a remainder. The least common multiple (LCM) of a group of numbers is the smallest number that is divisible by each number in the group without leaving a remainder. To find the least common multiple, you need to find the prime factors of given numbers. The LCM can also be calculated using a number of other methods that apply to groups of two or more numbers.

Steps

Series of multiples

Look at these numbers. The method described here is best used when given two numbers, each of which is less than 10. If larger numbers are given, use a different method.

For example, find the least common multiple of 5 and 8. These are small numbers, so you can use this method.

A multiple is a number that is divisible by a given number without a remainder. Multiples can be found in the multiplication table.
- For example, numbers that are multiples of 5 are: 5, 10, 15, 20, 25, 30, 35, 40.
Write down a series of numbers that are multiples of the first number. Do this under multiples of the first number to compare two sets of numbers.
- For example, numbers that are multiples of 8 are: 8, 16, 24, 32, 40, 48, 56, and 64.
Find the smallest number that is present in both sets of multiples. You may have to write long series of multiples to find the total number. The smallest number that is present in both sets of multiples is the least common multiple.
- For example, the smallest number that appears in the series of multiples of 5 and 8 is the number 40. Therefore, 40 is the least common multiple of 5 and 8.
Prime factorization
1. Look at these numbers. The method described here is best used when given two numbers, each of which is greater than 10. If smaller numbers are given, use a different method.
  - For example, find the least common multiple of the numbers 20 and 84. Each of the numbers is greater than 10, so you can use this method.
2. Factor into prime factors first number. That is, you need to find such prime numbers that, when multiplied, will result in a given number. Once you have found the prime factors, write them as equalities.
  
  Factor the second number into prime factors. Do this in the same way as you factored the first number, that is, find such prime numbers that, when multiplied, will yield the given number.
  
  Write down the factors common to both numbers. Write such factors as a multiplication operation. As you write each factor, cross it out in both expressions (expressions that describe factorizations of numbers into prime factors).
  
  Add the remaining factors to the multiplication operation. These are factors that are not crossed out in both expressions, that is, factors that are not common to both numbers.
  
  Calculate the least common multiple. To do this, multiply the numbers in the written multiplication operation.
Finding common factors
1. Find the divisor common to both numbers. Write it down in the first row and first column. It is better to look for prime factors, but this is not a requirement.
  - For example, 18 and 30 are even numbers, so their common factor is 2. So write 2 in the first row and first column.
2. Divide each number by the first divisor. Write each quotient under the appropriate number. A quotient is the result of dividing two numbers.
  
  Find the divisor common to both quotients. If there is no such divisor, skip the next two steps. Otherwise, write the divisor in the second row and first column.
  - For example, 9 and 15 are divisible by 3, so write 3 in the second row and first column.
3. Divide each quotient by its second divisor. Write each division result under the corresponding quotient.
  
  If necessary, add additional cells to the grid. Repeat the described steps until the quotients have a common divisor.
  
  Circle the numbers in the first column and last row of the grid. Then write the selected numbers as a multiplication operation.
Euclid's algorithm

Let's continue the conversation about the least common multiple, which we started in the section “LCM - least common multiple, definition, examples.” In this topic, we will look at ways to find the LCM for three or more numbers, and we will look at the question of how to find the LCM of a negative number.

Calculating Least Common Multiple (LCM) via GCD

We have already established the relationship between the least common multiple and the greatest common divisor. Now let's learn how to determine LCM through GCD. First, let's figure out how to do this for positive numbers.

Definition 1

You can find the least common multiple through the greatest common divisor using the formula LCM (a, b) = a · b: GCD (a, b).

Example 1

You need to find the LCM of the numbers 126 and 70.

Solution

Let's take a = 126, b = 70. Let's substitute the values into the formula for calculating the least common multiple through the greatest common divisor LCM (a, b) = a · b: GCD (a, b) .

Finds the gcd of numbers 70 and 126. For this we need the Euclidean algorithm: 126 = 70 1 + 56, 70 = 56 1 + 14, 56 = 14 4, therefore GCD (126 , 70) = 14 .

Let's calculate the LCM: LCD (126, 70) = 126 70: GCD (126, 70) = 126 70: 14 = 630.

Answer: LCM(126, 70) = 630.

Example 2

Find the number 68 and 34.

Solution

GCD in this case is not difficult to find, since 68 is divisible by 34. Let's calculate the least common multiple using the formula: LCM (68, 34) = 68 34: GCD (68, 34) = 68 34: 34 = 68.

Answer: LCM(68, 34) = 68.

In this example, we used the rule for finding the least common multiple of positive integers a and b: if the first number is divisible by the second, the LCM of those numbers will be equal to the first number.

Finding the LCM by factoring numbers into prime factors

Now let's look at the method of finding the LCM, which is based on factoring numbers into prime factors.

Definition 2

To find the least common multiple, we need to perform a number of simple steps:

we compose the product of all prime factors of the numbers for which we need to find the LCM;
we exclude all prime factors from their resulting products;
the product obtained after eliminating the common prime factors will be equal to the LCM of the given numbers.

This method of finding the least common multiple is based on the equality LCM (a, b) = a · b: GCD (a, b). If you look at the formula, it will become clear: the product of the numbers a and b is equal to the product of all the factors that participate in the decomposition of these two numbers. In this case, the gcd of two numbers is equal to the product of all prime factors that are simultaneously present in the factorizations of these two numbers.

Example 3

We have two numbers 75 and 210. We can factor them as follows: 75 = 3 5 5 And 210 = 2 3 5 7. If you compose the product of all the factors of the two original numbers, you get: 2 3 3 5 5 5 7.

If we exclude the factors common to both numbers 3 and 5, we get a product of the following form: 2 3 5 5 7 = 1050. This product will be our LCM for the numbers 75 and 210.

Example 4

Find the LCM of numbers 441 And 700 , factoring both numbers into prime factors.

Solution

Let's find all the prime factors of the numbers given in the condition:

441 147 49 7 1 3 3 7 7

700 350 175 35 7 1 2 2 5 5 7

We get two chains of numbers: 441 = 3 3 7 7 and 700 = 2 2 5 5 7.

The product of all factors that participated in the decomposition of these numbers will have the form: 2 2 3 3 5 5 7 7 7. Let's find common factors. This is the number 7. Let's exclude it from the total product: 2 2 3 3 5 5 7 7. It turns out that NOC (441, 700) = 2 2 3 3 5 5 7 7 = 44 100.

Answer: LOC(441, 700) = 44,100.

Let us give another formulation of the method for finding the LCM by decomposing numbers into prime factors.

Definition 3

Previously, we excluded from the total number of factors common to both numbers. Now we will do it differently:

Let's factor both numbers into prime factors:
add to the product of the prime factors of the first number the missing factors of the second number;
we obtain the product, which will be the desired LCM of two numbers.

Example 5

Let's return to the numbers 75 and 210, for which we already looked for the LCM in one of the previous examples. Let's break them down into simple factors: 75 = 3 5 5 And 210 = 2 3 5 7. To the product of factors 3, 5 and 5 numbers 75 add the missing factors 2 And 7 numbers 210. We get: 2 · 3 · 5 · 5 · 7 . This is the LCM of the numbers 75 and 210.

Example 6

It is necessary to calculate the LCM of the numbers 84 and 648.

Solution

Let's factor the numbers from the condition into simple factors: 84 = 2 2 3 7 And 648 = 2 2 2 3 3 3 3. Let's add to the product the factors 2, 2, 3 and 7 numbers 84 missing factors 2, 3, 3 and
3 numbers 648. We get the product 2 2 2 3 3 3 3 7 = 4536. This is the least common multiple of 84 and 648.

Answer: LCM(84, 648) = 4,536.

Finding the LCM of three or more numbers

Regardless of how many numbers we are dealing with, the algorithm of our actions will always be the same: we will sequentially find the LCM of two numbers. There is a theorem for this case.

Theorem 1

Let's assume we have integers a 1 , a 2 , … , a k. NOC m k these numbers are found by sequentially calculating m 2 = LCM (a 1, a 2), m 3 = LCM (m 2, a 3), ..., m k = LCM (m k − 1, a k).

Now let's look at how the theorem can be applied to solve specific problems.

Example 7

You need to calculate the least common multiple of four numbers 140, 9, 54 and 250 .

Solution

Let us introduce the notation: a 1 = 140, a 2 = 9, a 3 = 54, a 4 = 250.

Let's start by calculating m 2 = LCM (a 1 , a 2) = LCM (140, 9). Let's apply the Euclidean algorithm to calculate the GCD of the numbers 140 and 9: 140 = 9 15 + 5, 9 = 5 1 + 4, 5 = 4 1 + 1, 4 = 1 4. We get: GCD (140, 9) = 1, GCD (140, 9) = 140 9: GCD (140, 9) = 140 9: 1 = 1,260. Therefore, m 2 = 1,260.

Now let’s calculate using the same algorithm m 3 = LCM (m 2 , a 3) = LCM (1 260, 54). During the calculations we obtain m 3 = 3 780.

All we have to do is calculate m 4 = LCM (m 3 , a 4) = LCM (3 780, 250). We follow the same algorithm. We get m 4 = 94 500.

The LCM of the four numbers from the example condition is 94500.

Answer: NOC (140, 9, 54, 250) = 94,500.

As you can see, the calculations are simple, but quite labor-intensive. To save time, you can go another way.

Definition 4

We offer you the following algorithm of actions:

we decompose all numbers into prime factors;
to the product of the factors of the first number we add the missing factors from the product of the second number;
to the product obtained at the previous stage we add the missing factors of the third number, etc.;
the resulting product will be the least common multiple of all numbers from the condition.

Example 8

You need to find the LCM of five numbers 84, 6, 48, 7, 143.

Solution

Let's factor all five numbers into prime factors: 84 = 2 2 3 7, 6 = 2 3, 48 = 2 2 2 2 3, 7, 143 = 11 13. Prime numbers, which is the number 7, cannot be factored into prime factors. Such numbers coincide with their decomposition into prime factors.

Now let's take the product of the prime factors 2, 2, 3 and 7 of the number 84 and add to them the missing factors of the second number. We decomposed the number 6 into 2 and 3. These factors are already in the product of the first number. Therefore, we omit them.

We continue to add the missing multipliers. Let's move on to the number 48, from the product of whose prime factors we take 2 and 2. Then we add the prime factor of 7 from the fourth number and the factors of 11 and 13 of the fifth. We get: 2 2 2 2 3 7 11 13 = 48,048. This is the least common multiple of the original five numbers.

Answer: LCM (84, 6, 48, 7, 143) = 48,048.

Finding the least common multiple of negative numbers

In order to find the least common multiple of negative numbers, these numbers must first be replaced by numbers with the opposite sign, and then the calculations must be carried out using the above algorithms.

Example 9

LCM (54, − 34) = LCM (54, 34) and LCM (− 622, − 46, − 54, − 888) = LCM (622, 46, 54, 888).

Such actions are permissible due to the fact that if we accept that a And − a– opposite numbers,
then the set of multiples of a number a matches the set of multiples of a number − a.

Example 10

It is necessary to calculate the LCM of negative numbers − 145 And − 45 .

Solution

Let's replace the numbers − 145 And − 45 to their opposite numbers 145 And 45 . Now, using the algorithm, we calculate the LCM (145, 45) = 145 45: GCD (145, 45) = 145 45: 5 = 1 305, having previously determined the GCD using the Euclidean algorithm.

We get that the LCM of the numbers is − 145 and − 45 equals 1 305 .

Answer: LCM (− 145, − 45) = 1,305.

If you notice an error in the text, please highlight it and press Ctrl+Enter