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, a quick way to 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 "Beginnings" 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 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 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)), that is

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)).)

• Introduce the concept of "Euclid's algorithm".
• Learn to find the most common divisors in different mathematical ways.

During the classes

The concept of Euclid's algorithm

It is one of the oldest mathematical, which is more than 2000 years old.

Euclid's algorithm was invented to find greatest common divisor pairs of integers.

Greatest Common Divisor

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 these numbers.

In other words, this is the largest number by which two numbers can be divided without a remainder, for which a common divisor is being sought.

Algorithm for finding GCD by division

Description of the algorithm for finding the greatest common divisor by division

Larger number divided by smaller

If divisible without a remainder, then the smaller number is the greatest common divisor. Now you need to exit cycle

If there is a remainder, then the larger number is replaced by the remainder of the division

Go to point 1.

Example:

Find the greatest common divisor for 300 and 180.

300/180 = 1 (remainder 120)

180/120 = 1 (remainder 60)

120/60 = 2 (remainder 0).

End: the greatest common divisor is 6.

AT cycle"a" or "b" fixes the remainder of the division. When there is no remainder (we don’t know whether it is in “a” or “b,” so we check both terms), then the cycle ends.

At the end, the sum of "a" and "b" is displayed, because we do not know in which variable the greatest common divisor is written, and in one of them in any case 0, which does not affect the result of the sum.

Algorithm for finding GCD by subtraction

Description of the algorithm for finding the greatest common divisor by subtraction

Subtract the smaller from the larger number

If it turns out 0, then the numbers are equal to each other and are the greatest common divisor. Loop exit

If the result of the subtraction is not equal to 0, then the larger number is replaced by the result of the subtraction

Go to point 1.

Example: Find for the numbers 300 and 180.

End: The most common divisor of 300 and 180 is 60.

As a way to find the greatest common measure of two segments (the method of alternating subtraction) was known to the Pythagoreans.

When finding the greatest common measure of two segments proceed in the same way as above.

The division operation with a remainder is replaced by its geometric counterpart: lesser line segment set aside for a larger one as many times as possible, and the rest of the larger segment (and this is the remainder of the division) is postponed for a smaller segment.

If segments a and b commensurate, then the last non-zero remainder will give the greatest common measure of the segments.

In the case of their incommensurability, the resulting sequence of non-zero residues will be infinite.

Example:

As segments, take side AB and AC of an isosceles triangle ABC, in which A=C = 72°, B= 36°.

As the first remainder, we get segment AD (the CD bisector of angle C), and, as is easy to see, the sequence of and zero remainders will be infinite.

Hence, segments AB and AC are not commensurable.

Questions

1. What is the Euclid algorithm?

2. What is the greatest common divisor?

List of sources used

1. Lesson on the topic: "Euclid's Algorithm", Korchevoi P.I., Lutsk

2. A. I. Shchetnikov, Euclid’s algorithm and continued fractions. - Novosibirsk: ANT, 2003

3. Countinho S. Introduction to number theory. Algorithm RSA, - M., 2001

4. Kostrikin A.I. Introduction to algebra, - M., 2000

Edited and sent by the teacher Kyiv National University. Taras Shevchenko Solovyov M.S.

Working on the lesson

Korchevoi P.I.

Solovyov M.S.

You can raise a question about modern education, express an idea or solve an urgent problem at Education Forum

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). It also gives a practical way of finding numbers u and v from Z (or, if you like, from the theorem of point 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, obviously, is 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 \u003d into a continued (or continuous) fraction.

It's clear that

b=1+< 1 + и б=1 + > 1+ = ,

because the

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. Divide a larger number by a smaller one 2. If it divides 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 the senior class of a secondary 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 of 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 identified 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 for integrating 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...

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

1. Divide the larger number by the smaller one.
2. If it is divided without a remainder, then the smaller number is the GCD (you should exit the loop).
3. If there is a remainder, then the larger number is replaced by the remainder of the division.
4. 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

1. Subtract the smaller from the larger number.
2. If it turns out 0, then it means that the numbers are equal to each other and are GCD (you should exit the loop).
3. If the result of the subtraction is not equal to 0, then the larger number is replaced by the result of the subtraction.
4. 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)

Let's 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 .

Solution

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 . That is 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 ?

Solution

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 .

Solution

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 .

Solution

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 follow 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 .

Solution

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 .

Solution

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 .

Solution

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 .

Solution

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