How can you find the number of two natural numbers? Finding the least common multiple: methods, examples of finding LCM

The topic “Multiple Numbers” is studied in the 5th grade of 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 the 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 are found in the following way.

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

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

168=2³x3¹x7¹

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

LCM(168, 180, 3024) = 15120.

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

Second number: b=

Thousand separator Without space separator "´

Result:

Greatest common divisor gcd( a,b)=6

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

The largest natural number that can be divided without a remainder by numbers a and b is called greatest common divisor(GCD) of these numbers. Denoted by gcd(a,b), (a,b), gcd(a,b) or hcf(a,b).

Least common multiple The 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).

The integers a and b are called mutually prime, 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 the common divisor of these numbers, i.e. find such a number λ , which divides numbers a 1 and a 2 at the same time. Let's describe the algorithm.

1) In this article, the word number will be understood as an integer.

Let a 1 ≥ a 2 and let

Where m 1 , a 3 are some integers, a 3 <a 2 (remainder of division a 1 per 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 (Statement 2 of the article “Divisibility of numbers. Divisibility test”). It follows that every common divisor a 1 and a 2 is the common divisor a 2 and a 3. The reverse 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 is also divisible by λ . Therefore 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 the common divisor of numbers a 1 and a 2 reduced to the simpler problem of finding the common divisor of numbers a 2 and a 3 .

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

Where m 1 and a 4 are some integers, ( a 4 remainder from division a 2 per a 3 (a 4 <a 3)). By similar reasoning we come to the conclusion that common divisors of numbers a 3 and a 4 coincides with 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, ... are 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 of numbers 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 (remember 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 largest divisor of numbers 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 is called greatest common divisor numbers a 1 and a 2 .

Numbers a 1 and a 2 can be either positive or 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 undefined.

The above algorithm is called Euclidean 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.

In 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 the numbers a 1 and a 2 is equal to one. Then these numbers are called coprime numbers, having no common divisor.

Theorem 1. If a 1 and a 2 coprime 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 the Euclidean algorithm for finding the greatest common divisor of numbers a 1 and a 2 (see above).

From the conditions of the theorem it follows that the greatest common divisor of the numbers a 1 and a 2 and therefore a n and a n+1 is 1. That is a n+1 =1.

Let's multiply all these equalities by λ , Then

Let the common divisor a 1 λ And a 2 yes δ . Then δ is included as a multiplier in a 1 λ , m 1 a 2 λ and in a 1 λ -m 1 a 2 λ =a 3 λ (see "Divisibility of numbers", Statement 2). Further δ is included as a multiplier in a 2 λ And m 2 a 3 λ , and, therefore, is a factor in a 2 λ -m 2 a 3 λ =a 4 λ .

Reasoning this way, we are convinced that δ is included as a multiplier 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 δ is included as a multiplier in λ . Therefore the number δ is the common divisor of numbers λ And a 2 .

Let us 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 relatively simple, i.e. have a single common divisor 1. Then ac And b also have a single common divisor 1. Therefore 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 approval 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 relative to the number b.

2. Let us have two rows of numbers

such that every number in the first series is prime in the ratio of every number in the second series. Then the product

You need to find numbers that are divisible by each of these numbers.

If a number is divisible by a 1, then it has the form 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 multiples of numbers a 1 and a 2 .

a 1 and a 2 are relatively prime, then the least common multiple of the numbers a 1 and a 2:

We need to find the least common multiple of these numbers.

From the above it follows that any multiple of numbers a 1 , a 2 , a 3 must be a multiple of numbers ε And a 3 and back. Let the least common multiple of the numbers ε And a 3 yes ε 1 . Next, multiples 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 yes ε 2. Thus, we found out that all multiples of numbers a 1 , a 2 , a 3 ,...,a m coincide with multiples of a certain number ε n, which is called the least common multiple of the given numbers.

In the special case when the numbers a 1 , a 2 , a 3 ,...,a m are relatively prime, then the least common multiple of the numbers a 1 , a 2, as shown above, has the form (3). Next, since a 3 prime in relation to numbers a 1 , a 2 then a 3 prime number a 1 · a 2 (Corollary 1). Means the least common multiple of numbers a 1 ,a 2 ,a 3 is a number a 1 · a 2 · a 3. Reasoning in a similar way, we arrive at the following statements.

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.

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 in this case this 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 of the LCM( m, n).

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

So, Chebyshev function. And:

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.

The numbers 2,3,11,37 are prime numbers, 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 = 2 2 2 3 3 7,

2) write down the powers of all prime factors:

504 = 2 2 2 3 3 7 = 2 3 3 2 7 1,

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

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

5) multiply these powers.

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

Solution. 168 = 2 2 2 3 7 = 2 3 3 1 7 1,

180 = 2 2 3 3 5 = 2 2 3 2 5 1,

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

We write down the greatest powers of all prime divisors and multiply them:

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

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.