Students are given a lot of math assignments. Among them, very often there are tasks with the following formulation: there are two values. How to find the least common multiple of given numbers? It is necessary to be able to perform such tasks, since the acquired skills are used to work with fractions with different denominators. In the article, we will analyze how to find the LCM and the basic concepts.

Before finding the answer to the question of how to find the LCM, you need to define the term multiple. Most often, the formulation of this concept sounds as follows: a multiple of some value A is called such natural number, which without a remainder will be divisible by A. So, for 4 multiples will be 8, 12, 16, 20, and so on, up to the required limit.

In this case, the number of divisors for a particular value can be limited, and there are infinitely many multiples. There is also the same value for natural values. This is an indicator that is divided by them without a remainder. Having dealt with the concept of the smallest value for certain indicators, let's move on to how to find it.

Finding the NOC

The least multiple of two or more exponents is the smallest natural number that is fully divisible by all the given numbers.

There are several ways to find such a value. Let's consider the following methods:

1. If the numbers are small, then write in the line all divisible by it. Keep doing this until you find something in common among them. In the record, they are denoted by the letter K. For example, for 4 and 3, the smallest multiple is 12.
2. If these are large or you need to find a multiple for 3 or more values, then here you should use a different technique that involves decomposing numbers into prime factors. First, lay out the largest of the indicated, then all the rest. Each of them has its own number of multipliers. As an example, let's decompose 20 (2*2*5) and 50 (5*5*2). For the smaller of them, underline the factors and add to the largest. The result will be 100, which will be the least common multiple of the above numbers.
3. When finding 3 numbers (16, 24 and 36) the principles are the same as for the other two. Let's expand each of them: 16 = 2*2*2*2, 24=2*2*2*3, 36=2*2*3*3. Only two deuces from the decomposition of the number 16 were not included in the expansion of the largest. We add them and get 144, which is the smallest result for the previously indicated numerical values.

Now we know what general technique finding the smallest value for two, three or more values. However, there are also private methods, helping to search for NOCs, if the previous ones do not help.

How to find GCD and NOC.

Private Ways of Finding

As with any mathematical section, there are special cases of finding LCMs that help in specific situations:

• if one of the numbers is divisible by the others without a remainder, then the lowest multiple of these numbers is equal to it (NOC 60 and 15 is equal to 15);
• Coprime numbers do not have common prime divisors. Their smallest value is equal to the product of these numbers. Thus, for the numbers 7 and 8, this will be 56;
• the same rule works for other cases, including special ones, which can be read about in specialized literature. This should also include cases of decomposition of composite numbers, which are the subject of separate articles and even Ph.D. dissertations.

Special cases are less common than standard examples. But thanks to them, you can learn how to work with fractions of varying degrees of complexity. This is especially true for fractions., where there are different denominators.

Some examples

Let's look at a few examples, thanks to which you can understand the principle of finding the smallest multiple:

1. We find LCM (35; 40). We lay out first 35 = 5*7, then 40 = 5*8. We add 8 to the smallest number and get the NOC 280.
2. NOC (45; 54). We lay out each of them: 45 = 3*3*5 and 54 = 3*3*6. We add the number 6 to 45. We get the NOC equal to 270.
3. Well, the last example. There are 5 and 4. There are no simple multiples for them, so the least common multiple in this case will be their product, equal to 20.

Thanks to examples, you can understand how the NOC is located, what are the nuances and what is the meaning of such manipulations.

Finding the NOC is much easier than it might seem at first. For this, both a simple expansion and the multiplication of simple values ​​\u200b\u200bto each other are used.. The ability to work with this section of mathematics helps with the further study of mathematical topics, especially fractions. varying degrees difficulties.

Do not forget to periodically solve examples with different methods, this develops the logical apparatus and allows you to remember numerous terms. Learn methods for finding such an indicator and you will be able to work well with the rest of the mathematical sections. Happy learning math!

Video

This video will help you understand and remember how to find the least common multiple.

The least common multiple of two numbers is directly related to the greatest common divisor of those numbers. This link between GCD and 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: GCM(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.

Denote gcd(a, b) as d . Then we can write down 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. Therefore, 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 the properties of divisibility, is equivalent to the condition that a 1 k is divisible by b 1 .

We also need to write down two important corollaries from the considered theorem.

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

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

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

The rationale for this fact is quite 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 successively 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 numbers m k-1 and a k , therefore, coincide with multiples of m k . And since the least 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. etc. 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: Tutorial for students of physics and mathematics. specialties of pedagogical institutes.

Second number: b=

Digit separator No space separator " ´

Result:

Greatest Common Divisor gcd( a,b)=6

Least common multiple of LCM( a,b)=468

The largest natural number by which the numbers a and b are divisible without remainder is called greatest common divisor(gcd) of these numbers. Denoted gcd(a,b), (a,b), gcd(a,b) or hcf(a,b).

Least common multiple(LCM) of two integers a and b is the smallest natural number that is divisible by a and b without a remainder. Denoted LCM(a,b), or lcm(a,b).

Integers a and b are called coprime if they have no common divisors other than +1 and −1.

Greatest Common Divisor

Let two positive numbers be given a 1 and a 2 1). It is required to find a common divisor of these numbers, i.e. find such a number λ , which divides the numbers a 1 and a 2 at the same time. Let's describe the algorithm.

1) In this article, the word number will mean an integer.

Let a 1 ≥ a 2 and let

Where m 1 , a 3 are some integers, a 3 <a 2 (remainder from division a 1 on a 2 should be less a 2).

Let's pretend that λ divides a 1 and a 2 , then λ divides m 1 a 2 and λ divides a 1 −m 1 a 2 =a 3 (Assertion 2 of the article "Divisibility of numbers. Sign of divisibility"). It follows that every common divisor a 1 and a 2 is a common divisor a 2 and a 3 . The converse is also true if λ common divisor a 2 and a 3 , then m 1 a 2 and a 1 =m 1 a 2 +a 3 are also divided into λ . Hence the common divisor a 2 and a 3 is also a common divisor a 1 and a 2. Because a 3 <a 2 ≤a 1 , then we can say that the solution to the problem of finding a common divisor of numbers a 1 and a 2 reduced to a simpler problem of finding a common divisor of numbers a 2 and a 3 .

If a 3 ≠0, then we can divide a 2 on a 3 . Then

,

Where m 1 and a 4 are some integers, ( a 4 remainder of division a 2 on a 3 (a 4 <a 3)). By similar reasoning, we come to the conclusion that the common divisors of numbers a 3 and a 4 is the same as common divisors of numbers a 2 and a 3 , and also with common divisors a 1 and a 2. Because a 1 , a 2 , a 3 , a 4 , ... numbers that are constantly decreasing, and since there is a finite number of integers between a 2 and 0, then at some step n, remainder of the division a n on a n+1 will be equal to zero ( a n+2=0).

.

Every common divisor λ numbers a 1 and a 2 is also a divisor of numbers a 2 and a 3 , a 3 and a 4 , .... a n and a n+1 . The converse is also true, common divisors of numbers a n and a n+1 are also divisors of numbers a n−1 and a n , .... , a 2 and a 3 , a 1 and a 2. But the common divisor a n and a n+1 is a number a n+1 , because a n and a n+1 are divisible by a n+1 (recall that a n+2=0). Hence a n+1 is also a divisor of numbers a 1 and a 2 .

Note that the number a n+1 is the greatest number divisor a n and a n+1 , since the greatest divisor a n+1 is itself a n+1 . If a n + 1 can be represented as a product of integers, then these numbers are also common divisors of numbers a 1 and a 2. Number a n+1 are called greatest common divisor numbers a 1 and a 2 .

Numbers a 1 and a 2 can be both positive and negative numbers. If one of the numbers is equal to zero, then the greatest common divisor of these numbers will be equal to the absolute value of the other number. The greatest common divisor of zero numbers is not defined.

The above algorithm is called Euclid's algorithm to find the greatest common divisor of two integers.

An example of finding the greatest common divisor of two numbers

Find the greatest common divisor of two numbers 630 and 434.

• Step 1. Divide the number 630 by 434. The remainder is 196.
• Step 2. Divide the number 434 by 196. The remainder is 42.
• Step 3. Divide the number 196 by 42. The remainder is 28.
• Step 4. Divide the number 42 by 28. The remainder is 14.
• Step 5. Divide the number 28 by 14. The remainder is 0.

At step 5, the remainder of the division is 0. Therefore, the greatest common divisor of the numbers 630 and 434 is 14. Note that the numbers 2 and 7 are also divisors of the numbers 630 and 434.

Coprime numbers

Definition 1. Let the greatest common divisor of numbers a 1 and a 2 is equal to one. Then these numbers are called coprime numbers that do not have a common divisor.

Theorem 1. If a 1 and a 2 relatively prime numbers, and λ some number, then any common divisor of numbers λa 1 and a 2 is also a common divisor of numbers λ And a 2 .

Proof. Consider Euclid's algorithm for finding the greatest common divisor of numbers a 1 and a 2 (see above).

.

It follows from the conditions of the theorem that the greatest common divisor of numbers a 1 and a 2 , and therefore a n and a n+1 is 1. I.e. a n+1=1.

Let's multiply all these equalities by λ , Then

.

Let the common divisor a 1 λ And a 2 is δ . Then δ enters as a factor in a 1 λ , m 1 a 2 λ and in a 1 λ -m 1 a 2 λ =a 3 λ (See "Divisibility of numbers", Statement 2). Further δ enters as a factor in a 2 λ And m 2 a 3 λ , and hence enters as a factor in a 2 λ -m 2 a 3 λ =a 4 λ .

By reasoning in this way, we are convinced that δ enters as a factor in a n−1 λ And m n−1 a n λ , and therefore in a n−1 λ −m n−1 a n λ =a n+1 λ . Because a n+1 =1, then δ enters as a factor in λ . Hence the number δ is a common divisor of numbers λ And a 2 .

Consider special cases of Theorem 1.

Consequence 1. Let a And c prime numbers are relatively b. Then their product ac is a prime number with respect to b.

Really. From Theorem 1 ac And b have the same common divisors as c And b. But the numbers c And b coprime, i.e. have a single common divisor 1. Then ac And b also have a single common divisor 1. Hence ac And b mutually simple.

Consequence 2. Let a And b coprime numbers and let b divides ak. Then b divides and k.

Really. From the assertion condition ak And b have a common divisor b. By virtue of Theorem 1, b must be a common divisor b And k. Hence b divides k.

Corollary 1 can be generalized.

Consequence 3. 1. Let the numbers a 1 , a 2 , a 3 , ..., a m are prime relative to the number b. Then a 1 a 2 , a 1 a 2 · a 3 , ..., a 1 a 2 a 3 ··· a m , the product of these numbers is prime with respect to the number b.

2. Let we have two rows of numbers

such that every number in the first row is prime with respect to every number in the second row. Then the product

It is required to find such numbers that are divisible by each of these numbers.

If the number is divisible by a 1 , then it looks like sa 1 , where s some number. If q is the greatest common divisor of numbers a 1 and a 2 , then

Where s 1 is some integer. Then

is least common multiple of numbers a 1 and a 2 .

a 1 and a 2 coprime, then the least common multiple of the numbers a 1 and a 2:

Find the least common multiple of these numbers.

It follows from the above that any multiple of the numbers a 1 , a 2 , a 3 must be a multiple of numbers ε And a 3 and vice versa. Let the least common multiple of the numbers ε And a 3 is ε 1 . Further, a multiple of numbers a 1 , a 2 , a 3 , a 4 must be a multiple of numbers ε 1 and a 4 . Let the least common multiple of the numbers ε 1 and a 4 is ε 2. Thus, we found out that all multiples of numbers a 1 , a 2 , a 3 ,...,a m coincide with multiples of some specific number ε n , which is called the least common multiple of the given numbers.

In the particular case when the numbers a 1 , a 2 , a 3 ,...,a m coprime, then the least common multiple of the numbers a 1 , a 2 as shown above has the form (3). Further, since a 3 prime with respect to numbers a 1 , a 2 , then a 3 is a prime relative number a 1 · a 2 (Corollary 1). So the least common multiple of the numbers a 1 ,a 2 ,a 3 is a number a 1 · a 2 · a 3 . Arguing in a similar way, we arrive at the following assertions.

Statement 1. Least common multiple of coprime numbers a 1 , a 2 , a 3 ,...,a m is equal to their product a 1 · a 2 · a 3 ··· a m .

Statement 2. Any number that is divisible by each of the coprime numbers a 1 , a 2 , a 3 ,...,a m is also divisible by their product a 1 · a 2 · a 3 ··· a m .

Consider the solution of 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 both of them will take an integer number of steps.

Solution. The entire path that the guys will go through must be divisible by 60 and 70 without a remainder, 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 out all multiples, for the number 75. We get:

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

Now let's write out the numbers that will be a multiple 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 will be numbers, 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 smallest distance at which the guys take an integer number of steps will be 300 cm. The boy will go this way in 4 steps, and the girl will need to take 5 steps.

Finding the 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 for these numbers in a row.

You can use the following method.

How to find the least common multiple

First, you need to decompose 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).

We end up with 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. Decompose 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 decomposition of the rest, but not in the selected one.
• 4. Find the product of all the factors written out.

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

How to find LCM (least common multiple)

The common multiple of two integers is the integer that is evenly divisible by both given numbers without remainder.

The least common multiple of two integers is the smallest of all integers that is divisible evenly and without remainder 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 the numbers 6 and 9 will be 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 decomposing the original numbers into prime factors.
After decomposition, 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 the factor for the second, and the remaining numbers of the second number will be the 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 multiples of these numbers in a row. To do this, we decompose 75 and 60 into prime factors:
75 = 3 * 5 * 5, and
60 = 2 * 2 * 3 * 5 .
As you can see, the factors 3 and 5 occur in both rows. Mentally we "cross out" them.
Let's write down the remaining factors included in the expansion of each of these numbers. When decomposing the number 75, we left the number 5, and when decomposing the number 60, we left 2 * 2
So, 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 the numbers remaining from the expansion of the number 60 (this is 2 * 2) multiply by 75. That is, for ease of understanding , we say that we multiply "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 LCM for numbers 12, 16, 24
In this case, our actions will be somewhat more complicated. But, first, as always, we decompose all numbers into prime factors
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 successively go through its factors, crossing them out if at least one of the other rows of numbers has the same factor that has not yet been crossed out.

Step 1 . We see that 2 * 2 occurs in all series of numbers. We 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 action is 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. So the finding of the NOC is completed. It remains only to calculate its value.
For the number 12, we take the remaining factors from 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 ways of finding the LCM are correct.