Proof of the Euclidean algorithm for finding nodes. Euclid's algorithm for finding GCD (greatest common divisor). Application of the Euclid algorithm
Euclid's algorithm for finding GCD (greatest common divisor)
Given two non-negative integers and . It is required to find their greatest common divisor, i.e. the largest number that is a divisor of both and , and . On the English language"greatest common divisor" is spelled "greatest common divisor", and its common notation is :
(here "" denotes divisibility, i.e. "" stands for "divides")
When one of the numbers is equal to zero and the other is non-zero, their greatest common divisor, by definition, will be this second number. When both numbers are zero, the result is undefined (any infinitely large number will do), we put in this case the greatest common divisor zero. Therefore, we can talk about such a rule: if one of the numbers is equal to zero, then their greatest common divisor is equal to the second number.
Euclid's algorithm, discussed below, solves the problem of finding the greatest common divisor of two numbers and for .
This algorithm was first described in Euclid's Elements (circa 300 BC), although it is quite possible that this algorithm has an earlier origin.
Algorithm
The algorithm itself is extremely simple and is described by the following formula:
Implementation
int gcd (int a, int b) ( if (b == 0 ) return a; else return gcd (b, a % b) ; )Using the C++ ternary conditional operator, the algorithm can be written even shorter:
int gcd (int a, int b) ( return b ? gcd (b, a % b) : a; )Finally, we give a non-recursive form of the algorithm:
int gcd (int a, int b) ( while (b) ( a % = b; swap (a, b) ; ) return a; )Correctness proof
First, note that with each iteration of the Euclidean algorithm, its second argument is strictly decreasing, therefore, since it is non-negative, then the Euclidean algorithm always ends.
For correctness proofs we need to show that for any >.
Let us show that the value on the left side of the equality is divisible by the real one on the right, and the value on the right is divisible by the value on the left. Obviously, this will mean that the left and right parts are the same, which will prove the correctness of Euclid's algorithm.
Denote . Then, by definition, and .
But then it follows:
So, remembering the statement , we get the system:
Let us now use the following simple fact: if for some three numbers is satisfied: and , then it is executed and: . In our situation, we get:
Or, substituting its definition as , we get:
So, we have done half of the proof: we have shown that the left side divides the right one. The second half of the proof is done in a similar way.
Working hours
The running time of the algorithm is estimated Lame's theorem, which establishes a surprising connection between the Euclid algorithm and the Fibonacci sequence:
If > and for some , then Euclid's algorithm will make at most recursive calls.
1.1 Application of the Euclid algorithm
Like all good work, Euclid's algorithm does much more than it was originally expected to give. From looking at it, it is clear, for example, that the set of divisors a and b coincides with the set of divisors (a, b). He also gives practical way finding numbers u and v from Z (or, if you like, from the theorem of item 2) such that
rn = au + bv = (a, b).
Indeed, from the chain of equalities we have:
r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n =...
(we go along the chain of equalities from bottom to top, expressing the remainder from each next equality and substituting it into the expression that has already been obtained by this moment)
Au + bv = (a, b).
Undoubtedly, the procedure described by Euclid for determining the common measure of two quantities in relation to numbers (and the common measure of two natural numbers, is obviously their greatest common divisor) was invented long before Euclid. In the same way, GCD was found by ancient Chinese mathematicians. And only the fact that this procedure became known in the Renaissance precisely from the "Beginnings" gave it the name "Euclid's algorithm"
Most likely, it arose from the commercial practice of ancient merchants when they had to compare various ratios of whole numbers. How, for example, to compare the ratios of the numbers 3703700 and 1234567 and the numbers 22962965 and 7654321? It was quite natural to try to find out how many times a smaller number fits into a larger one. It is easy to check that 3703700 = 2 1234567 + 1234566 and 22962965 = 3 7654321 + 2. It is now clear that the ratio of 3703700 to 1234567 is less than the ratio of 22962965 to 7654321. Thus, what we now write as
2,99999919 <= 3, 000000261,
Ancient calculators explained in a long phrase.
If we had to compare closer ratios of numbers, for example, and, then the calculations would be more complicated:
71755875 = 61735500 + 10020375;
61735500 = 6 10020375 + 1613250;
10020375 = 6 1613250 + 340875;
1613250 = 4 340875 + 249750;
340875 = 249750 + 91125;
249750 = 2 91125 + 67500;
91125 = 67500 + 23625;
67500 = 2 23625 + 20250;
23625 = 20250 + 3375;
20250 = 6 3375.
Euclid's algorithm here allows us to determine the GCD of the numbers 71755875 and 61735500, equal to 3375 and corresponds to the expansion of the ratio 71755875 to 61735500 into a continued fraction:
Euclid's algorithm turns out to be equivalent to the modern procedure for decomposing a number into a continued fraction, and moreover, it allows you to "round" the ratios of numbers, i.e. Replace a fraction with a large denominator with a fraction very close to it with a smaller denominator. Indeed, the expression
equal to a fraction, in modern mathematics is called the “approaching fraction” of the expansion of the relation b = into a continued (or continuous) fraction.
It's clear that
b=1+< 1 + и б=1 + > 1+ = ,
insofar as
The above comparison > was made in the III century. BC. Aristarchus of Samos in the treatise "On the distance and size of the Moon and the Sun."
It is now known that the convergents of the expansion of any (rational or irrational) number into a continued fraction are the best rational approximations of this number.
Algorithms with polynomials
Euclid's algorithm is a method for finding the greatest common divisor of two integers, as well as two polynomials in one variable...
One of the oldest mathematical algorithms is the Euclid algorithm for finding the greatest common divisor of two positive numbers. Here is its simplest form. Let two integers be given. If they are equal...
Analysis of the Euclidean algorithm in Euclidean rings
Before proceeding to the analysis of Euclid's algorithm, consider the Fibonacci numbers. The essence of the Fibonacci sequence is that starting from 1.1, the next number is obtained by adding the previous two. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 …...
The history of the formation of the concept of "algorithm". Famous Algorithms in the History of Mathematics
Euclid's algorithm is a universal way that allows you to calculate the greatest common divisor of two positive integers. Description of the algorithm for finding GCD by division: 1. Greater number divide by less than 2. If divided without a remainder ...
Ring of Gaussian integers
We use the usual definition of the greatest common divisor for rings. The gcd of two Gaussian numbers is their common divisor, which is divisible by any other common divisor. As with the set of integers...
Mathematical foundations of the system of residual classes
Consider an example. Let p = 6. Then we have six partition classes of the set of integers modulo 6: r = 0; r = 1; r = 2; r=3; r=4; r=5; where r denotes the remainder of an integer divided by 6...
Methods for studying polynomials in optional classes in high school general education school
Let the ring of polynomials be over. Definition 1: Let and, if there is a polynomial, then the remainder of the division is zero, then it is called the divisor of the polynomial and is denoted: ()...
The main stages of formation and structure modern mathematics
In the 3rd century BC, a book of Euclid with the same name appeared in Alexandria, in the Russian translation of "Beginnings". From the Latin name "Beginnings" came the term "elementary geometry". Despite...
On the territory of a certain city N there are factories and shops that supply products from these factories. As a result of the development, possible routes for laying communications were determined and the cost of their creation for each route was estimated ...
Application of methods of discrete mathematics in economics
A company engaged in the transportation of perishable goods needs to deliver goods from Suifenhe to Khabarovsk, and there are several routes along which delivery can be made. The distance between Suifenhe and City 2 is 15 km...
Development of the concept of "Space" and non-Euclidean geometry
Special Methods integration of rational expressions
Let it be necessary to find the gcd of polynomials and. Without loss of generality, we will assume that the degree is not higher than the degree. We represent the polynomial in the form: where is the remainder of the division by. Then the degree is less than the degree of the divisor. Further...
Residue theory
Residue theory
Definition. The number d ??Z, dividing simultaneously the numbers a, b, c, ..., k ??Z, is called the common divisor of these numbers. The largest d with this property is called the greatest common divisor. Notation: d = (a , b , c , ..., k) . Theorem. If (a , b) = d...
Residue theory
Let it be required to solve a linear Diophantine equation: ax + by = c , where a , b , c ??Z ; a and b are not zeros. Let's try to reason, looking at this equation. Let (a , b) = d . Then a = a 1 d ; b = b 1 d and the equation looks like this: a 1 d x + b 1 d y = c , i.e. d (a 1 x + b 1 y) = c...
Widespread in e-commerce. Also, the algorithm is used in solving linear Diophantine equations, in constructing continued fractions, in the Sturm method. Euclid's algorithm is the main tool for proving theorems in modern number theory, such as Lagrange's theorem on the sum of four squares and the fundamental theorem of arithmetic.
Encyclopedic YouTube
1 / 5
✪ Math. Natural numbers: Euclid's algorithm. Foxford Online Learning Center
✪ Euclid's algorithm
✪ Euclid's algorithm, fast way find gcd
✪ Math 71. Greatest common divisor. Euclid's Algorithm - Academy of Entertaining Sciences
✪ 20 while Loop Euclid Python Algorithm
Subtitles
Story
Ancient Greek mathematicians called this algorithm ἀνθυφαίρεσις or ἀνταναίρεσις - "mutual subtraction". This algorithm was not discovered by Euclid, since it is already mentioned in Topeka Aristotle. In the "Elements" of Euclid, it is described twice - in Book VII for finding the greatest common divisor of two natural numbers and in Book X for finding the greatest common measure of two homogeneous quantities. In both cases, a geometric description of the algorithm is given to find the "common measure" of two segments.
Description
Euclid's algorithm for integers
Let be a (\displaystyle a) and b (\displaystyle b)- integers not equal to zero at the same time, and a sequence of numbers
a > b > r 1 > r 2 > r 3 > r 4 > … > r n (\displaystyle a>b>r_(1)>r_(2)>r_(3)>r_(4)>\ \dots \ >r_(n))determined by the fact that each r k (\displaystyle r_(k))- this is the remainder of dividing the previous number by the previous one, and the penultimate one is divided by the last one, that is:
a = b q 0 + r 1 , (\displaystyle a=bq_(0)+r_(1),) b = r 1 q 1 + r 2 , (\displaystyle b=r_(1)q_(1)+r_(2),) r 1 = r 2 q 2 + r 3 , (\displaystyle r_(1)=r_(2)q_(2)+r_(3),) ⋯ (\displaystyle \cdots ) r k − 2 = r k − 1 q k − 1 + r k , (\displaystyle r_(k-2)=r_(k-1)q_(k-1)+r_(k),) ⋯ (\displaystyle \cdots ) r n − 2 = r n − 1 q n − 1 + r n , (\displaystyle r_(n-2)=r_(n-1)q_(n-1)+r_(n),) r n − 1 = r n q n . (\displaystyle r_(n-1)=r_(n)q_(n).)Then gcd( a, b), the greatest common divisor a and b, is equal to r n , the last non-zero member of this sequence.
Existence such r 1 , r 2 , ..., r n , that is, the possibility of division with a remainder m on the n for any whole m and whole n≠ 0 is proved by induction on m.
Correctness this algorithm follows from the following two statements:
- Let be a = b⋅q + r, then gcd(a, b) = gcd(b, r).
Proof
- GCD( r, 0) = r for any non-zero r(because 0 is divisible by any integer other than zero).
Euclid's geometric algorithm
Let two segments of length be given a and b. Subtract the smaller segment from the larger segment and replace the larger segment with the resulting difference. Repeat this operation until the segments are equal. If this happens, then the original segments are commensurable, and the last segment obtained is their greatest common measure. If there is no common measure, then the process is infinite. In this form, the algorithm is described by Euclid and is implemented using a compass and ruler.
Example
To illustrate, the Euclid algorithm will be used to find the gcd a= 1071 and b= 462. To begin with, subtract a multiple of 462 from 1071 until we get a difference less than 462. We must subtract 462 twice, ( q 0 = 2), remaining with a remainder of 147:
1071 = 2 × 462 + 147.
Then we subtract a multiple of 147 from 462 until we get a difference less than 147. We must subtract 147 three times ( q 1 = 3), remaining with a remainder of 21:
462 = 3 x 147 + 21.
Then we subtract a multiple of 21 from 147 until we get a difference less than 21. We must subtract 21 seven times ( q 2 = 7), remaining without a remainder:
147 = 7 x 21 + 0.
Thus the sequence a > b > r 1 > r 2 > r 3 > … > r n in this particular case would look like this:
1071 > 462 > 147 > 21.
Since the last remainder is zero, the algorithm ends with 21 and gcd(1071, 462) = 21.
In tabular form, the steps were as follows:
Applications
Extended Euclid's Algorithm and Bezout's Relation
Formulas for r i (\displaystyle r_(i)) can be rewritten like this:
r 1 = a + b (− q 0) (\displaystyle r_(1)=a+b(-q_(0))) r 2 = b − r 1 q 1 = a (− q 1) + b (1 + q 1 q 0) (\displaystyle r_(2)=b-r_(1)q_(1)=a(-q_( 1))+b(1+q_(1)q_(0))) ⋮ (\displaystyle \vdots ) GCD (a , b) = r n = a s + b t (\displaystyle (a,b)=r_(n)=as+bt)Here s and t whole. This representation of the greatest common divisor is called the Bezout relation, and the numbers s and t- coefficients Bezu . Bezout's relation is the key one in the proof of Euclid's lemma and the main theorem of arithmetic.
Continued fractions
Euclid's algorithm is quite closely related to continued fractions. Attitude a/b admits a continued fraction representation:
a b = [ q 0 ; q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=).In this case, the continued fraction without the last term is equal to the ratio of the Bezout coefficients t/s taken with a minus sign:
[ q 0 ; q 1 , q 2 , ⋯ , q n − 1 ] = − t s (\displaystyle =-(\frac (t)(s))).The sequence of equalities defining the Euclid algorithm can be rewritten in the form:
a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 r N − 1 = q N (\displaystyle (\begin(aligned)(\frac (a)(b))&=q_(0)+(\frac (r_(0))(b))\\(\frac (b )(r_(0)))&=q_(1)+(\frac (r_(1))(r_(0)))\\(\frac (r_(0))(r_(1)))& =q_(2)+(\frac (r_(2))(r_(1)))\\&()\ \vdots \\(\frac (r_(k-2))(r_(k-1) ))&=q_(k)+(\frac (r_(k))(r_(k-1)))\\&()\ \vdots \\(\frac (r_(N-2))(r_ (N-1)))&=q_(N)\end(aligned)))The last term on the right side of an equation is always equal to the reciprocal of the left side of the following equation. Therefore, the first two equations can be combined in the form:
a b = q 0 + 1 q 1 + r 1 r 0 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (r_( 1))(r_(0))))))The third equality can be used to replace the denominator of the expression r 1 /r 0 , we get:
a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\ cfrac (1)(q_(2)+(\cfrac (r_(2))(r_(1))))))))Last Residue Ratio r k /r k−1 can always be replaced using the next equality in the sequence, and so on until the last equation. The result is a continued fraction:
a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [ q 0 ; q 1 , q 2 , … , q N ] (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (1)(q_ (2)+(\cfrac (1)(\ddots +(\cfrac (1)(q_(N)))))))))=)Generalized Euclid's algorithm for polynomials
Euclid's algorithm and the extended Euclid's algorithm naturally generalize to the ring of polynomials k[x] from one variable over an arbitrary field k, since for such polynomials the operation of division with a remainder is defined. When executing Euclid's algorithm for polynomials, similarly to Euclid's algorithm for integers, a sequence of polynomial remainders (PRS) is obtained.
Ring example Z[x]
Let cont(f) by definition be the gcd of the coefficients of the polynomial f(x) from Z[x] - content polynomial. The quotient of dividing f(x) by cont(f) is called primitive part polynomial f(x) and is denoted by primpart(f(x)). These definitions will be needed to find the gcd of two polynomials p 1 (x) and p 2 (x) in the ring Z[x]. For polynomials over integers, the following is true:
C o n t ((\displaystyle cont() NODNOD ( c o n t (p 1 (x)) , c o n t (p 2 (x)) ) , (\displaystyle \(cont(p_(1)(x)),cont(p_(2)(x))\),)
P r i m p a r t ((\displaystyle primpart() GCD ( p 1 (x) , p 2 (x) )) = (\displaystyle \(p_(1)(x),p_(2)(x)\))=) GCD ( p r i m p a r t (p 1 (x)) , p r i m p a r t (p 2 (x)) ) . (\displaystyle \(primpart(p_(1)(x)),primpart(p_(2)(x))\).)
Thus, the problem of finding the gcd of two arbitrary polynomials is reduced to the problem of finding the gcd of primitive polynomials.
Let there be two primitive polynomials p 1 (x) and p 2 (x) from Z[x] for which the relation between their powers is satisfied: deg(p 1 (x)) = m and deg(p 2 (x)) = n, m > n. The division of polynomials with a remainder implies the exact divisibility of the highest coefficient of the dividend by the highest coefficient of the divisor; in the general case, division with a remainder cannot be performed. Therefore, a pseudo-division algorithm is introduced, which nevertheless allows one to obtain a pseudo-quotient and a pseudo-remainder (prem), which will themselves belong to the set of polynomials over integers.
By pseudo-division we mean that the division itself is preceded by the multiplication of the polynomial p 1 (x) (\displaystyle p_(1)(x)) on the (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), i.e
L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , deg (r (x))< deg (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}
where q (x) (\displaystyle q(x)) and r (x) (\displaystyle r(x))- respectively pseudopartial and pseudoresidue.
So, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x),p_(2)(x)\in Z[x]), moreover deg (p 1) = n 1 ≥ deg (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Then Euclid's algorithm consists of the following steps:
1. Calculation of GCD contents:
C:= (\displaystyle c:=) GCD ( c o n t (p 1) , c o n t (p 2) ) (\displaystyle \(cont(p_(1)),cont(p_(2))\)).
2. Calculation of primitive parts:
P 1 ′ (x) := p r i m p a r t (p 1 (x)) ; (\displaystyle p_(1)"(x):=primpart(p_(1)(x));)
P 2 ′ (x) := p r i m p a r t (p 2 (x)) . (\displaystyle p_(2)"(x):=primpart(p_(2)(x)).)
3. Building a sequence of polynomial residues:
P 1 ′ (x) , (\displaystyle p_(1)"(x),)
P 2 ′ (x) , (\displaystyle p_(2)"(x),)
P 3 (x) := p r e m (p 1 ′ (x) , p 2 ′ (x)) , (\displaystyle p_(3)(x):=prem(p_(1)"(x),p_(2 )"(x)))
P 4 (x) := p r e m (p 2 ′ (x) , p 3 (x)) , (\displaystyle p_(4)(x):=prem(p_(2)"(x),p_(3) (x)))
P 5 (x) := p r e m (p 3 (x) , p 4 (x)) , (\displaystyle p_(5)(x):=prem(p_(3)(x),p_(4)(x ))))
. . . (\displaystyle ...)
P h (x) := p r e m (p h − 2 (x) , p h − 1 (x)) . (\displaystyle p_(h)(x):=prem(p_(h-2)(x),p_(h-1)(x)).)
Consider two main methods for finding GCD in two main ways: using the Euclid algorithm and by factoring. Let's apply both methods for two, three and more numbers.
Euclid's algorithm for finding GCD
Euclid's algorithm makes it easy to calculate the greatest common divisor of two positive numbers. We have given the formulations and proof of Euclid's algorithm in the Greatest Common Divisor: Determinant, Examples section.
The essence of the algorithm is to consistently carry out division with a remainder, during which a series of equalities of the form is obtained:
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
We can finish the division when rk + 1 = 0, wherein r k = gcd (a , b).
Example 1
64 and 48 .
Decision
Let's introduce the notation: a = 64 , b = 48 .
Based on the Euclid algorithm, we will carry out the division 64 on the 48 .
We get 1 and the remainder 16 . It turns out that q 1 = 1, r 1 = 16.
The second step is to divide 48 by 16 , we get 3 . I.e q2 = 3, a r 2 = 0 . Thus, the number 16 is the greatest common divisor for the numbers from the condition.
Answer: gcd(64, 48) = 16.
Example 2
What is the GCD of numbers 111 and 432 ?
Decision
Divide 432 on the 111 . According to Euclid's algorithm, we get the chain of equalities 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 .
Thus, the greatest common divisor of numbers 111 and 432 is 3 .
Answer: gcd(111, 432) = 3.
Example 3
Find the greatest common divisor of 661 and 113 .
Decision
We will sequentially divide the numbers and get the GCD (661 , 113) = 1 . This means that 661 and 113 are relatively prime numbers. We could figure this out before we started the calculations if we looked at the table of primes.
Answer: gcd(661, 113) = 1.
Finding GCD by Factoring Numbers into Prime Factors
In order to find the greatest common divisor of two numbers by factoring, it is necessary to multiply all the prime factors that are obtained by decomposing these two numbers and are common to them.
Example 4
If we decompose the numbers 220 and 600 into prime factors, we get two products: 220 = 2 2 5 11 and 600 = 2 2 2 3 5 5. Common factors in these two products will be 2 , 2 and 5 . This means that NOD (220, 600) = 2 2 5 = 20.
Example 5
Find the greatest common divisor of numbers 72 and 96 .
Decision
Find all prime factors of numbers 72 and 96 :
72 36 18 9 3 1 2 2 2 3 3
96 48 24 12 6 3 1 2 2 2 2 2 3
Common prime factors for two numbers: 2 , 2 , 2 and 3 . This means that NOD (72, 96) = 2 2 2 3 = 24.
Answer: gcd(72, 96) = 24.
The rule for finding the greatest common divisor of two numbers is based on the properties of the greatest common divisor, according to which 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
Regardless of the number of numbers for which we need to find the GCD, we will act according to the same algorithm, which consists in finding the GCD of two numbers in succession. This algorithm is based on the application of the following theorem: GCD of several numbers a 1 , a 2 , … , a k is equal to the number dk, which is found in the sequential calculation of the 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 .
Example 6
Find the greatest common divisor of the four numbers 78 , 294 , 570 and 36 .
Decision
Let's introduce the notation: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.
Let's start by finding the GCD of the numbers 78 and 294: d2= GCD (78 , 294) = 6 .
Now let's start finding d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) . According to the Euclid algorithm 570 = 6 95 . It means that d 3 = GCD (6 , 570) = 6 .
Find d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) . 36 is divisible by 6 without a remainder. This allows us to get d4= GCD (6 , 36) = 6 .
d4 = 6, that is, GCD (78 , 294 , 570 , 36) = 6 .
Answer:
And now let's look at another way to calculate GCD for those and more numbers. We can find the gcd by multiplying all the common prime factors of the numbers.
Example 7
Calculate the gcd of the numbers 78 , 294 , 570 and 36 .
Decision
Let's decompose these numbers into prime factors: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .
For all four numbers, the common prime factors will be the numbers 2 and 3.
It turns out that NOD (78, 294, 570, 36) = 2 3 = 6.
Answer: gcd(78 , 294 , 570 , 36) = 6 .
Finding the gcd of negative numbers
If we have to deal with negative numbers, then we can use the modules of these numbers to find the greatest common divisor. We can do this, knowing the property of numbers with opposite signs: numbers n and -n have the same divisors.
Example 8
Find the gcd of negative integers − 231 and − 140 .
Decision
To perform calculations, let's take modules of numbers given in the condition. These will be the numbers 231 and 140. Let's put it briefly: GCD (− 231 , − 140) = GCD (231 , 140) . Now let's apply Euclid's algorithm to find prime factors of two numbers: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 and 42 = 7 6. We get that gcd (231, 140) = 7 .
And since NOD (− 231 , − 140) = GCD (231 , 140) , then the gcd of numbers − 231 and − 140 equals 7 .
Answer: gcd (− 231 , − 140) = 7 .
Example 9
Determine the gcd of three numbers - 585, 81 and − 189 .
Decision
Let's replace the negative numbers in the above list with their absolute values, we get GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Then we decompose all given numbers into prime factors: 585 = 3 3 5 13, 81 = 3 3 3 3 and 189 = 3 3 3 7. The prime factors 3 and 3 are common to the three numbers. It turns out that gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 .
Answer: GCD (− 585 , 81 , − 189) = 9 .
If you notice a mistake in the text, please highlight it and press Ctrl+Enter
Euclid's algorithm is an algorithm for finding the greatest common divisor (gcd) of a pair of integers.
Greatest Common Divisor (GCD) is a number that divides two numbers without a remainder and is itself divisible without a remainder by any other divisor of the given two numbers. Simply put, this is the largest number by which the two numbers for which the gcd is sought can be divided without a remainder.
Algorithm for finding GCD by division
- Divide the larger number by the smaller one.
- If it is divided without a remainder, then the smaller number is the GCD (you should exit the loop).
- If there is a remainder, then the larger number is replaced by the remainder of the division.
- Let's move on to point 1.
Example:
Find GCD for 30 and 18.
30 / 18 = 1 (remainder 12)
18 / 12 = 1 (remainder 6)
12 / 6 = 2 (remainder 0)
End: GCD is the divisor of 6.
gcd(30, 18) = 6
a = 50 b = 130 while a != 0 and b != 0 : if a > b: a = a % b else : b = b % a print (a + b)
In the loop, the remainder of the division is written to the variable a or b. The loop ends when at least one of the variables is zero. This means that the other contains GCD. However, we don't know which one. Therefore, for GCD we find the sum of these variables. Since one of the variables is zero, it has no effect on the result.
Algorithm for finding GCD by subtraction
- Subtract the smaller from the larger number.
- If it turns out 0, then it means that the numbers are equal to each other and are GCD (you should exit the loop).
- If the result of the subtraction is not equal to 0, then the larger number is replaced by the result of the subtraction.
- Let's move on to point 1.
Example:
Find GCD for 30 and 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
End: GCD is the minuend or the subtrahend.
gcd(30, 18) = 6
a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)