Least common multiple of 3 and 2. Common divisor and multiple

Second number: b=

Digit separator No space separator " ´

Result:

Greatest Common Divisor gcd( a,b)=6

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

The largest natural number by which the numbers a and b are divisible without remainder is called greatest common divisor(gcd) of these numbers. Denoted gcd(a,b), (a,b), gcd(a,b) or hcf(a,b).

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

Integers a and b are called coprime if they have no common divisors other than +1 and −1.

Greatest Common Divisor

Let two be given positive numbers a 1 and a 2 1). It is required to find a common divisor of these numbers, i.e. find such a number λ , which divides the numbers a 1 and a 2 at the same time. Let's describe the algorithm.

1) In this article, the word number will mean an integer.

Let a 1 ≥ a 2 and let

Where m 1 , a 3 are some integers, a 3 <a 2 (remainder from division a 1 on 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 (Assertion 2 of the article "Divisibility of numbers. Sign of divisibility"). It follows that every common divisor a 1 and a 2 is a common divisor a 2 and a 3 . The converse 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 are also divided into λ . Hence 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 a common divisor of numbers a 1 and a 2 reduced to a simpler problem of finding a common divisor of numbers a 2 and a 3 .

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

,

Where m 1 and a 4 are some integers, ( a 4 remainder of division a 2 on a 3 (a 4 <a 3)). By similar reasoning, we come to the conclusion that the common divisors of numbers a 3 and a 4 is the same as 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 , ... 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 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 (recall 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 greatest number divisor 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 are called greatest common divisor numbers a 1 and a 2 .

Numbers a 1 and a 2 can be both positive and 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 not defined.

The above algorithm is called Euclid's 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.

At 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 numbers a 1 and a 2 is equal to one. Then these numbers are called coprime numbers that do not have a common divisor.

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

.

It follows from the conditions of the theorem that the greatest common divisor of numbers a 1 and a 2 , and therefore a n and a n+1 is 1. I.e. a n+1=1.

Let's multiply all these equalities by λ , Then

.

Let the common divisor a 1 λ And a 2 is δ . Then δ enters as a factor in a 1 λ , m 1 a 2 λ and in a 1 λ -m 1 a 2 λ =a 3 λ (See "Divisibility of numbers", Statement 2). Further δ enters as a factor in a 2 λ And m 2 a 3 λ , and hence enters as a factor in a 2 λ -m 2 a 3 λ =a 4 λ .

By reasoning in this way, we are convinced that δ enters as a factor 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 δ enters as a factor in λ . Hence the number δ is a common divisor of numbers λ And a 2 .

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 coprime, i.e. have a single common divisor 1. Then ac And b also have a single common divisor 1. Hence 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 assertion 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 with respect to the number b.

2. Let we have two rows of numbers

such that every number in the first row is prime with respect to every number in the second row. Then the product

It is required to find such numbers that are divisible by each of these numbers.

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

a 1 and a 2 coprime, then the least common multiple of the numbers a 1 and a 2:

Find the least common multiple of these numbers.

It follows from the above that any multiple of the numbers a 1 , a 2 , a 3 must be a multiple of numbers ε And a 3 and vice versa. Let the least common multiple of the numbers ε And a 3 is ε 1 . Further, a multiple 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 is ε 2. Thus, we found out that all multiples of numbers a 1 , a 2 , a 3 ,...,a m coincide with multiples of some specific number ε n , which is called the least common multiple of the given numbers.

In the particular case when the numbers a 1 , a 2 , a 3 ,...,a m coprime, then the least common multiple of the numbers a 1 , a 2 as shown above has the form (3). Further, since a 3 prime with respect to numbers a 1 , a 2 , then a 3 is a prime relative number a 1 · a 2 (Corollary 1). So the least common multiple of the numbers a 1 ,a 2 ,a 3 is a number a 1 · a 2 · a 3 . Arguing in a similar way, we arrive at the following assertions.

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 .

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 number of multiples

Look at these numbers. The method described here is best used when given two numbers that are both 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.

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

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

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

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

Least common multiple (LCM). Properties.

Commutativity:

Associativity:

In particular, if and are coprime numbers , then:

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

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

So, Chebyshev function. 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 relationship with the LCM:

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

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

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

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

Example:

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

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

- decompose numbers into prime factors;

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

- the resulting product of prime factors will be 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) were supplemented with a factor of 3 (the number 21), the resulting product (84) will be the smallest number that is divisible by 21 and 28.

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

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

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

Another option:

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

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

504 \u003d 2 2 2 3 3 7,

2) write down the powers of all prime factors:

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

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

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

5) multiply these powers.

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

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

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

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

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

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

The topic "Multiple numbers" is studied in the 5th grade of a comprehensive school. Its goal is to improve the written and oral skills of mathematical calculations. In this lesson, new concepts are introduced - "multiple numbers" and "divisors", the technique of finding divisors and multiples of a natural number, the ability to find LCM in various ways is worked out.

This topic is very important. Knowledge on 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 considered to be the least. A multiple cannot be less than the number itself.

It is necessary to prove that the number 125 is a multiple of the number 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.

When calculating the LCM, there are special cases.

1. If you need to find a common multiple for 2 numbers (for example, 80 and 20), where one of them (80) is divisible without a remainder by the other (20), then this number (80) is the smallest 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.

Consider the last example. 6 and 7 in relation to 42 are divisors. They divide a multiple without a remainder.

In this example, 6 and 7 are pair divisors. 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.

In another example, you need to determine if 9 is a divisor with respect to 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 is itself divisible by that number.

Greatest Common Divisor of Numbers a And b, multiplied by their smallest multiple, will give the product of the numbers themselves a And b.

Namely: GCD (a, b) x LCM (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 decompose these numbers into prime factors, write them as a product of powers:

168=2³x3¹x7¹

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

LCM (168, 180, 3024) = 15120.

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

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

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

A common multiple of natural numbers is a number that is divisible by them without a remainder.

How to find the least common multiple of numbers

The least common multiple (LCM) of numbers (two, three or more) is the smallest natural number that is evenly divisible by all these numbers.

To find the NOC, you can use several methods.

For small numbers, it is convenient to write out in a line all the multiples of these numbers until a common one is found among them. Multiples are denoted in the record with a capital letter K.

For example, multiples of 4 can be written like this:

K(4) = (8,12, 16, 20, 24, ...)

K(6) = (12, 18, 24, ...)

So, you can see that the least common multiple of the numbers 4 and 6 is the number 24. This entry is performed as follows:

LCM(4, 6) = 24

If the numbers are large, find the common multiple of three or more numbers, then it is better to use another way to calculate the LCM.

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

First you need to write out the expansion of the largest of the numbers in a line, and below it - the rest.

In the expansion of each number, there may be a different number of factors.

For example, let's factor the numbers 50 and 20 into prime factors.

In the expansion of the smaller number, one should underline the factors that are missing in the expansion of the first largest number, and then add them to it. In the presented example, a deuce is missing.

Now we can calculate the least common multiple of 20 and 50.

LCM (20, 50) = 2 * 5 * 5 * 2 = 100

Thus, the product of the prime factors of the larger number and the factors of the second number, which are not included in the decomposition of the larger number, will be the least common multiple.

To find the LCM of three or more numbers, all of them should be decomposed into prime factors, as in the previous case.

As an example, you can find the least common multiple of the numbers 16, 24, 36.

36 = 2 * 2 * 3 * 3

24 = 2 * 2 * 2 * 3

16 = 2 * 2 * 2 * 2

Thus, only two deuces from the decomposition of sixteen were not included in the factorization of a larger number (one is in the decomposition of twenty-four).

Thus, they need to be added to the decomposition of a larger number.

LCM (12, 16, 36) = 2 * 2 * 3 * 3 * 2 * 2 = 9

There are special cases of determining the least common multiple. So, if one of the numbers can be divided without a remainder by another, then the larger of these numbers will be the least common multiple.

For example, NOCs of twelve and twenty-four would be twenty-four.

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

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