The greatest common divisor and the least common multiple are key arithmetic concepts that allow you to easily operate with 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 divisible without a remainder. For example, the divisor of 4 is 2, and 36 is 4, 6, 9. A multiple of the 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 largest divisor of the GCD and the smallest multiple of the LCM are used in the calculations.
The smallest divisor does not make sense, since for any number it is always one. The largest multiple is also meaningless, since the sequence of multiples tends to infinity.
Finding GCD
There are many methods for finding the greatest common divisor, the most famous of which are:
- sequential enumeration of divisors, selection of common ones for a pair and search for the largest of them;
- decomposition of numbers into indivisible factors;
- Euclid's algorithm;
- binary algorithm.
Today at educational institutions the most popular are prime factorization methods and Euclid's algorithm. The latter, in turn, is used in solving Diophantine equations: the search for GCD is required to check the equation for the possibility of resolving it in integers.
Finding the NOC
The least common multiple is also exactly determined by iterative enumeration or factorization into indivisible factors. In addition, it is easy to find the LCM if the largest divisor has already been determined. For numbers X and Y, LCM and GCD are related by the following relation:
LCM(X,Y) = X × Y / GCM(X,Y).
For example, if gcd(15,18) = 3, then LCM(15,18) = 15 × 18 / 3 = 90. The most obvious use of LCM is to find the common denominator, which is the least common multiple of the given fractions.
Coprime numbers
If a pair of numbers has no common divisors, then such a pair is called coprime. The GCM for such pairs is always equal to one, and based on the connection of divisors and multiples, the GCM for coprime is equal to their product. For example, the numbers 25 and 28 are coprime, because they have no common divisors, and LCM(25, 28) = 700, which corresponds to their product. Any two indivisible numbers will always be coprime.
Common Divisor and Multiple Calculator
With our calculator you can calculate GCD and LCM for any number of numbers to choose from. Tasks for calculating common divisors and multiples are found in arithmetic of grades 5, 6, however, GCD and LCM - key concepts mathematics and are used in number theory, planimetry and communicative algebra.
Real life examples
Common denominator of fractions
The least common multiple is used when finding the common denominator of several fractions. Suppose in an arithmetic problem it is required 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 denominator values in the appropriate cells. The program will calculate LCM (8, 9, 12, 15, 18) = 360. Now you need to calculate additional factors for each fraction, which are defined as the ratio of LCM to the denominator. So the extra multipliers would look like:
- 360/8 = 45
- 360/9 = 40
- 360/12 = 30
- 360/15 = 24
- 360/18 = 20.
After that, 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 add such fractions and get the result in the form of 159/360. We reduce the fraction by 3 and see the final answer - 53/120.
Solution of 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 for the possibility of an integer solution. First, 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 an important role in number theory, and the concepts themselves are widely used in various areas of mathematics. Use our calculator to calculate the largest divisors and smallest multiples of any number of numbers.
Let's solve the problem. We have two types of cookies. Some are chocolate and some are plain. There are 48 chocolate pieces, and simple 36. It is necessary to make the maximum possible number of gifts from these cookies, and all of them must be used.
First, let's write down all the divisors of each of these two numbers, since both of these numbers must be divisible by the number of gifts.
We get
- 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
- 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.
Let's find among the divisors the common ones that both the first and the second number have.
Common divisors will be: 1, 2, 3, 4, 6, 12.
The greatest common divisor of all is 12. This number is called the greatest common divisor of 36 and 48.
Based on the result, we can conclude that 12 gifts can be made from all cookies. One such gift will contain 4 chocolate cookies and 3 regular cookies.
Finding the Greatest Common Divisor
- Greatest natural number, by which two numbers a and b are divisible without a remainder, is called the greatest common divisor of these numbers.
Sometimes the abbreviation GCD is used to abbreviate the entry.
Some pairs of numbers have one as their greatest common divisor. Such numbers are called coprime numbers. For example, numbers 24 and 35. Have GCD =1.
How to find the greatest common divisor
In order to find the greatest common divisor, it is not necessary to write out all the divisors of these numbers.
You can do otherwise. First, factor both numbers into prime factors.
- 48 = 2*2*2*2*3,
- 36 = 2*2*3*3.
Now, from the factors that are included in the expansion of the first number, we delete all those that are not included in the expansion of the second number. In our case, these are two deuces.
- 48 = 2*2*2*2*3 ,
- 36 = 2*2*3 *3.
The factors 2, 2 and 3 remain. Their product is 12. This number will be the greatest common divisor of the numbers 48 and 36.
This rule can be extended to the case of three, four, and so on. numbers.
General scheme for finding the greatest common divisor
- 1. Decompose numbers into prime factors.
- 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. Calculate the product of the remaining factors.
Finding the greatest common divisor of three or more numbers can be reduced to successively 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 is equal to the number dk, which is found in the 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 how the process of finding the GCD of several numbers looks like by considering the solution of the example.
Example.
Find the greatest common divisor of four numbers 78 , 294 , 570 and 36 .
Solution.
In this example a 1 =78, a2=294, a 3 \u003d 570, a4=36.
First, using the Euclid algorithm, we determine the greatest common divisor d2 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. In this way, d 2 \u003d GCD (78, 294) \u003d 6.
Now let's calculate d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). Let's use Euclid's algorithm again: 570=6 95, hence, d 3 \u003d GCD (6, 570) \u003d 6.
It remains to calculate d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). Because 36 divided by 6 , then d 4 \u003d GCD (6, 36) \u003d 6.
So the greatest common divisor of the four given numbers is d4=6, that is, gcd(78, 294, 570, 36)=6.
Answer:
gcd(78, 294, 570, 36)=6.
Decomposing 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 decompose the numbers 78 , 294 , 570 and 36 into 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 the 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 modules of these numbers. This is because opposite numbers a and -a have the same divisors, which 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). Euclid's 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 −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 are, respectively, of 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 up)
36. Multiple roots, criterion of multiplicity of the root.
This article is devoted to such a question as finding the greatest common divisor. First, we will explain what it is and give some examples, introduce the definitions of the greatest common divisor of 2, 3 or more numbers, after which we will dwell on the general properties of this concept and prove them.
Yandex.RTB R-A-339285-1
What are common divisors
To understand what the greatest common divisor is, we first formulate what a common divisor is for integers.
In the article on multiples and divisors, we said that an integer always has multiple divisors. Here we are interested in the divisors of a certain number of integers at once, especially common (identical) for all. Let us write down the main definition.
Definition 1
The common divisor of several integers will be a number that can be a divisor of each number from the specified set.
Example 1
Here are examples of such a divisor: the triple will be a common divisor for the numbers - 12 and 9, since the equalities 9 = 3 · 3 and − 12 = 3 · (− 4) are true. The numbers 3 and - 12 have other common divisors, such as 1 , - 1 and - 3 . Let's take another example. The four integers 3 , − 11 , − 8 and 19 will have two common divisors: 1 and - 1 .
Knowing the properties of divisibility, we can say that any integer can be divided by one and minus one, which means that any set of integers will already have at least two common divisors.
Also note that if we have a common divisor for several numbers b, then the same numbers can be divided by the opposite number, that is, by - b. In principle, we can only take positive divisors, then all common divisors will also be greater than 0 . This approach can also be used, but negative numbers should not be completely ignored.
What is the greatest common divisor (gcd)
According to the properties of divisibility, if b is a divisor of an integer a that is not equal to 0, then the modulus of b cannot be greater than the modulus of a, hence any number not equal to 0 has a finite number of divisors. This means that the number of common divisors of several integers, at least one of which differs from zero, will also be finite, and from their entire set we can always select the most big number(Earlier we have already talked about the concept of the largest and smallest integer, we advise you to repeat this material).
In further reasoning, we will assume that at least one of the set of numbers for which you need to find the greatest common divisor will be different from 0 . If they are all equal to 0 , then their divisor can be any integer, and since there are infinitely many of them, we cannot choose the largest. In other words, it is impossible to find the greatest common divisor for the set of numbers equal to 0 .
We pass to the formulation of the main definition.
Definition 2
The greatest common divisor of multiple numbers is the largest integer that divides all those numbers.
In writing, the greatest common divisor is most often denoted by the abbreviation GCD. For two numbers, it can be written as gcd (a, b) .
Example 2
What is an example of GCD for two integers? For example, for 6 and - 15 it would be 3 . Let's substantiate this. First, we write down all the divisors of six: ± 6, ± 3, ± 1, and then all the divisors of fifteen: ± 15, ± 5, ± 3 and ± 1. After that, we choose common ones: these are − 3 , − 1 , 1 and 3 . Of these, you need to choose the largest number. This will be 3 .
For three or more numbers, the definition of the greatest common divisor will be much the same.
Definition 3
The greatest common divisor of three or more numbers is the largest integer that divides all those numbers at the same time.
For numbers a 1 , a 2 , … , a n the divisor is conveniently denoted as GCD (a 1 , a 2 , … , a n) . The divisor value itself is written as GCD (a 1 , a 2 , … , a n) = b .
Example 3
Here are examples of the greatest common divisor of several integers: 12 , - 8 , 52 , 16 . It will be equal to four, which means we can write that gcd (12, - 8, 52, 16) = 4.
You can check the correctness of this statement by writing down all the divisors of these numbers and then choosing the largest of them.
In practice, there are often cases when the greatest common divisor is equal to one of the numbers. This happens when all other numbers can be divided by a given number (in the first paragraph of the article we gave the proof of this statement).
Example 4
So, the greatest common divisor of the numbers 60, 15 and - 45 is 15, since fifteen is divisible not only by 60 and - 45, but also by itself, and there is no greater divisor for all these numbers.
Coprime numbers are a special case. They are integers with a greatest common divisor of 1 .
Main properties of GCD and Euclid's algorithm
The greatest common divisor has some characteristic properties. We formulate them in the form of theorems and prove each of them.
Note that these properties are formulated for integers greater than zero, and we consider only positive divisors.
Definition 4
The numbers a and b have the greatest common divisor equal to gcd for b and a , i.e. gcd (a , b) = gcd (b , a) . Changing the places of numbers does not affect the final result.
This property follows from the very definition of GCD and does not need proof.
Definition 5
If the number a can be divided by the number b, then the set of common divisors of these two numbers will be similar to the set of divisors of the number b, that is, gcd (a, b) = b.
Let's prove this statement.
Proof 1
If the numbers a and b have common divisors, then any of them can be divided by them. At the same time, if a is a multiple of b, then any divisor of b will also be a divisor of a , since divisibility has such a property as transitivity. Hence, any divisor b will be common for the numbers a and b. This proves that if we can divide a by b , then the set of all divisors of both numbers coincides with the set of divisors of one number b . And since the greatest divisor of any number is the number itself, then the greatest common divisor of the numbers a and b will also be equal to b, i.e. gcd(a, b) = b. If a = b , then gcd (a , b) = gcd (a , a) = gcd (b , b) = a = b , e.g. gcd (132 , 132) = 132 .
Using this property, we can find the greatest common divisor of two numbers if one of them can be divided by the other. Such a divisor is equal to one of these two numbers by which the second number can be divided. For example, gcd (8, 24) = 8, because 24 is a multiple of eight.
Definition 6 Proof 2
Let's try to prove this property. We initially have the equality a = b q + c , and any common divisor of a and b will also divide c , which is explained by the corresponding divisibility property. Therefore, any common divisor of b and c will divide a . This means that the set of common divisors a and b will coincide with the set of divisors b and c, including the largest of them, which means that the equality gcd (a, b) = gcd (b, c) is true.
Definition 7
The following property is called the Euclid algorithm. With it, you can calculate the greatest common divisor of two numbers, as well as prove other properties of GCD.
Before formulating the property, we advise you to repeat the theorem that we proved in the article on division with a remainder. According to it, the divisible number a can be represented as b q + r, and here b is a divisor, q is some integer (it is also called an incomplete quotient), and r is a remainder that satisfies the condition 0 ≤ r ≤ b.
Let's say we have two integers greater than 0 for which the following equalities will be true:
a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
These equalities end when r k + 1 becomes equal to 0 . This will happen for sure, since the sequence b > r 1 > r 2 > r 3 , … is a series of decreasing integers, which can include only a finite number of them. Hence, r k is the greatest common divisor of a and b , that is, r k = gcd (a , b) .
First of all, we need to prove that r k is a common divisor of the numbers a and b, and after that, that r k is not just a divisor, but the greatest common divisor of the two given numbers.
Let's look at the list of equalities above, from bottom to top. According to the last equality,
r k − 1 can be divided by r k . Based on this fact, as well as the previous proved property of the greatest common divisor, it can be argued that r k − 2 can be divided by r k , since
r k − 1 is divisible by r k and r k is divisible by r k .
The third equality from the bottom allows us to conclude that r k − 3 can be divided by r k , and so on. The second from the bottom is that b is divisible by r k , and the first is that a is divisible by r k . From all this we conclude that r k is a common divisor of a and b .
Now let's prove that r k = gcd (a , b) . What do I need to do? Show that any common divisor of a and b will divide r k . Let's denote it r 0 .
Let's look at the same list of equalities, but from top to bottom. Based on the previous property, we can conclude that r 1 is divisible by r 0 , which means that according to the second equality, r 2 is divisible by r 0 . We go down through all the equalities and from the last one we conclude that r k is divisible by r 0 . Therefore, r k = gcd (a , b) .
Having considered this property, we conclude that the set of common divisors of a and b is similar to the set of divisors of the gcd of these numbers. This statement, which is a consequence of Euclid's algorithm, will allow us to calculate all the common divisors of two given numbers.
Let's move on to other properties.
Definition 8
If a and b are integers not equal to 0, then there must be two other integers u 0 and v 0 for which the equality gcd (a , b) = a u 0 + b v 0 will be valid.
The equality given in the property statement is a linear representation of the greatest common divisor of a and b . It is called the Bezout ratio, and the numbers u 0 and v 0 are called the Bezout coefficients.
Proof 3
Let's prove this property. We write down the sequence of equalities according to the Euclid algorithm:
a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
The first equality tells us that r 1 = a − b · q 1 . Denote 1 = s 1 and − q 1 = t 1 and rewrite this equality as r 1 = s 1 · a + t 1 · b . Here the numbers s 1 and t 1 will be integers. The second equality allows us to conclude that r 2 = b − r 1 q 2 = b − (s 1 a + t 1 b) q 2 = − s 1 q 2 a + (1 − t 1 q 2) b . Denote − s 1 q 2 = s 2 and 1 − t 1 q 2 = t 2 and rewrite the equality as r 2 = s 2 a + t 2 b , where s 2 and t 2 will also be integers. This is because the sum of integers, their product and difference are also integers. In exactly the same way, we obtain from the third equality r 3 = s 3 · a + t 3 · b , from the following r 4 = s 4 · a + t 4 · b, etc. Finally, we conclude that r k = s k a + t k b for integers s k and t k . Since r k \u003d GCD (a, b) , we denote s k \u003d u 0 and t k \u003d v 0. As a result, we can get a linear representation of GCD in the required form: GCD (a, b) \u003d a u 0 + b v 0.
Definition 9
gcd (m a, m b) = m gcd (a, b) for any natural value m .
Proof 4
This property can be justified as follows. Multiply by the number m both sides of each equality in the Euclid algorithm and we get that gcd (m a , m b) = m r k , and r k is gcd (a , b) . Hence, gcd (m a, m b) = m gcd (a, b) . It is this property of the greatest common divisor that is used when finding the GCD by the factorization method.
Definition 10
If numbers a and b have a common divisor p , then gcd (a: p , b: p) = gcd (a , b) : p . In the case when p = gcd (a , b) we get gcd (a: gcd (a , b) , b: gcd (a , b) = 1, therefore, the numbers a: gcd (a , b) and b: gcd (a , b) are coprime.
Since a = p (a: p) and b = p (b: p) , then, based on the previous property, we can create equalities of the form gcd (a , b) = gcd (p (a: p) , p (b: p)) = p GCD (a: p, b: p) , among which there will be a proof given property. We use this assertion when we give common fractions to irreducible form.
Definition 11
The greatest common divisor a 1 , a 2 , ... , ak will be the number dk , which can be found by successively calculating gcd (a 1 , a 2) = d 2 , gcd (d 2 , a 3) = d 3 , gcd (d 3 , a 4) = d 4 , … , gcd (dk - 1 , ak) = dk .
This property is useful for finding the greatest common divisor of three or more numbers. With it, you can reduce this action to operations with two numbers. Its basis is a corollary from the Euclidean algorithm: if the set of common divisors a 1 , a 2 and a 3 coincides with the set d 2 and a 3 , then it also coincides with the divisors d 3 . The divisors of the numbers a 1 , a 2 , a 3 and a 4 will match the divisors of d 3 , which means they will also match the divisors of d 4 , and so on. In the end, we get that the common divisors of the numbers a 1 , a 2 , … , a k will coincide with the divisors d k , and since the number itself will be the greatest divisor of the number d k , then gcd (a 1 , a 2 , … , a k) = d k .
That's all we would like to talk about the properties of the greatest common divisor.
If you notice a mistake in the text, please highlight it and press Ctrl+Enter
This article is about finding the greatest common divisor (gcd) two or more numbers. First, consider the Euclid algorithm, it allows you to find the GCD of two numbers. After that, we will dwell on a method that allows us to calculate the GCD of numbers as a product of their common prime factors. Next, we will deal with finding the greatest common divisor of three or more numbers, and also give examples of calculating the GCD of negative numbers.
Page navigation.
Euclid's algorithm for finding GCD
Note that if we had turned to the prime number table from the very beginning, we would have found out that the numbers 661 and 113 are prime, from which we could immediately say that their greatest common divisor is 1.
Answer:
gcd(661, 113)=1 .
Finding GCD by Factoring Numbers into Prime Factors
Consider another way to find the GCD. The greatest common divisor can be found by factoring numbers into prime factors. Let's formulate the rule: The gcd of two positive integers a and b is equal to the product of all common prime factors in the factorizations of a and b into prime factors.
Let us give an example to explain the rule for finding the GCD. Let us know the expansions of the numbers 220 and 600 into prime factors, they have the form 220=2 2 5 11 and 600=2 2 2 3 5 5 . Common prime factors involved in the expansion of the numbers 220 and 600 are 2 , 2 and 5 . Therefore gcd(220, 600)=2 2 5=20 .
Thus, if we decompose the numbers a and b into prime factors and find the product of all their common factors, then this will find the greatest common divisor of the numbers a and b.
Consider an example of finding the GCD according to the announced rule.
Example.
Find the greatest common divisor of 72 and 96.
Solution.
Let's factorize the numbers 72 and 96: 
That is, 72=2 2 2 3 3 and 96=2 2 2 2 2 3 . Common prime factors are 2 , 2 , 2 and 3 . So gcd(72, 96)=2 2 2 3=24 .
Answer:
gcd(72, 96)=24 .
In conclusion of this section, we note that the validity of the above rule for finding the gcd follows from the property of the greatest common divisor, which states that GCD(m a 1 , m b 1)=m GCD(a 1 , b 1), where m is any positive integer.
Finding GCD of three or more numbers
Finding the greatest common divisor of three or more numbers can be reduced to successively 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 , …, ak is equal to the number dk , which is found in the sequential calculation of 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 , ak)=dk .
Let's see how the process of finding the GCD of several numbers looks like by considering the solution of the example.
Example.
Find the greatest common divisor of the 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 Euclid algorithm, we determine the greatest common divisor d 2 of the 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 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). Again we apply the Euclid algorithm: 570=6·95 , therefore, d 3 =GCD(6, 570)=6 .
It remains to calculate d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). Since 36 is divisible by 6, then d 4 \u003d GCD (6, 36) \u003d 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 .
Decomposing 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.
We decompose the numbers 78 , 294 , 570 and 36 into 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.
History of sky lanterns
Job description: concept, purpose, structure, procedure for compiling and formalizing Purpose and content of job descriptions for managers
Interview questions What job are you going to work on?
What to do if the boss criticizes all the time If the boss does nothing
How to understand: will the kitten be fluffy?