What is a nok of numbers. Least common multiple (LCM)

Let's start studying the least common multiple of two or more numbers. In this section we will give a definition of the term, consider the theorem that establishes the connection between the least common multiple and the greatest common divisor, and give examples of solving problems.

Common multiples – definition, examples

In this topic we will be interested only in common multiples of integers other than zero.

Definition 1

Common multiple of integers is an integer that is a multiple of all given numbers. In fact, it is any integer that can be divided by any of the given numbers.

The definition of common multiples refers to two, three, or more integers.

Example 1

According to the definition given above, the common multiples of the number 12 are 3 and 2. Also, the number 12 will be a common multiple of the numbers 2, 3 and 4. The numbers 12 and -12 are common multiples of the numbers ±1, ±2, ±3, ±4, ±6, ±12.

At the same time, the common multiple of numbers 2 and 3 will be the numbers 12, 6, − 24, 72, 468, − 100,010,004 and a whole series of others.

If we take numbers that are divisible by the first number of a pair and not divisible by the second, then such numbers will not be common multiples. So, for numbers 2 and 3, the numbers 16, − 27, 5009, 27001 will not be common multiples.

0 is a common multiple of any set of integers other than zero.

If we recall the property of divisibility with respect to opposite numbers, it turns out that some integer k will be a common multiple of these numbers, just like the number - k. This means that common divisors can be either positive or negative.

Is it possible to find the LCM for all numbers?

The common multiple can be found for any integer.

Example 2

Suppose we are given k integers a 1 , a 2 , … , a k. The number we get when multiplying numbers a 1 · a 2 · … · a k according to the property of divisibility, it will be divided into each of the factors that were included in the original product. This means that the product of numbers a 1 , a 2 , … , a k is the least common multiple of these numbers.

How many common multiples can these integers have?

A group of integers can have a large number of common multiples. In fact, their number is infinite.

Example 3

Suppose we have some number k. Then the product of the numbers k · z, where z is an integer, will be a common multiple of the numbers k and z. Given that the number of numbers is infinite, the number of common multiples is infinite.

Least Common Multiple (LCM) – Definition, Notation and Examples

Let's remember the concept smallest number from the given set of numbers that we looked at in the “Comparing Integers” section. Taking this concept into account, we formulate the definition of the least common multiple, which has the greatest practical significance among all common multiples.

Definition 2

Least common multiple of given integers is the smallest positive common multiple of these numbers.

A least common multiple exists for any number of given numbers. The most commonly used abbreviation for the concept in reference literature is NOC. Short notation for least common multiple of numbers a 1 , a 2 , … , a k will have the form LOC (a 1 , a 2 , … , a k).

Example 4

The least common multiple of 6 and 7 is 42. Those. LCM(6, 7) = 42. The least common multiple of the four numbers 2, 12, 15 and 3 is 60. A short notation will look like LCM (- 2, 12, 15, 3) = 60.

The least common multiple is not obvious for all groups of given numbers. Often it has to be calculated.

Relationship between NOC and GCD

Least common multiple and greatest common divisor connected to each other. The relationship between concepts is established by the theorem.

Theorem 1

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

Evidence 1

Suppose we have some number M, which is a multiple of the numbers a and b. If the number M is divisible by a, there also exists some integer z , under which the equality is true M = a k. According to the definition of divisibility, if M is divisible by b, so then a · k divided by b.

If we introduce a new notation for gcd (a, b) as d, then we can use the equalities a = a 1 d and b = b 1 · d. In this case, both equalities will be mutual prime numbers.

We have already established above that a · k divided by b. Now this condition can be written as follows:
a 1 d k divided by b 1 d, which is equivalent to the condition a 1 k divided by b 1 according to the properties of divisibility.

According to the property of coprime numbers, if a 1 And b 1– coprime numbers, a 1 not divisible by b 1 despite the fact that a 1 k divided by b 1, That b 1 must be shared k.

In this case, it would be appropriate to assume that there is a number t, for which k = b 1 t, and since b 1 = b: d, That k = b: d t.

Now instead k let's substitute into equality M = a k expression of the form b: d t. This allows us to achieve equality M = a b: d t. At t = 1 we can get the least positive common multiple of a and b , equal a b: d, provided that numbers a and b positive.

So we proved that LCM (a, b) = a · b: GCD (a, b).

Establishing a connection between LCM and GCD allows you to find the least common multiple through the greatest common divisor of two or more given numbers.

Definition 3

The theorem has two important consequences:

multiples of the least common multiple of two numbers are the same as the common multiples of those two numbers;
least common multiple of coprime positive numbers a and b are equal to their product.

It is not difficult to substantiate these two facts. Any common multiple of M of numbers a and b is defined by the equality M = LCM (a, b) · t for some integer value t. 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

In order to find the least common multiple of several numbers, it is necessary to sequentially find the LCM of two numbers.

Theorem 2

Let's pretend that a 1 , a 2 , … , a k are some positive integers. In order to calculate the LCM m k these numbers, we need to sequentially calculate m 2 = LCM(a 1 , a 2) , m 3 = NOC(m 2 , a 3) , … , m k = NOC(m k - 1 , a k) .

Evidence 2

The first corollary from the first theorem discussed in this topic will help us prove the validity of the second theorem. The reasoning is based on the following algorithm:

common multiples of numbers a 1 And a 2 coincide with multiples of their LCM, in fact, they coincide with multiples of the number m 2;
common multiples of numbers a 1, a 2 And a 3 m 2 And a 3 m 3;
common multiples of numbers a 1 , a 2 , … , a k coincide with common multiples of numbers m k - 1 And a k, therefore, coincide with multiples of the number m k;
due to the fact that the smallest positive multiple of the number m k is the number itself m k, then the least common multiple of the numbers a 1 , a 2 , … , a k is m k.

This is how we proved the theorem.

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

Mathematical expressions and problems require a lot of additional knowledge. NOC is one of the main ones, especially often used in The topic is studied in high school, and it is not particularly difficult to understand material; a person familiar with powers and the multiplication table will not have difficulty identifying the necessary numbers and discovering the result.

Definition

A common multiple is a number that can be completely divided into two numbers at the same time (a and b). Most often, this number is obtained by multiplying the original numbers a and b. The number must be divisible by both numbers at once, without deviations.

NOC is the accepted designation short name, collected from the first letters.

Ways to get a number

The method of multiplying numbers is not always suitable for finding the LCM; it is much better suited for simple single-digit or two-digit numbers. It is customary to divide into factors than larger number, the more multipliers there will be.

Example #1

For the simplest example, schools usually use prime, single- or double-digit numbers. For example, you need to solve the following task, find the least common multiple of the numbers 7 and 3, the solution is quite simple, just multiply them. As a result, there is a number 21, there is simply no smaller number.

Example No. 2

The second version of the task is much more difficult. The numbers 300 and 1260 are given, finding the LOC is mandatory. To solve the problem, the following actions are assumed:

Decomposition of the first and second numbers into simple factors. 300 = 2 2 * 3 * 5 2 ; 1260 = 2 2 * 3 2 *5 *7. The first stage is completed.

The second stage involves working with already obtained data. Each of the received numbers must participate in the calculation of the final result. For each factor, the largest number of occurrences is taken from the original numbers. NOC is total number, therefore, the factors from the numbers must be repeated in it, every single one, even those that are present in one copy. Both initial numbers contain the numbers 2, 3 and 5, in different degrees, 7 is present in only one case.

To calculate the final result, you need to take each number in the largest of the powers represented into the equation. All that remains is to multiply and get the answer; if filled out correctly, the task fits into two steps without explanation:

1) 300 = 2 2 * 3 * 5 2 ; 1260 = 2 2 * 3 2 *5 *7.

2) NOC = 6300.

That’s the whole problem, if you try to calculate the required number by multiplication, then the answer will definitely not be correct, since 300 * 1260 = 378,000.

Examination:

6300 / 300 = 21 - correct;

6300 / 1260 = 5 - correct.

The correctness of the result obtained is determined by checking - dividing the LCM by both original numbers; if the number is an integer in both cases, then the answer is correct.

What does NOC mean in mathematics?

As you know, there is not a single useless function in mathematics, this one is no exception. The most common purpose of this number is to reduce fractions to a common denominator. What is usually studied in grades 5-6 high school. It is also additionally a common divisor for all multiples, if such conditions are present in the problem. Such an expression can find a multiple not only of two numbers, but also of a much larger number - three, five, and so on. The more numbers, the more actions in the task, but the complexity does not increase.

For example, given the numbers 250, 600 and 1500, you need to find their common LCM:

1) 250 = 25 * 10 = 5 2 *5 * 2 = 5 3 * 2 - this example describes factorization in detail, without reduction.

2) 600 = 60 * 10 = 3 * 2 3 *5 2 ;

3) 1500 = 15 * 100 = 33 * 5 3 *2 2 ;

In order to compose an expression, it is necessary to mention all the factors, in this case 2, 5, 3 are given - for all these numbers it is necessary to determine the maximum degree.

Attention: all factors must be brought to the point of complete simplification, if possible, decomposed to the level of single digits.

Examination:

1) 3000 / 250 = 12 - correct;

2) 3000 / 600 = 5 - true;

3) 3000 / 1500 = 2 - correct.

This method does not require any tricks or genius level abilities, everything is simple and clear.

Another way

In mathematics, many things are connected, many things can be solved in two or more ways, the same goes for finding the least common multiple, LCM. The following method can be used in the case of simple two-digit and single-digit numbers. A table is compiled into which the multiplicand is entered vertically, the multiplier horizontally, and the product is indicated in the intersecting cells of the column. You can reflect the table using a line, take a number and write down the results of multiplying this number by integers, from 1 to infinity, sometimes 3-5 points are enough, the second and subsequent numbers undergo the same computational process. Everything happens until a common multiple is found.

Given the numbers 30, 35, 42, you need to find the LCM connecting all the numbers:

1) Multiples of 30: 60, 90, 120, 150, 180, 210, 250, etc.

2) Multiples of 35: 70, 105, 140, 175, 210, 245, etc.

3) Multiples of 42: 84, 126, 168, 210, 252, etc.

It is noticeable that all the numbers are quite different, the only common number among them is 210, so it will be the NOC. Among the processes involved in this calculation there is also a greatest common divisor, which is calculated according to similar principles and is often encountered in neighboring problems. The difference is small, but quite significant, LCM involves calculating a number that is divided by all given initial values, and GCD involves calculating highest value by which the original numbers are divided.

To understand how to calculate the LCM, you must first determine the meaning of the term “multiple”.

A multiple of A is called natural number, which is divisible by A without a remainder. Thus, numbers that are multiples of 5 can be considered 15, 20, 25, and so on.

There can be divisors of a specific number limited quantity, but there are an infinite number of multiples.

A common multiple of natural numbers is a number that is divisible by them without leaving a remainder.

How to find the least common multiple of numbers

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

To find the LOC, you can use several methods.

For small numbers, it is convenient to write down all the multiples of these numbers on a line until you find something common among them. Multiples are denoted by the capital letter K.

For example, multiples of 4 can be written like this:

K (4) = (8,12, 16, 20, 24, ...)

K (6) = (12, 18, 24, ...)

Thus, you can see that the least common multiple of the numbers 4 and 6 is the number 24. This notation is done as follows:

LCM(4, 6) = 24

If the numbers are large, find the common multiple of three or more numbers, then it is better to use another method of calculating the LCM.

To complete the task, you need to factor the given numbers into prime factors.

First you need to write down the decomposition of the largest number on a line, and below it - the rest.

In the expansion of each number there may be different quantity multipliers.

For example, let's factor the numbers 50 and 20 into prime factors.

In the expansion of the smaller number, it is necessary to emphasize the factors that are absent in the expansion of the first one. large number, and then add them to it. In the example presented, a two is missing.

Now you can calculate the least common multiple of 20 and 50.

LCM(20, 50) = 2 * 5 * 5 * 2 = 100

Thus, the product of the prime factors of the larger number and the factors of the second number that were not included in the expansion of the larger number will be the least common multiple.

To find the LCM of three or more numbers, you should factor them all into prime factors, as in the previous case.

As an example, you can find the least common multiple of the numbers 16, 24, 36.

36 = 2 * 2 * 3 * 3

24 = 2 * 2 * 2 * 3

16 = 2 * 2 * 2 * 2

Thus, only two twos from the expansion of sixteen were not included in the factorization of a larger number (one is in the expansion of twenty-four).

Thus, they need to be added to the expansion of a larger number.

LCM(12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9

There are special cases of determining the least common multiple. So, if one of the numbers can be divided without a remainder by another, then the larger of these numbers will be the least common multiple.

For example, the LCM of twelve and twenty-four is twenty-four.

If it is necessary to find the least common multiple of coprime numbers that do not have identical divisors, then their LCM will be equal to their product.

For example, LCM (10, 11) = 110.

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: Tutorial for students of physics and mathematics. specialties of pedagogical institutes.

How to find the least common multiple?

We need to find each factor of each of the two numbers for which we find the least common multiple, and then multiply by each other the factors that coincide in the first and second numbers. The result of the product will be the required multiple.

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

Multiply three and get: 3, 6, 9, 12, 15

Multiply by five and get: 5, 10, 15

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

Add, multiply, divide, reduce to a common denominator and others arithmetic operations It’s a very exciting activity; I’m especially fascinated by the examples that take up an entire sheet of paper.

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

To begin with, let's learn that you can multiply two numbers by each other, and then reduce this figure and divide 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 divisible by 3 and 6 is divisible by 3, which means we also divide 90 by 3. We get 30. We try 30 divide 15 equals 2. And 30 divide 6 equals 5. Since 2 is the limit, it turns out that the least multiple for numbers is 15 and 6 will be 30.

With larger numbers it 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 great difficulties.

How to find NOC

Here is a video that will give you two ways to find the least common multiple (LCM). After practicing using the first of the suggested methods, you can better understand what the least common multiple is.

I present another way to find the least common multiple. Let's look at it with a clear example.

You need to find the LCM of three numbers at once: 16, 20 and 28.

We represent each number as a 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 (multipliers) with the greatest powers, multiply them and find the LCM:

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

LCM(16, 20, 28) = 560.

Thus, the result of the calculation was the number 560. It is the least common multiple, that is, it is divisible by each of the three numbers without a remainder.

The least common multiple is a number that can be divided into several given numbers without leaving a remainder. In order to calculate such a figure, you need to take each number and decompose it into simple factors. Those numbers that match are removed. 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 that is divisible by each of the given numbers without a remainder.

Here is 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 it is 2 x 3 x 5.

For 42, this is 2 x 3 x 7. Since 2 and 3 are in the expansion of the number 30, we cross them out.

We write down the factors that are included in the expansion of the number 30. This is 2 x 3 x 5.
Now we need to multiply them by the missing factor, which we have when expanding 42, which is 7. We get 2 x 3 x 5 x 7.
We find what 2 x 3 x 5 x 7 is equal to and get 210.

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

To find the least common multiple, you need to perform several simple steps in sequence. Let's look at this using two numbers as an example: 8 and 12

We factor both numbers into prime factors: 8=2*2*2 and 12=3*2*2
We reduce the same factors of one of the numbers. In our case, 2 * 2 coincide, let’s reduce them for the number 12, then 12 will have one factor left: 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’ll try to explain using the numbers 6 and 8 as an example. The least 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 first start multiplying 6 by 1, 2, 3, etc. and 8 by 1, 2, 3, etc.