• Repair
• Repair 
• Interior Design
• About everything
• About plumbing

How to find a common multiple. Nod and nok of numbers - greatest common divisor and least common multiple of several numbers

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:

Adding, multiplying, dividing, reducing to a common denominator and other arithmetic operations are a very exciting activity; the examples that take up an entire sheet of paper are especially fascinating.

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 obvious 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

1. We factor both numbers into prime factors: 8=2*2*2 and 12=3*2*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.
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.

Let's start studying the least common multiple of two or more numbers. In this section we will define 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 whole line any 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, 5 009, 27 001 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 us recall the concept of the smallest number of given set numbers, which 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

The least common multiple and the greatest common divisor are related. 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 relatively 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– mutually prime 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 the 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;
• the least common multiple of mutually prime positive numbers a and b is 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

The topic “Multiples” is studied in grade 5 secondary school. Its goal is to improve written and oral mathematical calculation skills. In this lesson, new concepts are introduced - “multiple numbers” and “divisors”, the technique of finding divisors and multiples of a natural number, and the ability to find LCM in various ways are practiced.

This topic is very important. Knowledge of it can be applied when solving examples with fractions. To do this you need to find common denominator by calculating the least common multiple (LCM).

A multiple of A is an integer that is divisible by A without a remainder.

Every natural number has an infinite number of multiples of it. It is itself considered the smallest. The multiple cannot be less than the number itself.

You need to prove that the number 125 is a multiple of 5. To do this, you need to divide the first number by the second. If 125 is divisible by 5 without a remainder, then the answer is yes.

This method is applicable for small numbers.

There are special cases when calculating LOC.

1. If you need to find a common multiple of 2 numbers (for example, 80 and 20), where one of them (80) is divisible by the other (20), then this number (80) is the least multiple of these two numbers.

LCM(80, 20) = 80.

2. If two do not have a common divisor, then we can say that their LCM is the product of these two numbers.

LCM(6, 7) = 42.

Let's look at the last example. 6 and 7 in relation to 42 are divisors. They divide a multiple of a number without a remainder.

In this example, 6 and 7 are paired factors. Their product is equal to the most multiple number (42).

A number is called prime if it is divisible only by itself or by 1 (3:1=3; 3:3=1). The rest are called composite.

Another example involves determining whether 9 is a divisor of 42.

42:9=4 (remainder 6)

Answer: 9 is not a divisor of 42 because the answer has a remainder.

A divisor differs from a multiple in that the divisor is the number by which natural numbers are divided, and the multiple itself is divisible by this number.

Greatest common divisor of numbers a And b, multiplied by their least multiple, will give the product of the numbers themselves a And b.

Namely: gcd (a, b) x gcd (a, b) = a x b.

Common multiples for more complex numbers found in the following way.

For example, find the LCM for 168, 180, 3024.

We factor these numbers into prime factors and write them as a product of powers:

168=2³x3¹x7¹

2⁴х3³х5¹х7¹=15120

LCM(168, 180, 3024) = 15120.

Signs of divisibility natural numbers.

Numbers divisible by 2 without a remainder are calledeven .

Numbers that are not evenly divisible by 2 are calledodd .

Test for divisibility by 2

If a natural number ends with an even digit, then this number is divisible by 2 without a remainder, and if a number ends with an odd digit, then this number is not evenly divisible by 2.

For example, the numbers 60 , 30 8 , 8 4 are divisible by 2 without remainder, and the numbers are 51 , 8 5 , 16 7 are not divisible by 2 without a remainder.

Test for divisibility by 3

If the sum of the digits of a number is divisible by 3, then the number is divisible by 3; If the sum of the digits of a number is not divisible by 3, then the number is not divisible by 3.

For example, let’s find out whether the number 2772825 is divisible by 3. To do this, let’s calculate the sum of the digits of this number: 2+7+7+2+8+2+5 = 33 - divisible by 3. This means the number 2772825 is divisible by 3.

Divisibility test by 5

If the record of a natural number ends with the digit 0 or 5, then this number is divisible by 5 without a remainder. If the record of a number ends with another digit, then the number is not divisible by 5 without a remainder.

For example, the numbers 15 , 3 0 , 176 5 , 47530 0 are divisible by 5 without remainder, and the numbers are 17 , 37 8 , 9 1 don't share.

Divisibility test by 9

If the sum of the digits of a number is divisible by 9, then the number is divisible by 9; If the sum of the digits of a number is not divisible by 9, then the number is not divisible by 9.

For example, let’s find out whether the number 5402070 is divisible by 9. To do this, let’s calculate the sum of the digits of this number: 5+4+0+2+0+7+0 = 16 - not divisible by 9. This means the number 5402070 is not divisible by 9.

Divisibility test by 10

If a natural number ends with the digit 0, then this number is divisible by 10 without a remainder. If a natural number ends with another digit, then it is not evenly divisible by 10.

For example, the numbers 40 , 17 0 , 1409 0 are divisible by 10 without remainder, and the numbers 17 , 9 3 , 1430 7 - do not share.

The rule for finding the greatest common divisor (GCD).

To find the greatest common divisor of several natural numbers, you need to:

2) from the factors included in the expansion of one of these numbers, cross out those that are not included in the expansion of other numbers;

3) find the product of the remaining factors.

Example. Let's find GCD (48;36). Let's use the rule.

1. Let's factor the numbers 48 and 36 into prime factors.

48 = 2 · 2 · 2 · 2 · 3

36 = 2 · 2 · 3 · 3

2. From the factors included in the expansion of the number 48, we delete those that are not included in the expansion of the number 36.

48 = 2 · 2 · 2 · 2 · 3

The remaining factors are 2, 2 and 3.

3. Multiply the remaining factors and get 12. This number is the greatest common divisor of the numbers 48 and 36.

GCD (48;36) = 2· 2 · 3 = 12.

The rule for finding the least common multiple (LCM).

To find the least common multiple of several natural numbers, you need to:

1) factor them into prime factors;

2) write down the factors included in the expansion of one of the numbers;

3) add to them the missing factors from the expansions of the remaining numbers;

4) find the product of the resulting factors.

Example. Let's find the LOC (75;60). Let's use the rule.

1. Let's factor the numbers 75 and 60 into prime factors.

75 = 3 · 5 · 5

60 = 2 · 2 · 3 · 3

2. Let’s write down the factors included in the expansion of the number 75: 3, 5, 5.

LCM(75;60) = 3 · 5 · 5 · …

3. Add to them the missing factors from the expansion of the number 60, i.e. 2, 2.

LCM(75;60) = 3 · 5 · 5 · 2 · 2

4. Find the product of the resulting factors

LCM(75;60) = 3 · 5 · 5 · 2 · 2 = 300.

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

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

Most in a simple way Calculating the greatest common divisor of two numbers is to find all possible divisors of these numbers and select the largest of them.

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.