Definition. The largest natural number that can be divided without a remainder by numbers a and b is called greatest common divisor (GCD) these numbers.
Let's find the largest common divisor numbers 24 and 35.
The divisors of 24 are the numbers 1, 2, 3, 4, 6, 8, 12, 24, and the divisors of 35 are 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 prime.
Definition. Natural numbers are called mutually prime, 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 expansion of the first of these numbers, we cross out those that are not included in the expansion of the second number (i.e., two twos).
The factors remaining are 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 divisor
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.
If all given numbers are divisible by one of them, then this number is greatest common divisor given numbers.
For example, the greatest common divisor of the numbers 15, 45, 75 and 180 is the number 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 the smallest natural number that is a multiple of both a and b. The least common multiple (LCM) of the numbers 75 and 60 can be found without writing down the multiples of these numbers in a row. To do this, let's decompose 75 and 60 into prime factors: 75 = 3 * 5 * 5, and 60 = 2 * 2 * 3 * 5.
Let's write down the factors included in the expansion of the first of these numbers, and add to them the missing factors 2 and 2 from the expansion of the second number (i.e., we 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 the numbers 75 and 60.
They also find the least common multiple of three or more numbers.
To find least common multiple several natural numbers, you need:
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.
Note that if one of these numbers is divisible by all other numbers, then this number is the least common multiple of these numbers.
For example, the least common multiple of the numbers 12, 15, 20, and 60 is 60 because it is divisible by all of those numbers.
Pythagoras (VI century BC) and his students studied the question of the divisibility of numbers. Number, equal to the sum They called all its divisors (without the number itself) 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 only knew the first three perfect numbers. The fourth - 8128 - became known in the 1st century. n. e. The fifth - 33,550,336 - was found in the 15th century. By 1983, 27 perfect numbers were already known. But scientists still don’t know whether there are odd perfect numbers or whether there is a largest perfect number.
The interest of ancient mathematicians in prime numbers stems from the fact that any number is either prime or can be represented as a product prime numbers, i.e. prime numbers are like bricks from which the rest of the natural numbers are built.
You probably noticed that prime numbers in the 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 prime numbers are. The question arises: is there a last (largest) prime number? The ancient Greek mathematician Euclid (3rd century BC), in his book “Elements”, which was the main textbook of mathematics for two thousand years, proved that there are infinitely many prime numbers, i.e. behind each prime number there is an even greater prime number.
To find prime numbers, another Greek mathematician of the same time, Eratosthenes, came up with this method. He wrote down all the numbers from 1 to some number, and then crossed out one, which is neither a prime nor a composite number, then crossed out through one all the numbers coming after 2 (numbers that are multiples of 2, i.e. 4, 6 , 8, etc.). The first remaining number after 2 was 3. Then, after two, all numbers coming after 3 (numbers that are multiples of 3, i.e. 6, 9, 12, etc.) were crossed out. in the end only the prime numbers remained uncrossed.
Finding the greatest common divisor of three or more numbers can be reduced to sequentially finding the gcd of two numbers. We mentioned this when studying the properties of GCD. There we formulated and proved the theorem: the greatest common divisor of several numbers a 1 , a 2 , …, a k equal to the number dk, which is found by sequential calculation GCD(a 1 , a 2)=d 2, GCD(d 2 , a 3)=d 3, GCD(d 3 , a 4)=d 4, …,GCD(d k-1 , a k)=d k.
Let's see what the process of finding the gcd of several numbers looks like by looking at the solution to the example.
Example.
Find the greatest common divisor of four numbers 78 , 294 , 570 And 36 .
Solution.
In this example a 1 =78, a 2 =294, a 3 =570, a 4 =36.
First, using the Euclidean algorithm, we determine the greatest common divisor d 2 first two numbers 78 And 294 . When dividing we get the equalities 294=78 3+60; 78=60 1+18;60=18·3+6 And 18=6·3. Thus, d 2 =GCD(78, 294)=6.
Now let's calculate d 3 =GCD(d 2, a 3)=GCD(6, 570). Let's use the Euclidean algorithm again: 570=6·95, hence, d 3 =GCD(6, 570)=6.
It remains to calculate d 4 =GCD(d 3, a 4)=GCD(6, 36). Because 36 divided by 6 , That d 4 =GCD(6, 36)=6.
Thus, the greatest common divisor of the four given numbers is d 4 =6, that is, GCD(78, 294, 570, 36)=6.
Answer:
GCD(78, 294, 570, 36)=6.
Factoring numbers into prime factors also allows you to calculate the gcd of three or more numbers. In this case, the greatest common divisor is found as the product of all common prime factors of the given numbers.
Example.
Calculate the gcd of the numbers from the previous example using their prime factorizations.
Solution.
Let's break down the numbers 78 , 294 , 570 And 36 by prime factors, we get 78=2·3·13,294=2·3·7·7, 570=2 3 5 19, 36=2·2·3·3. The common prime factors of all given four numbers are the numbers 2 And 3 . Hence, GCD(78, 294, 570, 36)=2·3=6.
Answer:
GCD(78, 294, 570, 36)=6.
Top of page
Finding gcd of negative numbers
If one, several, or all of the numbers whose greatest divisor is to be found are negative numbers, then their gcd is equal to the greatest common divisor of the moduli of these numbers. This is due to the fact that opposite numbers a And −a have the same divisors, as we discussed when studying the properties of divisibility.
Example.
Find the gcd of negative integers −231 And −140 .
Solution.
The absolute value of a number −231 equals 231 , and the modulus of the number −140 equals 140 , And GCD(−231, −140)=GCD(231, 140). The Euclidean algorithm gives us the following equalities: 231=140 1+91; 140=91 1+49; 91=49 1+42; 49=42 1+7 And 42=7 6. Hence, GCD(231, 140)=7. Then the desired greatest common divisor of negative numbers is −231 And −140 equals 7 .
Answer:
GCD(−231, −140)=7.
Example.
Determine the gcd of three numbers −585 , 81 And −189 .
Solution.
When finding the greatest common divisor, negative numbers can be replaced by their absolute values, that is, GCD(−585, 81, −189)=GCD(585, 81, 189). Number expansions 585 , 81 And 189 into prime factors have the form 585=3·3·5·13, 81=3·3·3·3 And 189=3·3·3·7. The common prime factors of these three numbers are 3 And 3 . Then GCD(585, 81, 189)=3·3=9, hence, GCD(−585, 81, −189)=9.
Answer:
GCD(−585, 81, −189)=9.
35. Roots of a polynomial. Bezout's theorem. (33 and above)
36. Multiple roots, criterion for multiplicity of roots.
Greatest common divisor and least common multiple are key arithmetic concepts that allow you to operate effortlessly ordinary fractions. 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 at educational institutions The most popular are the methods of prime factorization 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 search or decomposition 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 multiple fractions. Let in 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 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 big 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.
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 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.
Common divisor of two given numbers a And b- this is the number by which both given numbers are divided without remainder a And b. Common divisor of several numbers (GCD) is a number that serves as a divisor for each of them.
Briefly greatest common divisor of numbers a And b write it like this:
Example: GCD (12; 36) = 12.
Divisors of numbers in the solution record are denoted by the capital letter “D”.
Example:
GCD (7; 9) = 1
The numbers 7 and 9 have only one common divisor - the number 1. Such numbers are called mutually primechi slami.
Coprime numbers- these are natural numbers that have only one common divisor - the number 1. Their gcd is 1.
Greatest common divisor (GCD), properties.
- Basic property: greatest common divisor m And n is divisible by any common divisor of these numbers. Example: For numbers 12 and 18, the greatest common divisor is 6; it is divided by all common divisors of these numbers: 1, 2, 3, 6.
- Corollary 1: set of common divisors m And n coincides with the set of GCD divisors( m, n).
- Corollary 2: set of common multiples m And n coincides with the set of multiple LCMs ( m, n).
This means, in particular, that to reduce a fraction to an irreducible form, you need to divide its numerator and denominator by their gcd.
- Greatest common divisor of numbers m And n can be defined as the smallest positive element of the set of all their linear combinations:
and therefore represent it as a linear combination of numbers m And n:
This ratio is called Bezout's relation, and the coefficients u And v — Bezout coefficients. Bezout coefficients are calculated efficiently by the extended Euclidean algorithm. This statement generalizes to sets of natural numbers - its meaning is that the subgroup of the group generated by the set is cyclic and generated by one element: GCD ( a 1 , a 2 , … , a n).
Calculate the greatest common divisor (GCD).
Efficient ways to calculate the gcd of two numbers are Euclidean algorithm And binaryalgorithm. In addition, the value of gcd ( m,n) can be easily calculated if the canonical expansion of numbers is known m And n into prime factors:
where are distinct prime numbers, and and are non-negative integers (they can be zeros if the corresponding prime is not in the expansion). Then GCD ( m,n) and NOC ( m,n) are expressed by the formulas:
If there are more than two numbers: , their gcd is found using the following algorithm:
- this is the desired GCD.
Also, in order to find greatest common divisor, you can factor each of the given numbers into prime factors. Then write down separately only those factors that are included in all given numbers. Then we multiply the written numbers together - the result of the multiplication is the greatest common divisor .
Let's look at the calculation of the greatest common divisor step by step:
1. Decompose the divisors of numbers into prime factors:
It is convenient to write calculations using a vertical bar. To the left of the line we first write down the dividend, to the right - the divisor. Next, in the left column we write down the values of the quotients. Let's explain it right away with an example. Let's factor the numbers 28 and 64 into prime factors.
2. We emphasize the same prime factors in both numbers:
28 = 2 . 2 . 7
64 = 2 . 2 . 2 . 2 . 2 . 2
3. Find the product of identical prime factors and write down the answer:
gcd (28; 64) = 2. 2 = 4
Answer: GCD (28; 64) = 4
You can formalize the location of the GCD in two ways: in a column (as done above) or “in a row”.
The first way to write GCD:
Find gcd 48 and 36.
GCD (48; 36) = 2. 2. 3 = 12
The second way to write GCD:
Now let's write down the solution to the GCD search in a line. Find gcd 10 and 15.
D (10) = (1, 2, 5, 10)
D (15) = (1, 3, 5, 15)
D (10, 15) = (1, 5)
To understand how to calculate the LCM, you must first determine the meaning of the term “multiple”.
A multiple of A is a natural number that is divisible by A without a remainder. Thus, numbers that are multiples of 5 can be considered 15, 20, 25, and so on.
There can be divisors of a specific number limited quantity, but there are an infinite number of multiples.
A common multiple of natural numbers is a number that is divisible by them without leaving 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 divisible by all these numbers.
To find the LOC, you can use several methods.
For small numbers, it is convenient to write down all the multiples of these numbers on a line until you find something common among them. Multiples are denoted by the 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, ...)
Thus, you can see that the least common multiple of the numbers 4 and 6 is the number 24. This notation is done 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 method of calculating the LCM.
To complete the task, you need to factor the given numbers into prime factors.
First you need to write down the decomposition of the largest number on a line, and below it - the rest.
The decomposition of each number may contain 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, it is necessary to emphasize the factors that are absent in the expansion of the first one. large number, and then add them to it. In the example presented, a two is missing.
Now you can calculate the least common multiple of 20 and 50.
LCM(20, 50) = 2 * 5 * 5 * 2 = 100
So, the product of prime factors more and the factors of the second number that were not included in the expansion of the larger number will be the least common multiple.
To find the LCM of three or more numbers, you should factor them all 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 twos from the expansion of sixteen were not included in the factorization of a larger number (one is in the expansion of twenty-four).
Thus, they need to be added to the expansion 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, the LCM of twelve and twenty-four is twenty-four.
If it is necessary to find the least common multiple of coprime numbers that do not have identical divisors, then their LCM will be equal to their product.
For example, LCM (10, 11) = 110.