• Introduce the concept of “Euclidean algorithm”.
• Learn to find the most common divisors using different mathematical methods.

During the classes

Concept of Euclidean Algorithm

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

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

Greatest common divisor

Largest 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 for which a common divisor can be found can be divided without a remainder.

Algorithm for finding GCD by division

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

The larger number is divided by the smaller number

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

If there is a remainder, then replace the larger number with 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.

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

At the end, the sum of “a” and “b” is displayed, because we do not know which variable contains the greatest common divisor, and in any case one of them contains 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

The smaller number is subtracted from the larger number

If the result is 0, then the numbers are equal to each other and are the greatest common divisor. Exit from loop

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

Go to point 1.

Example: Find for numbers 300 and 180.

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

The method of finding 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 ways as above.

The operation of division with a remainder is replaced by its geometric counterpart: less line segment they put it off on the larger one as many times as possible, and the rest of the larger segment (and this is the remainder of the division) is put off on the smaller segment.

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

If they are incommensurable, the resulting sequence of non-zero residues will be infinite.

Example:

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

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

This means that segments AB and AC are not commensurable.

Questions

1. What is the Euclidean algorithm?

2. What is the greatest common divisor?

List of sources used

1. Lesson on the topic: “Euclidean Algorithm”, P. I. Korchevoy, Lutsk

2. Shchetnikov A.I. Euclidean algorithm and continued fractions. - Novosibirsk: ANT, 2003.

3. Countinho S. Introduction to number theory. RSA algorithm, – M., 2001.

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

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

We worked on the lesson

Korchevoy P.I.

Soloviev M. S.

Ask a question about modern education, express an idea or solve a pressing problem, you can Educational forum

Widely used in e-commerce. The algorithm is also used in solving linear Diophantine equations, in constructing continued fractions, and 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

✪ Mathematics. Natural numbers: Euclid's algorithm. Foxford Online Learning Center

✪Euclidean algorithm

✪ Euclidean algorithm, quick way find gcd

✪ Math 71. Greatest common divisor. Euclid's algorithm - Academy of Entertaining Sciences

✪ 20 while loop Python Euclidean algorithm

Subtitles

Story

Ancient Greek mathematicians called this algorithm ἀνθυφαίρεσις or ἀνταναίρεσις - “mutual subtraction”. This algorithm was not discovered by Euclid, since it was already mentioned in Topeka Aristotle. In Euclid's Elements 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 for finding the “common measure” of two segments.

Description

Euclid's algorithm for integers

Let a (\displaystyle a) And b (\displaystyle b)- integers that are not equal to zero at the same time, and a sequence of numbers

determined by the fact that each r k (\displaystyle r_(k))- this is the remainder from dividing the previous number by the previous one, and the penultimate one is divided by the last one completely, that is:

(\displaystyle r_(n-1)=r_(n)q_(n).) a, b Then GCD( a And b), greatest common divisor , is equal r

n, the last non-zero term of this sequence. Existence , is equal 1 , , is equal 2 , ..., , is equal such n, that is, the possibility of division with a remainder m on n n, that is, the possibility of division with a remainder for any integer on and the whole n, that is, the possibility of division with a remainder.

≠ 0, can be proven by induction on Correctness

• Let a = b⋅This algorithm follows from the following two statements: + , is equal q

, then gcd (a, b) = gcd (b, r).

• Proof , is equal, 0) = , is equal GCD( , is equal for any non-zero

(since 0 is divisible by any integer other than zero).

Geometric Euclidean algorithm a And b Let two segments of length be given

. Subtract the smaller segment from the larger segment and replace the larger segment with the resulting difference. We repeat this operation until the segments are equal. If this happens, then the original segments are commensurable, and the last resulting segment is their greatest common measure. If there is no general measure, then the process is endless. In this form, the algorithm was described by Euclid and is implemented using a compass and ruler.

To illustrate, the Euclidean algorithm will be used to find the gcd a= 1071 and b= 462. First, subtract a multiple of 462 from 1071 until we get a difference less than 462. We must subtract 462 twice, ( This algorithm follows from the following two statements: 0 = 2), leaving a remainder of 147:

1071 = 2 × 462 + 147.

Then subtract multiples of 147 from 462 until we get a difference less than 147. We must subtract 147 three times ( This algorithm follows from the following two statements: 1 = 3), leaving a remainder of 21:

462 = 3 × 147 + 21.

Then subtract multiples of 21 from 147 until the difference is less than 21. We must subtract 21 seven times ( This algorithm follows from the following two statements: 2 = 7), leaving no remainder:

147 = 7 × 21 + 0.

Thus the sequence a > b > , is equal 1 > , is equal 2 > , is equal 3 > … > , is equal n in this particular case will look like this:

1071 > 462 > 147 > 21.

Since the last remainder is zero, the algorithm ends with the number 21 and gcd(1071, 462) = 21.

In tabular form, the steps were as follows:

Applications

Extended Euclidean algorithm and Bezout's relation

Formulas for r i (\displaystyle r_(i)) can be rewritten as follows:

Here s And t whole. This representation of the greatest common divisor is called the Bezout relation, and the numbers s And t- Bezout coefficients. Bezout's relation is key in the proof of Euclid's lemma and the fundamental theorem of arithmetic.

Continued fractions

Euclid's algorithm is quite closely related to continued fractions. Attitude a/b can be represented as a continued fraction:

q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=) t/s In this case, the continued fraction without the last term is equal to the ratio of the Bezout coefficients

[q 0 ;

The last term on the right side of the equation is always equal to the inverse of the left side of the following equation. Therefore the first two equations can be combined in the form:

The third equality can be used to replace the denominator of the expression , is equal 1 /, is equal 0 , we get:

Last Residual Ratio , is equal k /, is equal k−1 can always be replaced using the next equation in the sequence, and so on until the last equation. The result is a continued fraction:

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 Euclidean algorithm for polynomials k[The Euclidean algorithm and the extended Euclidean algorithm naturally generalize to the ring of polynomials x k] from one variable over an arbitrary field

, since for such polynomials the operation of division with remainder is defined. Running the Euclidean algorithm for polynomials in a similar way to the Euclidean algorithm for integers produces a polynomial remainder sequence (PRS). Example for a ring[The Euclidean algorithm and the extended Euclidean algorithm naturally generalize to the ring of polynomials]

Z Let cont(f) by definition be the gcd of the coefficients of the polynomial f(x) from Z[x] - content polynomial. The quotient of f(x) divided 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 And p1(x) p2(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 r i m p a r t ((\displaystyle primpart() ( p 1 (x) , p 2 (x) )) = (\displaystyle \(p_(1)(x),p_(2)(x)\))=)

( p r i m p a r t (p 1 (x)), p r i m p a r t (p 2 (x)) .

Let there be two primitive polynomials p 1 (x) and p 2 (x) from Z[x], for which the relation between their powers holds: deg(p 1 (x)) = m and deg(p 2 (x)) = n, m > n. Division of polynomials with a remainder presupposes 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 still 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 a polynomial p 1 (x) (\displaystyle p_(1)(x)) m (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))- pseudo-quotient and pseudo-remainder, respectively.

So, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x),p_(2)(x)\in Z[x]), and deg ⁡ (p 1) = n 1 ≥ deg ⁡ (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Then the Euclidean algorithm consists of the following steps:

1. Calculation of GCD contents:

C:= (\displaystyle c:=) P r i m p a r t ((\displaystyle primpart() ( 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. Construction of a sequence of polynomial remainders:

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

..

. 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 two numbers for which the gcd is being sought can be divided without a remainder.

Algorithm for finding GCD by division

1. Divide the larger number by the smaller number.
2. If it is divided without a remainder, then the smaller number is GCD (you should exit the cycle).
3. If there is a remainder, then replace the larger number with 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 a 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 one contains a gcd. However, we don’t know which one exactly. 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 number from the larger number.
2. If the result is 0, 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 replace the larger number with 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 a minuend or subtrahend.
GCD(30, 18) = 6

a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)

1.1 Application of the Euclidean algorithm

Like any job well done, the Euclidean algorithm produces much more than was originally expected. From his examination it is clear, for example, that the set of divisors a and b coincides with the set of divisors (a, b). He also gives a practical way of finding numbers u and v from Z (or, if you prefer, from the theorem in point 2) such that

r n = 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 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. The ancient Chinese mathematicians also found GCD in the same way. And only the fact that this procedure became known in the Renaissance precisely from the “Principles” gave it the name “Euclidean algorithm”

Most likely, it arose from the commercial practice of ancient merchants, when they needed to compare various ratios of integers. How, for example, can we 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, we now write it 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 complex:

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.

The Euclidean algorithm here allows us to determine the gcd of the numbers 71755875 and 61735500, which is equal to 3375 and corresponds to the expansion of the ratio 71755875 to 61735500 into a continued fraction:

The Euclid algorithm turns out to be equivalent to the modern procedure for decomposing a number into a continued fraction and, moreover, allows you to “round off” the ratios of numbers, i.e. replace a fraction with a large denominator with a very close fraction with a smaller denominator. In fact, the expression

equal to a fraction, in modern mathematics is called a “suitable fraction” of the decomposition of the relation b = into a continued (or continued) fraction.

It's clear that

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

because the

The above comparison was made in the 3rd century. BC. Aristarchus of Samos in his treatise “On the distance and size of the Moon and the Sun.”

It is now known that the suitable fractions of the continued fraction expansion of any (rational or irrational) number are the best rational approximations of that number.

Algorithms with polynomials

Euclid's algorithm is a method for finding the greatest common divisor of two integers, as well as two polynomials of the same 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 we begin analyzing the Euclidean algorithm, let's look at the Fibonacci numbers. The essence of the Fibonacci sequence is that starting from 1.1, the next number is obtained by adding the two previous ones. 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". The most famous algorithms in the history of mathematics

The Euclidean algorithm is a universal method that allows you to calculate the greatest common divisor of two positive integers. Description of the algorithm for finding GCD by division: 1. Divide the larger number by the smaller 2. If it is divided without a remainder...

Gaussian integer ring

We use the usual definition of the greatest common divisor for rings. The GCD of two Gaussian numbers is their common divisor that is divisible by any other common divisor. As in many integers...

Mathematical foundations of the residual class system

Let's look at an example. Let p = 6. Then we have six classes of partition of the set of integers modulo 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; where r denotes the remainder when dividing an integer by 6...

Methods for studying polynomials in elective classes in senior 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 “Principles”. The term “elementary geometry” comes from the Latin name “Beginnings”. Despite...

On the territory of a certain city N there are factories and stores to which products from these factories are supplied. 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 discrete mathematics methods 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. Let us represent the polynomial in the form: where is the remainder of division by. Then the degree is less than the degree of the divisor. Further...

Residue theory

Residue theory

Definition. The number d??Z, which simultaneously divides 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. Designation: d = (a, b, c, ..., k). Theorem. If (a , b) = d...

Residue theory

Let it be necessary 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 by 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...

Let's consider two main methods of finding GCD in two main ways: using the Euclidean algorithm and by factoring into prime factors. Let's apply both methods for two, three or more numbers.

Euclidean algorithm for finding GCD

The Euclidean algorithm makes it easy to calculate the greatest common factor of two positive numbers. We presented the formulations and proof of the Euclid algorithm in the section “Greatest common divisor: determinant, examples.”

The essence of the algorithm is to sequentially carry out division with a remainder, during which a series of equalities of the form are 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 division when r k + 1 = 0, wherein r k = gcd (a , b).

Example 1

64 And 48 .

Solution

Let's introduce the following notations: a = 64, b = 48.

Based on the Euclidean algorithm, we will carry out division 64 m 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 q 2 = 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

We divide 432 m 111 . According to the Euclidean algorithm, we obtain 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 is 111 And 432 – this is 3.

Answer: GCD (111, 432) = 3.

Example 3

Find the greatest common divisor of the numbers 661 and 113.

Solution

Let's sequentially divide the numbers and get GCD (661 , 113) = 1 . This means that 661 and 113 are relatively prime numbers. We could figure this out before starting the calculation if we consulted a table of prime numbers.

Answer: GCD (661, 113) = 1.

Finding GCD by factoring numbers into prime factors

In order to find the greatest common divisor of two numbers using the factorization method, it is necessary to multiply all the prime factors that are obtained by factoring these two numbers and are common to them.

Example 4

If we factor 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. The common factors in these two products are 2, 2 and 5. This means that GCD (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

The common prime factors for two numbers are 2, 2, 2 and 3. This means that GCD (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 the 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 of sequentially finding the GCD of two numbers. This algorithm is based on the application of the following theorem: GCD of several numbers a 1 , a 2 , … , a k equal to the number dk, which is found by sequentially calculating 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 four numbers 78, 294, 570 and 36 .

Solution

Let us introduce the notation: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Let's start by finding the gcd of numbers 78 and 294: d 2 = P r i m p a r t ((\displaystyle primpart() (78 , 294) = 6 .

Now let's start finding d 3 = GCD (d 2 , a 3) = GCD (6, 570). According to the Euclidean algorithm 570 = 6 95. It means that d 3 = P r i m p a r t ((\displaystyle primpart() (6 , 570) = 6 .

Let's find d 4 = GCD (d 3 , a 4) = GCD (6, 36). 36 divisible by 6 without remainder. This allows us to get d 4 = P r i m p a r t ((\displaystyle primpart() (6 , 36) = 6 .

d4 = 6, that is, GCD (78 , 294 , 570 , 36) = 6 .

Answer:

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 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 GCD (78, 294, 570, 36) = 2 3 = 6.

Answer: GCD (78, 294, 570, 36) = 6.

Finding gcd of negative numbers

If we have to deal with negative numbers, then we can use the moduli 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, we take the modules of the numbers given in the condition. These will be the numbers 231 and 140. Let's write it down briefly: GCD (− 231 , − 140) = GCD (231, 140) . Now we apply the Euclidean 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 GCD (− 231 , − 140) = P r i m p a r t ((\displaystyle primpart() (231 , 140) , then 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) = P r i m p a r t ((\displaystyle primpart() (585 , 81 , 189) . Then we factor all these numbers into prime factors: 585 = 3 3 5 13, 81 = 3 3 3 3 and 189 = 3 3 3 7. Common to the three numbers are the prime factors 3 and 3. It turns out that GCD (585, 81, 189) = GCD (− 585, 81, − 189) = 9.

Answer: GCD (− 585, 81, − 189) = 9.

If you notice an error in the text, please highlight it and press Ctrl+Enter