But many natural numbers are also divisible by other natural numbers.
For example:
The number 12 is divisible by 1, by 2, by 3, by 4, by 6, by 12;
The number 36 is divisible by 1, by 2, by 3, by 4, by 6, by 12, by 18, by 36.
The numbers by which the number is divisible by a whole (for 12 these are 1, 2, 3, 4, 6 and 12) are called divisors of numbers. Divisor of a natural number a- is a natural number that divides a given number a without a trace. A natural number that has more than two divisors is called composite .
Please note that the numbers 12 and 36 have common factors. These numbers are: 1, 2, 3, 4, 6, 12. The greatest divisor of these numbers is 12. The common divisor of these two numbers a And b- this is the number by which both given numbers are divided without remainder a And b.
Common multiples several numbers is a number that is divisible by each of these numbers. For example, the numbers 9, 18 and 45 have a common multiple of 180. But 90 and 360 are also their common multiples. Among all common multiples there is always a smallest one, in this case it is 90. This number is called the smallestcommon multiple (CMM).
The LCM is always a natural number that must be greater than the largest of the numbers for which it is defined.
Least common multiple (LCM). Properties.
Commutativity:
Associativity:
In particular, if and are coprime numbers, then:
Least common multiple of two integers m And n is a divisor of all other common multiples m And n. Moreover, the set of common multiples m, n coincides with the set of multiples for LCM( m, n).
The asymptotics for can be expressed in terms of some number-theoretic functions.
So, Chebyshev function. And also:
This follows from the definition and properties of the Landau function g(n).
What follows from the law of distribution of prime numbers.
Finding the least common multiple (LCM).
NOC( a, b) can be calculated in several ways:
1. If the greatest common divisor is known, you can use its connection with the LCM:
2. Let the canonical decomposition of both numbers into prime factors be known:
Where p 1 ,...,p k- various prime numbers, and d 1 ,...,d k And e 1 ,...,e k— non-negative integers (they can be zeros if the corresponding prime is not in the expansion).
Then NOC ( a,b) is calculated by the formula:
In other words, the LCM decomposition contains all prime factors included in at least one of the decompositions of numbers a, b, and the largest of the two exponents of this multiplier is taken.
Example:
Calculating the least common multiple of several numbers can be reduced to several sequential calculations of the LCM of two numbers:
Rule. To find the LCM of a series of numbers, you need:
- decompose numbers into prime factors;
- transfer the largest decomposition (the product of the factors of the largest number of the given ones) to the factors of the desired product, and then add factors from the decomposition of other numbers that do not appear in the first number or appear in it fewer times;
— the resulting product of prime factors will be the LCM of the given numbers.
Any two or more natural numbers have their own LCM. If the numbers are not multiples of each other or do not have the same factors in the expansion, then their LCM is equal to the product of these numbers.
The prime factors of the number 28 (2, 2, 7) are supplemented with a factor of 3 (the number 21), the resulting product (84) will be the smallest number that is divisible by 21 and 28.
The prime factors of the largest number 30 are supplemented by the factor 5 of the number 25, the resulting product 150 is greater than the largest number 30 and is divisible by all given numbers without a remainder. This is the smallest possible product (150, 250, 300...) that is a multiple of all given numbers.
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.
Divisibility criteria for natural numbers.
Numbers divisible by 2 without a remainder are calledeven .
Numbers that are not evenly divisible by 2 are calledodd .
Test for divisibility by 2
If a natural number ends with an even digit, then this number is divisible by 2 without a remainder, and if a number ends with an odd digit, then this number is not evenly divisible by 2.
For example, the numbers 60 , 30 8 , 8 4 are divisible by 2 without remainder, and the numbers are 51 , 8 5 , 16 7 are not divisible by 2 without a remainder.
Test for divisibility by 3
If the sum of the digits of a number is divisible by 3, then the number is divisible by 3; If the sum of the digits of a number is not divisible by 3, then the number is not divisible by 3.
For example, let’s find out whether the number 2772825 is divisible by 3. To do this, let’s calculate the sum of the digits of this number: 2+7+7+2+8+2+5 = 33 - divisible by 3. This means the number 2772825 is divisible by 3.
Divisibility test by 5
If the record of a natural number ends with the digit 0 or 5, then this number is divisible by 5 without a remainder. If the record of a number ends with another digit, then the number is not divisible by 5 without a remainder.
For example, the numbers 15 , 3 0 , 176 5 , 47530 0 are divisible by 5 without remainder, and the numbers are 17 , 37 8 , 9 1 don't share.
Divisibility test by 9
If the sum of the digits of a number is divisible by 9, then the number is divisible by 9; If the sum of the digits of a number is not divisible by 9, then the number is not divisible by 9.
For example, let’s find out whether the number 5402070 is divisible by 9. To do this, let’s calculate the sum of the digits of this number: 5+4+0+2+0+7+0 = 16 - not divisible by 9. This means the number 5402070 is not divisible by 9.
Divisibility test by 10
If a natural number ends with the digit 0, then this number is divisible by 10 without a remainder. If a natural number ends with another digit, then it is not evenly divisible by 10.
For example, the numbers 40 , 17 0 , 1409 0 are divisible by 10 without remainder, and the numbers 17 , 9 3 , 1430 7 - don't share.
The rule for finding the greatest common divisor (GCD).
To find the greatest common divisor of several natural numbers, you need to:
2) from the factors included in the expansion of one of these numbers, cross out those that are not included in the expansion of other numbers;
3) find the product of the remaining factors.
Example. Let's find GCD (48;36). Let's use the rule.
1. Let's factor the numbers 48 and 36 into prime factors.
48 = 2 · 2 · 2 · 2 · 3
36 = 2 · 2 · 3 · 3
2. From the factors included in the expansion of the number 48, we delete those that are not included in the expansion of the number 36.
48 = 2 · 2 · 2 · 2 · 3
The remaining factors are 2, 2 and 3.
3. Multiply the remaining factors and get 12. This number is the greatest common divisor of the numbers 48 and 36.
GCD (48;36) = 2· 2 · 3 = 12.
The rule for finding the least common multiple (LCM).
To find the least common multiple of several natural numbers, you need to:
1) factor them into prime factors;
2) write down the factors included in the expansion of one of the numbers;
3) add to them the missing factors from the expansions of the remaining numbers;
4) find the product of the resulting factors.
Example. Let's find the LOC (75;60). Let's use the rule.
1. Let's factor the numbers 75 and 60 into prime factors.
75 = 3 · 5 · 5
60 = 2 · 2 · 3 · 3
2. Let’s write down the factors included in the expansion of the number 75: 3, 5, 5.
LCM(75;60) = 3 · 5 · 5 · …
3. Add to them the missing factors from the expansion of the number 60, i.e. 2, 2.
LCM(75;60) = 3 · 5 · 5 · 2 · 2
4. Find the product of the resulting factors
LCM(75;60) = 3 · 5 · 5 · 2 · 2 = 300.
Greatest common divisor and least common multiple are key arithmetic concepts that make working with fractions effortless. LCM and are most often used to find the common denominator of several fractions.
Basic Concepts
The divisor of an integer X is another integer Y by which X is divided without leaving a remainder. For example, the divisor of 4 is 2, and 36 is 4, 6, 9. A multiple of an integer X is a number Y that is divisible by X without a remainder. For example, 3 is a multiple of 15, and 6 is a multiple of 12.
For any pair of numbers we can find their common divisors and multiples. For example, for 6 and 9, the common multiple is 18, and the common divisor is 3. Obviously, pairs can have several divisors and multiples, so the calculations use the largest divisor GCD and the smallest multiple LCM.
The least divisor is meaningless, since for any number it is always one. The greatest multiple is also meaningless, since the sequence of multiples goes to infinity.
Finding gcd
There are many methods for finding the greatest common divisor, the most famous of which are:
- sequential search of divisors, selection of common ones for a pair and search for the largest of them;
- decomposition of numbers into indivisible factors;
- Euclidean algorithm;
- binary algorithm.
Today in educational institutions the most popular methods are decomposition into prime factors and the Euclidean algorithm. The latter, in turn, is used when solving Diophantine equations: searching for GCD is required to check the equation for the possibility of resolution in integers.
Finding the NOC
The least common multiple is also determined by sequential enumeration or factorization into indivisible factors. In addition, it is easy to find the LCM if the greatest divisor has already been determined. For numbers X and Y, the LCM and GCD are related by the following relationship:
LCD(X,Y) = X × Y / GCD(X,Y).
For example, if GCM(15,18) = 3, then LCM(15,18) = 15 × 18 / 3 = 90. The most obvious example of using LCM is to find the common denominator, which is the least common multiple of given fractions.
Coprime numbers
If a pair of numbers has no common divisors, then such a pair is called coprime. The gcd for such pairs is always equal to one, and based on the connection between divisors and multiples, the gcd for coprime pairs is equal to their product. For example, the numbers 25 and 28 are relatively prime, because they have no common divisors, and LCM(25, 28) = 700, which corresponds to their product. Any two indivisible numbers will always be relatively prime.
Common divisor and multiple calculator
Using our calculator you can calculate GCD and LCM for an arbitrary number of numbers to choose from. Tasks on calculating common divisors and multiples are found in 5th and 6th grade arithmetic, but GCD and LCM are key concepts in mathematics and are used in number theory, planimetry and communicative algebra.
Real life examples
Common denominator of fractions
Least common multiple is used when finding the common denominator of several fractions. Let's say in an arithmetic problem you need to sum 5 fractions:
1/8 + 1/9 + 1/12 + 1/15 + 1/18.
To add fractions, the expression must be reduced to a common denominator, which reduces to the problem of finding the LCM. To do this, select 5 numbers in the calculator and enter the values of the denominators in the appropriate cells. The program will calculate the LCM (8, 9, 12, 15, 18) = 360. Now you need to calculate additional factors for each fraction, which are defined as the ratio of the LCM to the denominator. So the additional multipliers would look like:
- 360/8 = 45
- 360/9 = 40
- 360/12 = 30
- 360/15 = 24
- 360/18 = 20.
After this, we multiply all the fractions by the corresponding additional factor and get:
45/360 + 40/360 + 30/360 + 24/360 + 20/360.
We can easily sum such fractions and get the result as 159/360. We reduce the fraction by 3 and see the final answer - 53/120.
Solving linear Diophantine equations
Linear Diophantine equations are expressions of the form ax + by = d. If the ratio d / gcd(a, b) is an integer, then the equation is solvable in integers. Let's check a couple of equations to see if they have an integer solution. First, let's check the equation 150x + 8y = 37. Using a calculator, we find GCD (150.8) = 2. Divide 37/2 = 18.5. The number is not an integer, therefore the equation does not have integer roots.
Let's check the equation 1320x + 1760y = 10120. Use a calculator to find GCD(1320, 1760) = 440. Divide 10120/440 = 23. As a result, we get an integer, therefore, the Diophantine equation is solvable in integer coefficients.
Conclusion
GCD and LCM play a large role in number theory, and the concepts themselves are widely used in a wide variety of areas of mathematics. Use our calculator to calculate the greatest divisors and least multiples of any number of numbers.
Schoolchildren are given a lot of tasks in mathematics. Among them, very often there are problems with the following formulation: there are two meanings. How to find the least common multiple of given numbers? It is necessary to be able to perform such tasks, since the acquired skills are used to work with fractions with different denominators. In this article we will look at how to find the LOC and basic concepts.
Before finding the answer to the question of how to find LCM, you need to define the term multiple. Most often, the formulation of this concept sounds like this: a multiple of a certain value A is a natural number that will be divisible by A without a remainder. So, for 4, the multiples will be 8, 12, 16, 20, and so on, to the required limit.
In this case, the number of divisors for a specific value can be limited, but the multiples are infinitely many. There is also the same value for natural values. This is an indicator that is divided into them without a remainder. Having understood the concept of the smallest value for certain indicators, let's move on to how to find it.
Finding the NOC
The least multiple of two or more exponents is the smallest natural number that is entirely divisible by all specified numbers.
There are several ways to find such a value, consider the following methods:
- If the numbers are small, then write down on a line all those divisible by it. Keep doing this until you find something in common among them. In writing they are denoted by the letter K. For example, for 4 and 3, the smallest multiple is 12.
- If these are large or you need to find a multiple of 3 or more values, then you should use another technique that involves decomposing numbers into prime factors. First, lay out the largest one listed, then all the others. Each of them has its own number of multipliers. As an example, let's decompose 20 (2*2*5) and 50 (5*5*2). For the smaller one, underline the factors and add them to the largest one. The result will be 100, which will be the least common multiple of the above numbers.
- When finding 3 numbers (16, 24 and 36) the principles are the same as for the other two. Let's expand each of them: 16 = 2*2*2*2, 24=2*2*2*3, 36=2*2*3*3. Only two twos from the expansion of the number 16 were not included in the expansion of the largest. We add them and get 144, which is the smallest result for the previously indicated numerical values.
Now we know what the general technique is for finding the smallest value for two, three or more values. However, there are also private methods, helping to search for NOC if the previous ones do not help.
How to find GCD and NOC.
Private methods of finding
As with any mathematical section, there are special cases of finding LCM that help in specific situations:
- if one of the numbers is divisible by the others without a remainder, then the lowest multiple of these numbers is equal to it (the LCM of 60 and 15 is 15);
- relatively prime numbers have no common prime factors. Their smallest value is equal to the product of these numbers. Thus, for the numbers 7 and 8 it will be 56;
- the same rule works for other cases, including special ones, which can be read about in specialized literature. This should also include cases of decomposition of composite numbers, which are the topic of individual articles and even candidate dissertations.
Special cases are less common than standard examples. But thanks to them, you can learn to work with fractions of varying degrees of complexity. This is especially true for fractions, where there are unequal denominators.
Few examples
Let's look at a few examples that will help you understand the principle of finding the least multiple:
- Find the LOC (35; 40). We first decompose 35 = 5*7, then 40 = 5*8. Add 8 to the smallest number and get LOC 280.
- NOC (45; 54). We decompose each of them: 45 = 3*3*5 and 54 = 3*3*6. We add the number 6 to 45. We get an LCM equal to 270.
- Well, the last example. There are 5 and 4. There are no prime multiples of them, so the least common multiple in this case will be their product, which is equal to 20.
Thanks to the examples, you can understand how the NOC is located, what the nuances are and what the meaning of such manipulations is.
Finding NOC is much easier than it might initially seem. To do this, both simple expansion and multiplication of simple values by each other are used. The ability to work with this section of mathematics helps with further study of mathematical topics, especially fractions of varying degrees of complexity.
Don’t forget to periodically solve examples using different methods; this develops your logical apparatus and allows you to remember numerous terms. Learn how to find such an exponent and you will be able to do well in the rest of the math sections. Happy learning math!
Video
This video will help you understand and remember how to find the least common multiple.
To learn how to find the greatest common divisor of two or more numbers, you need to understand what natural, prime and complex numbers are.
A natural number is any number that is used to count whole objects.
If a natural number can only be divided into itself and one, then it is called prime.
All natural numbers can be divided by themselves and one, but the only even prime number is 2, all others can be divided by two. Therefore, only odd numbers can be prime.
There are quite a lot of prime numbers; there is no complete list of them. To find GCD it is convenient to use special tables with such numbers.
Most natural numbers can be divided not only by one, themselves, but also by other numbers. So, for example, the number 15 can be divided by 3 and 5. All of them are called divisors of the number 15.
Thus, the divisor of any A is the number by which it can be divided without a remainder. If a number has more than two natural factors, it is called composite.
The number 30 can have divisors such as 1, 3, 5, 6, 15, 30.
You will notice that 15 and 30 have the same divisors 1, 3, 5, 15. The greatest common divisor of these two numbers is 15.
Thus, the common divisor of the numbers A and B is the number by which they can be divided entirely. The largest can be considered the maximum total number by which they can be divided.
To solve problems, the following abbreviated inscription is used:
GCD (A; B).
For example, gcd (15; 30) = 30.
To write down all the divisors of a natural number, use the notation:
D (15) = (1, 3, 5, 15)
GCD (9; 15) = 1
In this example, the natural numbers have only one common divisor. They are called relatively prime, so unity is their greatest common divisor.
How to find the greatest common divisor of numbers
To find the gcd of several numbers, you need:
Find all divisors of each natural number separately, that is, factor them into factors (prime numbers);
Select all identical factors of given numbers;
Multiply them together.
For example, to calculate the greatest common divisor of the numbers 30 and 56, you would write the following:
To avoid confusion, it is convenient to write down factors using vertical columns. On the left side of the line you need to place the dividend, and on the right side - the divisor. Under the dividend, you should indicate the resulting quotient.
So, in the right column there will be all the factors needed for the solution.
Identical divisors (found factors) can be underlined for convenience. They should be rewritten and multiplied and the greatest common divisor written down.
GCD (30; 56) = 2 * 5 = 10
This is how easy it really is to find the greatest common divisor of numbers. If you practice a little, you can do this almost automatically.
