How to find the least common multiple of two numbers. Nod and nok of two numbers, Euclidean algorithm

Consider the solution of the following problem. The boy's step is 75 cm, and the girl's step is 60 cm. It is necessary to find the smallest distance at which both of them will take an integer number of steps.

Decision. The entire path that the guys will go through must be divisible by 60 and 70 without a remainder, since they must each take an integer number of steps. In other words, the answer must be a multiple of both 75 and 60.

First, we will write out all multiples, for the number 75. We get:

• 75, 150, 225, 300, 375, 450, 525, 600, 675, … .

Now let's write out the numbers that will be a multiple of 60. We get:

• 60, 120, 180, 240, 300, 360, 420, 480, 540, 600, 660, … .

Now we find the numbers that are in both rows.

• Common multiples of numbers will be numbers, 300, 600, etc.

The smallest of them is the number 300. In this case, it will be called the least common multiple of the numbers 75 and 60.

Returning to the condition of the problem, the smallest distance at which the guys take an integer number of steps will be 300 cm. The boy will go this way in 4 steps, and the girl will need to take 5 steps.

Finding the Least Common Multiple

• The least common multiple of two natural numbers a and b is the smallest natural number that is a multiple of both a and b.

In order to find the least common multiple of two numbers, it is not necessary to write down all the multiples for these numbers in a row.

You can use the following method.

How to find the least common multiple

First, you need to decompose these numbers into prime factors.

• 60 = 2*2*3*5,
• 75=3*5*5.

Now let's write down all the factors that are in the expansion of the first number (2,2,3,5) and add to it all the missing factors from the expansion of the second number (5).

As a result, we get a series of prime numbers: 2,2,3,5,5. The product of these numbers will be the least common factor for these numbers. 2*2*3*5*5 = 300.

General scheme for finding the least common multiple

• 1. Decompose numbers into prime factors.
• 2. Write down the prime factors that are part of one of them.
• 3. Add to these factors all those that are in the decomposition of the rest, but not in the selected one.
• 4. Find the product of all the factors written out.

This method is universal. It can be used to find the least common multiple of any number of natural numbers.

A multiple of a number 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 evenly divisible by each number in the group. To find the least common multiple, you need to find the prime factors of the given numbers. Also, LCM can be calculated using a number of other methods that are applicable to groups of two or more numbers.

Steps

A series of multiples

Look at these numbers. The method described here is best used when given two numbers that are each less than 10. If large numbers are given, use a different method.

• For example, find the least common multiple of the numbers 5 and 8. These are small numbers, so this method can be used.

1. A multiple of a number is a number that is divisible by a given number without a remainder. Multiple numbers can be found in the multiplication table.

   • For example, numbers that are multiples of 5 are: 5, 10, 15, 20, 25, 30, 35, 40.

2. Write down a series of numbers that are multiples of the first number. Do this under multiples of the first number to compare two rows of numbers.

   • For example, numbers that are multiples of 8 are: 8, 16, 24, 32, 40, 48, 56, and 64.

3. Find the smallest number that appears in both series of multiples. You may have to write long series of multiples to find the total. The smallest number that appears in both series of multiples is the least common multiple.

   • For example, the smallest number that appears in the series of multiples of 5 and 8 is 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 that are both 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 this method can be used.

   2. Factorize the first number. That is, you need to find such prime numbers, when multiplied, you get a given number. Having found prime factors, write them down as an equality.

      • 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 down 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 get this 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 down as an expression: .

   4. Write down the factors common to both numbers. Write such factors as a multiplication operation. As you write down each factor, cross it out in both expressions (expressions that describe the decomposition of numbers into prime factors).

      • For example, the common factor for both numbers is 2, so write 2 × (\displaystyle 2\times ) and cross out the 2 in both expressions.
      • The common factor for both numbers 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 as follows: 2 × 2 × 5 (\displaystyle 2\times 2\times 5)
      • In the expression 84 = 2 × 7 × 3 × 2 (\displaystyle 84=2\times 7\times 3\times 2) both deuces (2) are also crossed out. Factors 7 and 3 are not crossed out, so write the multiplication operation as follows: 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 divisors

      1. Draw a grid like you would for a game of tic-tac-toe. Such a grid consists of two parallel lines that intersect (at right angles) with two other parallel lines. This will result in three rows and three columns (the grid looks a lot like the # sign). Write the first number in the first row and second column. Write the second number in the first row and third column.

         • For example, find the least common multiple of 18 and 30. Write 18 in the first row and second column, and write 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 divisors, but this is not a prerequisite.

         • For example, 18 and 30 are even numbers, so their common divisor 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 corresponding number. The 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 15 under 30.

      4. Find a divisor common to both quotients. If there is no such divisor, skip the next two steps. Otherwise, write down 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 the 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, supplement the grid with additional cells. Repeat the above 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 highlighted 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 the 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 by which to divide. The quotient is the result of dividing two numbers. The remainder is the number left when two numbers are divided.

         • For example, in the expression 15 ÷ 6 = 2 (\displaystyle 15\div 6=2) rest. 3:
           15 is the divisible
           6 is the divisor
           2 is private
           3 is the remainder.

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 the number $a$ is called a multiple of $b$.

Let $a$ and $b$ be natural numbers. The number $c$ is called a common divisor for 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 the largest one, which is called the greatest common divisor of the numbers $a$ and $b$, and the notation is used to denote it:

$gcd \ (a;b) \ ​​or \ D \ (a;b)$

To find the greatest common divisor of two numbers:

1. 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 monomials $63$ and $81$.

We will find according to the presented algorithm. For this:

Let's decompose 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 the set of divisors of numbers.

Example 3

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

Decision:

Find the set of divisors of $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$

Now let's find the set of divisors of $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$. So the greatest common divisor of $48$ and $60$ is $12$.

Definition of NOC

Definition 3

common multiple 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 without a remainder. For example, for the numbers $25$ and $50$, the common multiples will be the numbers $50,100,150,200$, etc.

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

To find the LCM of two numbers, you need:

1. Decompose numbers into prime factors
2. Write out the factors that are part of the first number and add to them the factors that are part of the second and do not go to the first

Example 4

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

We will find according to the presented algorithm. For this

Decompose numbers into prime factors

$99=3\cdot 3\cdot 11$

Write down the factors included in the first

add to them factors that are part of the second and do not go to the first

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

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

Compiling lists of divisors of numbers is often very time consuming. There is a way to find GCD called Euclid's algorithm.

Statements on which Euclid's 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 decrease 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

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

If K$(a;b)=k$ and $m$-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 a common multiple of $a$ and $b$

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

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

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

The material presented below is a logical continuation of the theory from the article under the heading LCM - least common multiple, definition, examples, relationship between LCM and GCD. Here we will talk about finding the least common multiple (LCM), and pay special attention to solving examples. Let us first show how the LCM of two numbers is calculated in terms of the GCD of these numbers. Next, consider finding the least common multiple by factoring numbers into prime factors. After that, we will focus on finding the LCM of three or more numbers, and also pay attention to the calculation of the LCM of negative numbers.

Page navigation.

Calculation of the least common multiple (LCM) through gcd

One way to find the least common multiple is based on the relationship between LCM and GCD. The existing relationship between LCM and GCD allows you to calculate the least common multiple of two positive integers through the known greatest common divisor. The corresponding formula has the form LCM(a, b)=a b: GCM(a, b) . Consider examples of finding the LCM according to the above formula.

Example.

Find the least common multiple of the two numbers 126 and 70 .

Decision.

In this example a=126 , b=70 . Let us use the relationship between LCM and GCD expressed by the formula LCM(a, b)=a b: GCM(a, b). That is, first we have to find the greatest common divisor of the numbers 70 and 126, after which we can calculate the LCM of these numbers according to the written formula.

Find gcd(126, 70) using Euclid's algorithm: 126=70 1+56 , 70=56 1+14 , 56=14 4 , hence gcd(126, 70)=14 .

Now we find the required least common multiple: LCM(126, 70)=126 70: GCM(126, 70)= 126 70:14=630 .

Answer:

LCM(126, 70)=630 .

Example.

What is LCM(68, 34) ?

Decision.

As 68 is evenly divisible by 34 , then gcd(68, 34)=34 . Now we calculate the least common multiple: LCM(68, 34)=68 34: LCM(68, 34)= 68 34:34=68 .

Answer:

LCM(68, 34)=68 .

Note that the previous example fits the following rule for finding the LCM for positive integers a and b : if the number a is divisible by b , then the least common multiple of these numbers is a .

Finding the LCM by Factoring Numbers into Prime Factors

Another way to find the least common multiple is based on factoring numbers into prime factors. If we make a product of all prime factors of these numbers, after which we exclude from this product all common prime factors that are present in the expansions of these numbers, then the resulting product will be equal to the least common multiple of these numbers.

The announced rule for finding the LCM follows from the equality LCM(a, b)=a b: GCM(a, b). Indeed, the product of the numbers a and b is equal to the product of all the factors involved in the expansions of the numbers a and b. In turn, gcd(a, b) is equal to the product of all prime factors that are simultaneously present in the expansions of the numbers a and b (which is described in the section on finding the gcd using the decomposition of numbers into prime factors).

Let's take an example. Let we know that 75=3 5 5 and 210=2 3 5 7 . Compose the product of all factors of these expansions: 2 3 3 5 5 5 7 . Now we exclude from this product all the factors that are present both in the expansion of the number 75 and in the expansion of the number 210 (such factors are 3 and 5), then the product will take the form 2 3 5 5 7 . The value of this product is equal to the least common multiple of the numbers 75 and 210, that is, LCM(75, 210)= 2 3 5 5 7=1 050.

Example.

After factoring the numbers 441 and 700 into prime factors, find the least common multiple of these numbers.

Decision.

Let's decompose the numbers 441 and 700 into prime factors:

We get 441=3 3 7 7 and 700=2 2 5 5 7 .

Now let's make a product of all the factors involved in the expansions of these numbers: 2 2 3 3 5 5 7 7 7 . Let us exclude from this product all the factors that are simultaneously present in both expansions (there is only one such factor - this is the number 7): 2 2 3 3 5 5 7 7 . Thus, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

Answer:

LCM(441, 700)= 44 100 .

The rule for finding the LCM using the decomposition of numbers into prime factors can be formulated a little differently. If we add the missing factors from the expansion of the number b to the factors from the expansion of the number a, then the value of the resulting product will be equal to the least common multiple of the numbers a and b.

For example, let's take all the same numbers 75 and 210, their expansions into prime factors are as follows: 75=3 5 5 and 210=2 3 5 7 . To the factors 3, 5 and 5 from the decomposition of the number 75, we add the missing factors 2 and 7 from the decomposition of the number 210, we get the product 2 3 5 5 7 , the value of which is LCM(75, 210) .

Example.

Find the least common multiple of 84 and 648.

Decision.

We first obtain the decomposition of the numbers 84 and 648 into prime factors. They look like 84=2 2 3 7 and 648=2 2 2 3 3 3 3 . To the factors 2 , 2 , 3 and 7 from the expansion of the number 84 we add the missing factors 2 , 3 , 3 and 3 from the expansion of the number 648 , we get the product 2 2 2 3 3 3 3 7 , which is equal to 4 536 . Thus, the desired least common multiple of the numbers 84 and 648 is 4,536.

Answer:

LCM(84, 648)=4 536 .

Finding the LCM of three or more numbers

The least common multiple of three or more numbers can be found by successively finding the LCM of two numbers. Recall the corresponding theorem, which gives a way to find the LCM of three or more numbers.

Theorem.

Let positive integers a 1 , a 2 , …, a k be given, the least common multiple m k of these numbers is found in the sequential calculation m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , a k) .

Consider the application of this theorem on the example of finding the least common multiple of four numbers.

Example.

Find the LCM of the four numbers 140 , 9 , 54 and 250 .

Decision.

In this example a 1 =140 , a 2 =9 , a 3 =54 , a 4 =250 .

First we find m 2 \u003d LCM (a 1, a 2) \u003d LCM (140, 9). To do this, using the Euclidean algorithm, we determine gcd(140, 9) , we have 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , therefore, gcd(140, 9)=1 , whence LCM(140, 9)=140 9: LCM(140, 9)= 140 9:1=1 260 . That is, m 2 =1 260 .

Now we find m 3 \u003d LCM (m 2, a 3) \u003d LCM (1 260, 54). Let's calculate it through gcd(1 260, 54) , which is also determined by the Euclid algorithm: 1 260=54 23+18 , 54=18 3 . Then gcd(1 260, 54)=18 , whence LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . That is, m 3 \u003d 3 780.

Left to find m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250). To do this, we find GCD(3 780, 250) using the Euclid algorithm: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Therefore, gcd(3 780, 250)=10 , whence gcd(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . That is, m 4 \u003d 94 500.

So the least common multiple of the original four numbers is 94,500.

Answer:

LCM(140, 9, 54, 250)=94,500.

In many cases, the least common multiple of three or more numbers is conveniently found using prime factorizations of given numbers. In this case, the following rule should be followed. The least common multiple of several numbers is equal to the product, which is composed as follows: the missing factors from the expansion of the second number are added to all the factors from the expansion of the first number, the missing factors from the expansion of the third number are added to the obtained factors, and so on.

Consider an example of finding the least common multiple using the decomposition of numbers into prime factors.

Example.

Find the least common multiple of five numbers 84 , 6 , 48 , 7 , 143 .

Decision.

First, we obtain the expansions of these numbers into prime factors: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 prime factors) and 143=11 13 .

To find the LCM of these numbers, to the factors of the first number 84 (they are 2 , 2 , 3 and 7 ) you need to add the missing factors from the expansion of the second number 6 . The expansion of the number 6 does not contain missing factors, since both 2 and 3 are already present in the expansion of the first number 84 . Further to the factors 2 , 2 , 3 and 7 we add the missing factors 2 and 2 from the expansion of the third number 48 , we get a set of factors 2 , 2 , 2 , 2 , 3 and 7 . There is no need to add factors to this set in the next step, since 7 is already contained in it. Finally, to the factors 2 , 2 , 2 , 2 , 3 and 7 we add the missing factors 11 and 13 from the expansion of the number 143 . We get the product 2 2 2 2 3 7 11 13 , which is equal to 48 048 .

Let's start studying the least common multiple of two or more numbers. In the section, we will give a definition of the term, consider a theorem that establishes a relationship 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 for the number 12, the common multiples 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 for the numbers 2 and 3 will be the numbers 12 , 6 , − 24 , 72 , 468 , − 100 010 004 and a number of 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 the numbers 2 and 3, the numbers 16 , − 27 , 5009 , 27001 will not be common multiples.

0 is a common multiple of any set of non-zero integers.

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

Is it possible to find an LCM for all numbers?

The common multiple can be found for any integers.

Example 2

Suppose we are given k integers a 1 , a 2 , … , a k. The number that we get during the multiplication of numbers a 1 a 2 … a k according to the divisibility property, it will be divided by each of the factors that were included in the original product. This means that the product of the 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, then the number of common multiples is infinite.

Least Common Multiple (LCM) - Definition, Symbol and Examples

Recall the concept of the smallest number from a given set of numbers, which we considered in the Comparison of Integers section. With this concept in mind, 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 least positive common multiple of these numbers.

The least common multiple exists for any number of given numbers. The abbreviation NOK is the most commonly used to designate a concept in the reference literature. Shorthand for Least Common Multiple for Numbers a 1 , a 2 , … , a k will look like LCM (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 four numbers - 2 , 12 , 15 and 3 will be equal to 60 . Shorthand will be LCM (- 2 , 12 , 15 , 3) ​​= 60 .

Not for all groups of given numbers, the least common multiple is obvious. Often it has to be calculated.

Relationship between NOC and NOD

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 the numbers a and b divided by the greatest common divisor of the numbers a and b , that is, LCM (a , b) = a b: GCD (a , b) .

Proof 1

Suppose we have some number M which is a multiple of numbers a and b . If the number M is divisible by a , there is also some integer z , under which the equality M = a k. According to the definition of divisibility, if M is also 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 coprime 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 relatively prime numbers, if a 1 and b 1 are mutually prime numbers, a 1 not divisible by b 1 despite the fact that a 1 k divided by b 1, then b 1 should share k.

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

Now instead of k put into equality M = a k expression of the form b: d t. This allows us to come to 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 have 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 common multiples of those two numbers;
• the least common multiple of coprime positive numbers a and b is equal to their product.

It is not difficult to substantiate these two facts. Any common multiple 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 coprime, then gcd (a, b) = 1, therefore, LCM (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, you need to sequentially find the LCM of two numbers.

Theorem 2

Let's pretend that a 1 , a 2 , … , a k are some positive integers. 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) .

Proof 2

The first corollary of the first theorem considered in this topic will help us to prove the correctness of the second theorem. Reasoning is built according to 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 m2;
• common multiples of numbers a 1, a 2 and a 3 m2 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 an m k.

So we have proved the theorem.

If you notice a mistake in the text, please highlight it and press Ctrl+Enter