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

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 the first number into prime factors. 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.
  - For example, 2 × 10 = 20 (\displaystyle (\mathbf (2) )\times 10=20) And 2 × 5 = 10 (\displaystyle (\mathbf (2) )\times (\mathbf (5) )=10). Thus, the prime factors of the number 20 are the numbers 2, 2 and 5. Write them as an expression: .
3. 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.
  - For example, 2 × 42 = 84 (\displaystyle (\mathbf (2) )\times 42=84), 7 × 6 = 42 (\displaystyle (\mathbf (7) )\times 6=42) And 3 × 2 = 6 (\displaystyle (\mathbf (3) )\times (\mathbf (2) )=6). Thus, the prime factors of the number 84 are the numbers 2, 7, 3 and 2. Write them as an expression: .
4. 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).
  - For example, both numbers have a common factor of 2, so write 2 × (\displaystyle 2\times ) and cross out the 2 in both expressions.
  - What both numbers have in common is another factor of 2, so write 2 × 2 (\displaystyle 2\times 2) and cross out the second 2 in both expressions.
5. 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.
  - For example, in the expression 20 = 2 × 2 × 5 (\displaystyle 20=2\times 2\times 5) Both twos (2) are crossed out because they are common factors. The factor 5 is not crossed out, so write the multiplication operation like this: 2 × 2 × 5 (\displaystyle 2\times 2\times 5)
  - In expression 84 = 2 × 7 × 3 × 2 (\displaystyle 84=2\times 7\times 3\times 2) both twos (2) are also crossed out. The factors 7 and 3 are not crossed out, so write the multiplication operation like this: 2 × 2 × 5 × 7 × 3 (\displaystyle 2\times 2\times 5\times 7\times 3).
6. Calculate the least common multiple. To do this, multiply the numbers in the written multiplication operation.
  - For example, 2 × 2 × 5 × 7 × 3 = 420 (\displaystyle 2\times 2\times 5\times 7\times 3=420). So the least common multiple of 20 and 84 is 420.
Finding common factors
1. Draw a grid like for a game of tic-tac-toe. Such a grid consists of two parallel lines that intersect (at right angles) with another two parallel lines. This will give you three rows and three columns (the grid looks a lot like the # icon). Write the first number in the first line and second column. Write the second number in the first row and third column.
  - For example, find the least common multiple of the numbers 18 and 30. Write the number 18 in the first row and second column, and write the number 30 in the first row and third column.
2. 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.
3. Divide each number by the first divisor. Write each quotient under the appropriate number. A quotient is the result of dividing two numbers.
  - For example, 18 ÷ 2 = 9 (\displaystyle 18\div 2=9), so write 9 under 18.
  - 30 ÷ 2 = 15 (\displaystyle 30\div 2=15), so write down 15 under 30.
4. 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.
5. Divide each quotient by its second divisor. Write each division result under the corresponding quotient.
  - For example, 9 ÷ 3 = 3 (\displaystyle 9\div 3=3), so write 3 under 9.
  - 15 ÷ 3 = 5 (\displaystyle 15\div 3=5), so write 5 under 15.
6. If necessary, add additional cells to the grid. Repeat the described steps until the quotients have a common divisor.
7. Circle the numbers in the first column and last row of the grid. Then write the selected numbers as a multiplication operation.
  - For example, the numbers 2 and 3 are in the first column, and the numbers 3 and 5 are in the last row, so write the multiplication operation like this: 2 × 3 × 3 × 5 (\displaystyle 2\times 3\times 3\times 5).
8. Find the result of multiplying numbers. This will calculate the least common multiple of two given numbers.
  - For example, 2 × 3 × 3 × 5 = 90 (\displaystyle 2\times 3\times 3\times 5=90). So the least common multiple of 18 and 30 is 90.
Euclid's algorithm
1. Remember the terminology associated with the division operation. The dividend is the number that is being divided. The divisor is the number that is being divided by. A quotient is the result of dividing two numbers. A remainder is the number left when two numbers are divided.
  - For example, in the expression 15 ÷ 6 = 2 (\displaystyle 15\div 6=2) ost. 3:
    15 is the dividend
    6 is a divisor
    2 is quotient
    3 is the remainder.

Definition. The largest natural number that can be divided without a remainder by numbers a and b is called greatest common divisor (GCD) these numbers.

Let's find the greatest common divisor of the numbers 24 and 35.
The divisors of 24 are the numbers 1, 2, 3, 4, 6, 8, 12, 24, and the divisors of 35 are the numbers 1, 5, 7, 35.
We see that the numbers 24 and 35 have only one common divisor - the number 1. Such numbers are called mutually prime.

Definition. Natural numbers are called mutually prime, if their greatest common divisor (GCD) is 1.

Greatest Common Divisor (GCD) can be found without writing out all the divisors of the given numbers.

Let's factor the numbers 48 and 36 and get:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
From the factors included in the expansion of the first of these numbers, we cross out those that are not included in the expansion of the second number (i.e., two twos).
The factors remaining are 2 * 2 * 3. Their product is 12. This number is the greatest common divisor of the numbers 48 and 36. The greatest common divisor of three or more numbers is also found.

To find greatest common divisor

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.

If all given numbers are divisible by one of them, then this number is greatest common divisor given numbers.
For example, the greatest common divisor of the numbers 15, 45, 75 and 180 is the number 15, since all other numbers are divisible by it: 45, 75 and 180.

Least common multiple (LCM)

Definition. Least common multiple (LCM) natural numbers a and b is the smallest natural number that is a multiple of both a and b. The least common multiple (LCM) of the numbers 75 and 60 can be found without writing down the multiples of these numbers in a row. To do this, let's factor 75 and 60 into prime factors: 75 = 3 * 5 * 5, and 60 = 2 * 2 * 3 * 5.
Let's write down the factors included in the expansion of the first of these numbers, and add to them the missing factors 2 and 2 from the expansion of the second number (i.e., we combine the factors).
We get five factors 2 * 2 * 3 * 5 * 5, the product of which is 300. This number is the least common multiple of the numbers 75 and 60.

They also find the least common multiple of three or more numbers.

To find least common multiple several natural numbers, you need:
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.

Note that if one of these numbers is divisible by all other numbers, then this number is the least common multiple of these numbers.
For example, the least common multiple of the numbers 12, 15, 20, and 60 is 60 because it is divisible by all of those numbers.

Pythagoras (VI century BC) and his students studied the question of the divisibility of numbers. They called a number equal to the sum of all its divisors (without the number itself) a perfect number. For example, the numbers 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) are perfect. The next perfect numbers are 496, 8128, 33,550,336. The Pythagoreans only knew the first three perfect numbers. The fourth - 8128 - became known in the 1st century. n. e. The fifth - 33,550,336 - was found in the 15th century. By 1983, 27 perfect numbers were already known. But scientists still don’t know whether there are odd perfect numbers or whether there is a largest perfect number.
The interest of ancient mathematicians in prime numbers is due to the fact that any number is either prime or can be represented as a product of prime numbers, i.e. prime numbers are like bricks from which the rest of the natural numbers are built.
You probably noticed that prime numbers in the series of natural numbers occur unevenly - in some parts of the series there are more of them, in others - less. But the further we move along the number series, the less common prime numbers are. The question arises: is there a last (largest) prime number? The ancient Greek mathematician Euclid (3rd century BC), in his book “Elements”, which was the main textbook of mathematics for two thousand years, proved that there are infinitely many prime numbers, i.e. behind each prime number there is an even greater prime number.
To find prime numbers, another Greek mathematician of the same time, Eratosthenes, came up with this method. He wrote down all the numbers from 1 to some number, and then crossed out one, which is neither a prime nor a composite number, then crossed out through one all the numbers coming after 2 (numbers that are multiples of 2, i.e. 4, 6 , 8, etc.). The first remaining number after 2 was 3. Then, after two, all numbers coming after 3 (numbers that are multiples of 3, i.e. 6, 9, 12, etc.) were crossed out. in the end only the prime numbers remained uncrossed.

Finding the Least Common Multiple (LCD) and Greatest Common Divisor (GCD) of natural numbers.

	2						5
	2						5
	3						3
	5

60=2*2*3*5
75=3*5*5
2) Let's write out the factors included in the expansion of the first of these numbers and add to them the missing factor 5 from the expansion of the second number. We get: 2*2*3*5*5=300. We found the NOC, i.e. this amount = 300. Don’t forget the dimension and write the answer:
Answer: Mom gives 300 rubles.

GCD definition: Greatest Common Divisor (GCD) natural numbers A And V call the largest natural number c, to which a, And b divided without remainder. Those. c is the smallest natural number for which and A And b are multiples.

Memo: There are two approaches to defining natural numbers

numbers used in: listing (numbering) objects (first, second, third, ...); - in schools it's usually like this.
designation of the number of items (no Pokemon - zero, one Pokemon, two Pokemon, ...).

Negative and non-integer (rational, real, ...) numbers are not natural numbers. Some authors include zero in the set of natural numbers, others do not. The set of all natural numbers is usually denoted by the symbol N

Memo: Divisor of a natural number a name the number b, to which a divided without remainder. Multiples of a natural number b call a natural number a, which is divisible by b without a trace. If the number b- number divisor a, That a multiple of the number b. Example: 2 is a divisor of 4, and 4 is a multiple of two. 3 is a divisor of 12, and 12 is a multiple of 3.
Memo: Natural numbers are called prime if they are divisible without a remainder only by themselves and 1. Co-prime numbers are those that have only one common divisor equal to 1.

Determination of how to find a GCD in the general case: To find GCD (Greatest Common Divisor) several natural numbers are needed:
1) Divide them into prime factors. (The Table of Prime Numbers can be very useful for this.)
2) Write down the factors included in the expansion of one of them.
3) Cross out those that are not included in the expansion of the remaining numbers.
4) Multiply the factors obtained in step 3).

Problem 2 on (NOK): For the New Year, Kolya Puzatov bought 48 hamsters and 36 coffee pots in the city. Fekla Dormidontova, as the most honest girl in the class, was given the task of dividing this property into the largest possible number of gift sets for teachers. How many sets did you get? What is the content of the sets?

Example 2.1. solving the problem of finding GCD. Finding GCD by selection.
Solution: Each of the numbers 48 and 36 must be divisible by the number of gifts.
1) Write down the divisors 48: 48, 24, 16, 12 , 8, 6, 3, 2, 1
2) Write down the divisors of 36: 36, 18, 12 , 9, 6, 3, 2, 1 Choose the greatest common divisor. Whoa-la-la! We found that the number of sets is 12 pieces.
3) Divide 48 by 12 to get 4, divide 36 by 12 to get 3. Don’t forget the dimension and write the answer:
Answer: You will get 12 sets of 4 hamsters and 3 coffee pots in each set.

Greatest common divisor

Definition 2

If a natural number a is divisible by a natural number $b$, then $b$ is called a divisor of $a$, and $a$ is called a multiple of $b$.

Let $a$ and $b$ be natural numbers. The number $c$ is called the common divisor of both $a$ and $b$.

The set of common divisors of the numbers $a$ and $b$ is finite, since none of these divisors can be greater than $a$. This means that among these divisors there is a largest one, which is called the greatest common divisor of the numbers $a$ and $b$ and is denoted by the following notation:

$GCD\(a;b)\ or \D\(a;b)$

To find the greatest common divisor of two numbers you need:

Find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.

Example 1

Find the gcd of the numbers $121$ and $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Choose the numbers that are included in the expansion of these numbers

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.

$GCD=2\cdot 11=22$

Example 2

Find the gcd of the monomials $63$ and $81$.

We will find according to the presented algorithm. To do this:

Let's factor the numbers into prime factors

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

We select the numbers that are included in the expansion of these numbers

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Let's find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.

$GCD=3\cdot 3=9$

You can find the gcd of two numbers in another way, using a set of divisors of numbers.

Example 3

Find the gcd of the numbers $48$ and $60$.

Solution:

Let's find the set of divisors of the number $48$: $\left$(\rm 1,2,3.4.6,8,12,16,24,48)\right$$

Now let's find the set of divisors of the number $60$:$\ \left$(\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right$$

Let's find the intersection of these sets: $\left$(\rm 1,2,3,4,6,12)\right$$ - this set will determine the set of common divisors of the numbers $48$ and $60$. The largest element in this set will be the number $12$. This means that the greatest common divisor of the numbers $48$ and $60$ is $12$.

Definition of NPL

Definition 3

Common multiples of natural numbers$a$ and $b$ is a natural number that is a multiple of both $a$ and $b$.

Common multiples of numbers are numbers that are divisible by the original numbers without a remainder. For example, for the numbers $25$ and $50$, the common multiples will be the numbers $50,100,150,200$, etc.

The smallest common multiple will be called the least common multiple and will be denoted LCM$(a;b)$ or K$(a;b).$

To find the LCM of two numbers, you need to:

Factor numbers into prime factors
Write down the factors that are part of the first number and add to them the factors that are part of the second and are not part of the first

Example 4

Find the LCM of the numbers $99$ and $77$.

We will find according to the presented algorithm. For this

Factor numbers into prime factors

$99=3\cdot 3\cdot 11$

Write down the factors included in the first

add to them multipliers that are part of the second and not part of the first

Find the product of the numbers found in step 2. The resulting number will be the desired least common multiple

$NOK=3\cdot 3\cdot 11\cdot 7=693$

Compiling lists of divisors of numbers is often a very labor-intensive task. There is a way to find GCD called the Euclidean algorithm.

Statements on which the Euclidean algorithm is based:

If $a$ and $b$ are natural numbers, and $a\vdots b$, then $D(a;b)=b$

If $a$ and $b$ are natural numbers such that $b

Using $D(a;b)= D(a-b;b)$, we can successively reduce the numbers under consideration until we reach a pair of numbers such that one of them is divisible by the other. Then the smaller of these numbers will be the desired greatest common divisor for the numbers $a$ and $b$.

Properties of GCD and LCM

Any common multiple of $a$ and $b$ is divisible by K$(a;b)$
If $a\vdots b$ , then К$(a;b)=a$

If K$(a;b)=k$ and $m$ is a natural number, then K$(am;bm)=km$

If $d$ is a common divisor for $a$ and $b$, then K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d) $

If $a\vdots c$ and $b\vdots c$ , then $\frac(ab)(c)$ is the common multiple of $a$ and $b$

For any natural numbers $a$ and $b$ the equality holds

$D(a;b)\cdot К(a;b)=ab$

Any common divisor of the numbers $a$ and $b$ is a divisor of the number $D(a;b)$

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

For example:

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 by a whole (for 12 these are 1, 2, 3, 4, 6 and 12) are called divisors of numbers. Divisor of a natural number a- is a natural number that divides a given number a without a trace. A natural number that has more than two divisors is called composite .

Please note that the numbers 12 and 36 have common factors. These numbers are: 1, 2, 3, 4, 6, 12. The greatest divisor of these numbers is 12. The common divisor of these two numbers a And b- this is the number by which both given numbers are divided without remainder a And b.

Common multiples several numbers is a number that is divisible by each of these numbers. For example, the numbers 9, 18 and 45 have a common multiple of 180. But 90 and 360 are also their common multiples. Among all common multiples there is always a smallest one, in this case it is 90. This number is called the smallestcommon multiple (CMM).

The LCM is always a natural number that 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. And also:

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

What follows from the law of distribution of 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 connection with the LCM:

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

Where p 1 ,...,p k- various prime numbers, and d 1 ,...,d k And e 1 ,...,e k— non-negative integers (they can be zeros if the corresponding prime is not in the expansion).

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

In other words, the LCM decomposition contains all prime factors included in at least one of the decompositions of numbers a, b, and the largest of the two exponents of this multiplier is taken.

Example:

Calculating the least common multiple of several numbers can be reduced to several sequential 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 decomposition (the product of the factors of the largest number of the given ones) to the factors of the desired product, and then add factors from the decomposition of other numbers that do not appear in the first number or appear in it fewer times;

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

Any two or more natural numbers have their own LCM. 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) are 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.

The prime factors of the largest number 30 are supplemented by the factor 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 is a multiple of all given numbers.