Least common short of numbers 15 and 12. Nod and nok of numbers - the greatest common divisor and least common multiple of several numbers

But many natural numbers are evenly divisible by other natural numbers.

for instance:

The number 12 is divisible by 1, by 2, by 3, by 4, by 6, by 12;

The number 36 is divisible by 1, by 2, by 3, by 4, by 6, by 12, by 18, by 36.

The numbers by which the number is divisible (for 12 it is 1, 2, 3, 4, 6 and 12) are called number divisors. Divisor of a natural number a is the natural number that divides the given number a without a trace. A natural number that has more than two factors is called composite .

Note that the numbers 12 and 36 have common divisors. These are the numbers: 1, 2, 3, 4, 6, 12. The largest divisor of these numbers is 12. The common divisor of these two numbers a and b is the number by which both given numbers are divisible without a remainder a and b.

common multiple several numbers is called the number that is divisible by each of these numbers. for instance, the numbers 9, 18 and 45 have a common multiple of 180. But 90 and 360 are also their common multiples. Among all jcommon multiples, there is always the smallest, in this case it's 90. This number is called leastcommon multiple (LCM).

LCM is always a natural number, which must be greater than the largest of the numbers for which it is defined.

Least common multiple (LCM). Properties.

Commutativity:

Associativity:

In particular, if and are coprime numbers , then:

Least common multiple of two integers m and n is a divisor of all other common multiples m and n. Moreover, the set of common multiples m,n coincides with the set of multiples for LCM( m,n).

The asymptotics for can be expressed in terms of some number-theoretic functions.

So, Chebyshev function. As well as:

This follows from the definition and properties of the Landau function g(n).

What follows from the law of distribution prime numbers.

Finding the least common multiple (LCM).

NOC( a, b) can be calculated in several ways:

1. If the greatest common divisor is known, you can use its relationship with the LCM:

2. Let the canonical decomposition of both numbers into prime factors be known:

where p 1 ,...,p k are various prime numbers, and d 1 ,...,d k and e 1 ,...,ek are non-negative integers (they can be zero if the corresponding prime is not in the decomposition).

Then LCM ( a,b) is calculated by the formula:

In other words, the LCM expansion contains all prime factors that are included in at least one of the number expansions a, b, and the largest of the two exponents of this factor is taken.

Example:

The calculation of the least common multiple of several numbers can be reduced to several successive calculations of the LCM of two numbers:

Rule. To find the LCM of a series of numbers, you need:

- decompose numbers into prime factors;

- transfer the largest expansion into the factors of the desired product (the product of the factors of the a large number from the given ones), and then add factors from the decomposition of other numbers that do not occur in the first number or are in it a smaller number of times;

- the resulting product of prime factors will be LCM given numbers.

Any two or more natural numbers have their own NOC. If the numbers are not multiples of each other or do not have the same factors in the expansion, then their LCM is equal to the product of these numbers.

The prime factors of the number 28 (2, 2, 7) were supplemented with a factor of 3 (the number 21), the resulting product (84) will be the smallest number that is divisible by 21 and 28.

Prime factors nai more 30 was supplemented with a factor of 5 of the number 25, the resulting product 150 is greater than the largest number 30 and is divisible by all given numbers without a remainder. This is the smallest possible product (150, 250, 300...) that all given numbers are multiples of.

The numbers 2,3,11,37 are prime, so their LCM is equal to the product of the given numbers.

rule. To calculate the LCM of prime numbers, you need to multiply all these numbers together.

Another option:

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

1) represent each number as a product of its prime factors, for example:

504 \u003d 2 2 2 3 3 7,

2) write down the powers of all prime factors:

504 \u003d 2 2 2 3 3 7 \u003d 2 3 3 2 7 1,

3) write down all prime divisors (multipliers) of each of these numbers;

4) choose the largest degree of each of them, found in all expansions of these numbers;

5) multiply these powers.

Example. Find the LCM of numbers: 168, 180 and 3024.

Solution. 168 \u003d 2 2 2 3 7 \u003d 2 3 3 1 7 1,

180 \u003d 2 2 3 3 5 \u003d 2 2 3 2 5 1,

3024 = 2 2 2 2 3 3 3 7 = 2 4 3 3 7 1 .

We write out the largest powers of all prime divisors and multiply them:

LCM = 2 4 3 3 5 1 7 1 = 15120.

Consider three ways to find the least common multiple.

Finding by Factoring

The first way is to find the least common multiple by factoring the given numbers into prime factors.

Suppose we need to find the LCM of numbers: 99, 30 and 28. To do this, we decompose 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 highest occurring power and multiply them together:

2 2 3 2 5 7 11 = 13 860

So LCM (99, 30, 28) = 13,860. No other number less than 13,860 is evenly divisible by 99, 30, or 28.

To find the least common multiple of given numbers, you need to decompose them into prime factors, then take each prime factor with the largest exponent with which it occurs, and multiply these factors together.

Since coprime numbers have no common prime factors, their least common multiple is equal to the product of these numbers. For example, three numbers: 20, 49 and 33 are coprime. So

LCM (20, 49, 33) = 20 49 33 = 32,340.

The same should be done when looking for the least common multiple of various primes. For example, LCM (3, 7, 11) = 3 7 11 = 231.

Finding by selection

The second way is to find the least common multiple by fitting.

Example 1. When the largest of the given numbers is evenly divisible by other given numbers, then the LCM of these numbers is equal to the larger of them. For example, given four numbers: 60, 30, 10 and 6. Each of them is divisible by 60, therefore:

NOC(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 numbers that are multiples of the largest number, multiplying it by natural numbers in ascending order and checking whether the remaining given numbers are divisible by the resulting product.

Example 2. Given three numbers 24, 3 and 18. Determine the largest of them - this is the number 24. Next, find the numbers that are multiples of 24, checking whether each of them is divisible by 18 and by 3:

24 1 = 24 is divisible by 3 but not divisible by 18.

24 2 = 48 - divisible by 3 but not divisible by 18.

24 3 \u003d 72 - divisible by 3 and 18.

So LCM(24, 3, 18) = 72.

Finding by Sequential Finding LCM

The third way is to find the least common multiple by successively 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 into their GCD:

So LCM(12, 8) = 24.

To find the LCM of three or more numbers, the following procedure is used:

1. First, the LCM of any two of the given numbers is found.
2. Then, the 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, and so on.
4. Thus the LCM search continues as long as there are numbers.

Example 2. Let's find the LCM of three given numbers: 12, 8 and 9. We have 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 24 and the third given number - 9. Determine their greatest common divisor: gcd (24, 9) = 3. Multiply LCM with the number 9:

We divide the product into their GCD:

So LCM(12, 8, 9) = 72.

The online calculator allows you to quickly find the greatest common divisor and least common multiple of two or any other number of numbers.

Calculator for finding GCD and NOC

Find GCD and NOC

GCD and NOC found: 5806

How to use the calculator

• Enter numbers in the input field
• In case of entering incorrect characters, the input field will be highlighted in red
• press the button "Find GCD and NOC"

How to enter numbers

• Numbers are entered separated by spaces, dots or commas
• The length of the entered numbers is not limited, so finding the gcd and lcm of long numbers will not be difficult

What is NOD and NOK?

Greatest Common Divisor of several numbers is the largest natural integer by which all the original numbers are divisible without a remainder. The greatest common divisor is abbreviated as GCD.
Least common multiple multiple numbers is smallest number, which is divisible by each of the original numbers without a remainder. The least common multiple is abbreviated as NOC.

How to check if a number is divisible by another number without a remainder?

To find out if one number is divisible by another without a remainder, you can use some properties of divisibility of numbers. Then, by combining them, one can check the divisibility by some of them and their combinations.

Some signs of divisibility of numbers

1. Sign of divisibility of 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 if the number 34938 is divisible by 2.
Solution: look at the last digit: 8 means the number is divisible by two.

2. Sign of divisibility of a number by 3
A number is divisible by 3 when the sum of its digits is divisible by 3. Thus, to determine whether a number is divisible by 3, you need to calculate the sum of the digits and check if it is divisible by 3. Even if the sum of the digits turned out to be very large, you can repeat the same process again.
Example: determine if the number 34938 is divisible by 3.
Solution: we count the sum of the digits: 3+4+9+3+8 = 27. 27 is divisible by 3, which means that the number is divisible by three.

3. Sign of divisibility of a number by 5
A number is divisible by 5 when its last digit is zero or five.
Example: determine if the number 34938 is divisible by 5.
Solution: look at the last digit: 8 means the number is NOT divisible by five.

4. Sign of divisibility of 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 if the number 34938 is divisible by 9.
Solution: we calculate the sum of the digits: 3+4+9+3+8 = 27. 27 is divisible by 9, which means that the number is divisible by nine.

How to find GCD and LCM of two numbers

How to find the GCD of two numbers

Most in a simple way calculating the greatest common divisor of two numbers is to find all possible divisors of those numbers and choose the largest of them.

Consider this method using the example of finding GCD(28, 36) :

1. We factorize 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 \u003d 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 smallest multiple of two numbers. The first way is that you can write out the first multiples of two numbers, and then choose among them such 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 just consider 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 the numbers 28 and 36: 28 36 = 1008
2. gcd(28, 36) is already known to be 4
3. LCM(28, 36) = 1008 / 4 = 252 .

Finding GCD and LCM for Multiple Numbers

The greatest common divisor can be found for several numbers, and not just for two. For this, the numbers to be searched for the greatest common divisor are decomposed into prime factors, then the product of the common prime factors of these numbers is found. Also, to find the GCD of several numbers, you can use the following relationship: gcd(a, b, c) = gcd(gcd(a, b), c).

A similar relation also applies to the least common multiple of numbers: 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 common factors: 1, 2 and 2 .
3. Their product will give gcd: 1 2 2 = 4
4. Now let's find the LCM: for this we first find the LCM(12, 32): 12 32 / 4 = 96 .
5. To find the NOC 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 .

How to find LCM (least common multiple)

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 times 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 delete from the resulting series of prime factors same numbers. 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 sequentially 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.

To understand how to calculate the LCM, you should first determine the meaning of the term "multiple".

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

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

A common multiple of natural numbers is a number that is divisible by them without 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 evenly divisible by all these numbers.

To find the NOC, you can use several methods.

For small numbers, it is convenient to write out in a line all the multiples of these numbers until a common one is found among them. Multiples are denoted in the record with a 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, ...)

So, you can see that the least common multiple of the numbers 4 and 6 is the number 24. This entry is performed 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 way to calculate the LCM.

To complete the task, it is necessary to decompose the proposed numbers into prime factors.

First you need to write out the expansion of the largest of the numbers in 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 decomposition of the smaller number, one should underline the factors that are absent in the decomposition of the first largest number, and then add them to it. In the presented example, a deuce is missing.

Now we 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, which are not included in the decomposition of the larger number, will be the least common multiple.

To find the LCM of three or more numbers, all of them should be decomposed 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 deuces from the decomposition of sixteen were not included in the factorization of a larger number (one is in the decomposition of twenty-four).

Thus, they need to be added to the decomposition 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, NOCs of twelve and twenty-four would be twenty-four.

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

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