Consider the solution to 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 they both take a whole number of steps.

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

First, we will write out all the 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 multiples 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 these is 300. In this case, it will be called the least common multiple of 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 cover this path in 4 steps, and the girl will need to take 5 steps.

Least Common Multiple Determination

• Least common multiple of two natural numbers a and b is called 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 factor these numbers into prime factors.

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

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

As a result, we get a series 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.

Consider three ways to find the least common multiple.

Finding by factoring

The first way is to find the least common multiple by factoring these numbers into prime factors.

Suppose we need to find the LCM of numbers: 99, 30 and 28. To do this, we decompose each of these numbers into prime factors:

For the desired number to be divisible by 99, 30 and 28, it is necessary and sufficient that all prime factors of these divisors enter into it. To do this, we need to take all the prime factors of these numbers to the greatest possible power and multiply them together:

2 2 3 2 5 7 11 = 13 860

So the LCM (99, 30, 28) = 13 860. No other number less than 13 860 is divisible by 99, 30 or 28.

To find the least common multiple of these numbers, you need to factor them into prime factors, then take each prime factor with the largest exponent that it meets, and multiply these factors together.

Since coprime numbers do not have common prime factors, their least common multiple is equal to the product of these numbers. For example, three numbers: 20, 49 and 33 are mutually prime. That's why

LCM (20, 49, 33) = 20 49 33 = 32 340.

The same should be done when looking for the least common multiple of different primes. For example, LCM (3, 7, 11) = 3 7 11 = 231.

Finding by selection

The second way is to find the least common multiple by fitting.

Example 1. When the largest of the given numbers is divided entirely by the other given numbers, the LCM of these numbers is equal to the larger of them. For example, given four numbers: 60, 30, 10 and 6. Each of them is divisible by 60, therefore:

LCM (60, 30, 10, 6) = 60

Otherwise, the following procedure is used to find the least common multiple:

1. Determine the largest number of the given numbers.
2. Next, we find numbers that are multiples of the largest number, multiplying it by natural numbers in ascending order and checking whether the remaining given numbers are divisible by the resulting product.

Example 2. Given three numbers 24, 3 and 18. Determine the largest of them - this is the number 24. Next, find numbers that are multiples of 24, checking whether each of them is divisible by 18 and 3:

24 1 = 24 - divisible by 3, but not divisible by 18.

24 2 = 48 - divisible by 3, but not divisible by 18.

24 3 = 72 - divisible by 3 and 18.

So the LCM (24, 3, 18) = 72.

Finding by sequentially finding the LCM

The third way is to find the least common multiple by sequentially finding the LCM.

The LCM of two given numbers is equal to the product of these numbers divided by their greatest common divisor.

Example 1. Let's find the LCM of two given numbers: 12 and 8. Determine their greatest common divisor: GCD (12, 8) = 4. Multiply these numbers:

We divide the work into their GCD:

Thus, LCM (12, 8) = 24.

To find the LCM of three or more numbers, use the following procedure:

1. First, find the LCM of any two of the given numbers.
2. Then, the LCM of the found least common multiple and the third given number.
3. Then, the LCM of the resulting least common multiple and the fourth number, etc.
4. Thus, the search for the LCM continues as long as there are numbers.

Example 2. Let's find the LCM of the three given numbers: 12, 8 and 9. The LCM of the numbers 12 and 8 we have already found in the previous example (this is the number 24). It remains to find the least common multiple of 24 and the third given number - 9. Determine their greatest common divisor: GCD (24, 9) = 3. Multiply the LCM with the number 9:

We divide the work into their GCD:

So the LCM (12, 8, 9) = 72.

Definition. The largest natural number by which the numbers a and b are divisible without remainder is called greatest common factor (gcd) these numbers.

Find the greatest common divisor of 24 and 35.
The divisors of 24 will be the numbers 1, 2, 3, 4, 6, 8, 12, 24, and the divisors of 35 will be 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 simple.

Definition. Natural numbers are called mutually simple 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.

Factoring the numbers 48 and 36, we get:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
From the factors included in the decomposition of the first of these numbers, delete those that are not included in the decomposition of the second number (that is, two twos).
Factors remain 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 factor

2) from the factors included in the decomposition of one of these numbers, delete those that are not included in the decomposition of other numbers;
3) find the product of the remaining factors.

If all these numbers are divisible by one of them, then this number is greatest common factor given numbers.
For example, the greatest common divisor of 15, 45, 75, and 180 is 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 are called the smallest natural number, which is a multiple of both a and b. The least common multiple (LCM) of numbers 75 and 60 can be found without writing out the multiples of these numbers in a row. To do this, we decompose 75 and 60 into prime factors: 75 = 3 * 5 * 5, and 60 = 2 * 2 * 3 * 5.
Let us write out the factors included in the decomposition of the first of these numbers, and add to them the missing factors 2 and 2 from the decomposition of the second number (i.e., 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 75 and 60.

Also find the least common multiple for three or more numbers.

To find least common multiple several natural numbers, you need:
1) decompose them into prime factors;
2) write down the factors included in the decomposition 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 the other numbers, then this number is the least common multiple of these numbers.
For example, the least common multiple of 12, 15, 20, and 60 is 60 because it is divisible by all of these numbers.

Pythagoras (VI century BC) and his students studied the question of divisibility of numbers. A number equal to the sum of all its divisors (without the number itself), they called 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 knew only the first three perfect numbers. The fourth - 8128 - became known in the 1st century. n. NS. The fifth - 33 550 336 - was found in the 15th century. By 1983, 27 perfect numbers were already known. But until now, scientists do not know whether there are odd perfect numbers, whether there is the 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, that is, prime numbers are like bricks from which the rest of the natural numbers are built.
You probably noticed that prime numbers in a 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 are prime numbers. The question arises: is there a last (largest) prime number? The ancient Greek mathematician Euclid (III century BC) in his book "Beginnings", which was for two thousand years the main textbook of mathematics, proved that there are infinitely many primes, that is, behind each prime there is an even greater prime number.
To find prime numbers, another Greek mathematician of the same time, Eratosthenes, came up with such a method. He wrote down all the numbers from 1 to some number, and then crossed out a unit that is neither a prime nor a composite number, then crossed out all the numbers after 2 (numbers divisible by 2, i.e. 4, 6 , 8, etc.). The first remaining number after 2 was 3. Then all numbers after 3 (numbers that are multiples of 3, that is, 6, 9, 12, etc.) were crossed out after two. in the end, only the prime numbers remained uncrossed.

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

For example:

The number 12 is divided by 1, by 2, by 3, by 4, by 6, by 12;

The number 36 is divisible by 1, 2, 3, 4, 6, 12, 18, 36.

The numbers by which the number is evenly divisible (for 12 it is 1, 2, 3, 4, 6 and 12) are called divisors... Natural number divisor a is a natural number that divides a given number a without a remainder. A natural number that has more than two divisors is called composite .

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

Common multiple multiple 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 j total multiples, there is always the smallest, in this case it is 90. This number is called the smallestcommon multiple (LCM).

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

Least Common Multiple (LCM). Properties.

Commutability:

Associativity:

In particular, if and are coprime numbers, then:

Least common multiple of two integers m and n is the 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).

LCM ( 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- various primes, and d 1, ..., d k and e 1, ..., e k- non-negative integers (they can be zeros if the corresponding prime is absent in the decomposition).

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

In other words, the LCM decomposition contains all prime factors 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 consecutive calculations of the LCM of two numbers:

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

- to decompose numbers into prime factors;

- transfer the largest expansion into the factors of the desired product (the product of the factors of the a large number from 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 fewer times;

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

Any two or more natural numbers have their 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 (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 divided by all the given numbers without a remainder. This is the smallest possible product (150, 250, 300 ...), which is a multiple of all given numbers.

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

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

Another option:

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

1) represent each number as the 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 (factors) of each of these numbers;

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

5) multiply these degrees.

Example... Find the LCM of 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 out the greatest powers of all prime factors and multiply them:

LCM = 2 4 3 3 5 1 7 1 = 15 120.

The online calculator allows you to quickly find the greatest common divisor and least common multiple for two or any other number of numbers.

Calculator for finding GCD and LCM

Find GCD and LCM

Found GCD and NOC: 5806

How to use the calculator

• Enter numbers in the input field
• If you enter incorrect characters, the input field will be highlighted in red
• click the button "Find GCD and LCM"

How to enter numbers

• Numbers are entered separated by space, period or comma
• The length of the entered numbers is not limited, so finding the GCD and LCM of long numbers will not be difficult

What are GCD and NOC?

Greatest common divisor multiple numbers - this is the largest natural integer by which all original numbers are divisible without a remainder. The greatest common factor is abbreviated as Gcd.
Least common multiple several numbers are smallest number, which is divisible by each of the original numbers without a remainder. The least common multiple is abbreviated as NOC.

How to check that a number is divisible by another number without a remainder?

To find out whether one number is divisible by another without a remainder, you can use some of the divisibility properties of numbers. Then, by combining them, one can check divisibility into some of them and their combinations.

Some signs of divisibility of numbers

1. The criterion for divisibility of a number by 2
To determine whether a number is divisible by two (whether it is even), it is enough to look at the last digit of this number: if it is 0, 2, 4, 6 or 8, then the number is even, which means it is divisible by 2.
Example: determine if 34938 is divisible by 2.
Solution: look at the last digit: 8 - so the number is divisible by two.

2. The sign of divisibility of a number by 3
A number is divisible by 3 when the sum of its digits is divisible by three. Thus, to determine if a number is divisible by 3, you need to calculate the sum of the digits and check if it is divisible by 3. Even if the sum of the digits is very large, you can repeat the same process again.
Example: determine if 34938 is divisible by 3.
Solution: we count the sum of the digits: 3 + 4 + 9 + 3 + 8 = 27.27 is divisible by 3, which means that the number is divisible by three.

3. The sign of divisibility of a number by 5
A number is divisible by 5 when its last digit is zero or five.
Example: determine if 34938 is divisible by 5.
Solution: look at the last digit: 8 means the number is NOT divisible by five.

4. The sign of divisibility of a number by 9
This feature is very similar to the divisibility by three: a number is divisible by 9 when the sum of its digits is divisible by 9.
Example: determine if 34938 is divisible by 9.
Solution: we count the sum of digits: 3 + 4 + 9 + 3 + 8 = 27.27 is divisible by 9, which means that the number is divisible by nine.

How to find the gcd and LCM of two numbers

How to find the gcd of two numbers

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

Let us consider this method using the example of finding the GCD (28, 36):

1. Factor both numbers: 28 = 1 2 2 7, 36 = 1 2 2 3 3
2. We find the common factors, that is, those that both numbers have: 1, 2 and 2.
3. We calculate the product of these factors: 1 · 2 · 2 = 4 - this is the greatest common divisor of the numbers 28 and 36.

How to find the LCM of two numbers

There are two most common ways to find the least multiple of two numbers. The first way is that you can write out the first multiples of two numbers, and then choose among them such a number that will be common to both numbers and at the same time the smallest. And the second is to find the GCD of these numbers. Let's consider only it.

To calculate the LCM, you need to calculate the product of the original numbers and then divide it by the previously found GCD. Let's find the LCM for the same numbers 28 and 36:

1. Find the product of the numbers 28 and 36: 28 36 = 1008
2. GCD (28, 36), as is already known, is equal to 4
3. LCM (28, 36) = 1008/4 = 252.

Finding GCD and LCM for several numbers

The greatest common factor can be found for several numbers, not just two. For this, the numbers to be searched for the greatest common factor are decomposed into prime factors, then the product of the common prime factors of these numbers is found. Also, to find the GCD of several numbers, you can use the following ratio: Gcd (a, b, c) = gcd (gcd (a, b), c).

A similar relationship is valid for the least common multiple: LCM (a, b, c) = LCM (LCM (a, b), c)

Example: find GCD and LCM for numbers 12, 32 and 36.

1. First, factor the numbers: 12 = 1 2 2 3, 32 = 1 2 2 2 2 2 2, 36 = 1 2 2 3 3.
2. Let's find common factors: 1, 2 and 2.
3. Their product will give GCD: 1 2 2 = 4
4. Let us now find the LCM: for this, we first find the LCM (12, 32): 12 · 32/4 = 96.
5. To find the LCM of all three numbers, you need to find the GCD (96, 36): 96 = 1 2 2 2 2 2 2 3, 36 = 1 2 2 3 3, GCD = 1 2 2 3 = 12.
6. LCM (12, 32, 36) = 96 36/12 = 288.