Learning the Euclidean algorithm at school. Euclid's Algorithm - Finding the Greatest Common Divisor

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 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 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 Extended Euclid's Algorithm naturally generalizes 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 (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)).)

Greatest Common Divisor

Definition 2

If a natural number a is divisible by a natural number $b$, then $b$ is called a divisor of $a$, and the number $a$ is called a multiple of $b$.

Let $a$ and $b$ be natural numbers. The number $c$ is called a common divisor for both $a$ and $b$.

The set of common divisors of the numbers $a$ and $b$ is finite, since none of these divisors can be greater than $a$. This means that among these divisors there is the largest one, which is called the greatest common divisor of the numbers $a$ and $b$, and the notation is used to denote it:

$gcd \ (a;b) \ ​​or \ D \ (a;b)$

To find the greatest common divisor of two numbers:

1. Find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.

Example 1

Find the gcd of the numbers $121$ and $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Choose the numbers that are included in the expansion of these numbers

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.

$gcd=2\cdot 11=22$

Example 2

Find the GCD of monomials $63$ and $81$.

We will find according to the presented algorithm. For this:

Let's decompose numbers into prime factors

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

We select the numbers that are included in the expansion of these numbers

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Let's find the product of the numbers found in step 2. The resulting number will be the desired greatest common divisor.

$gcd=3\cdot 3=9$

You can find the GCD of two numbers in another way, using the set of divisors of numbers.

Example 3

Find the gcd of the numbers $48$ and $60$.

Solution:

Find the set of divisors of $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$

Now let's find the set of divisors of $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$

Let's find the intersection of these sets: $\left\((\rm 1,2,3,4,6,12)\right\)$ - this set will determine the set of common divisors of the numbers $48$ and $60$. The largest element in this set will be the number $12$. So the greatest common divisor of $48$ and $60$ is $12$.

Definition of NOC

Definition 3

common multiple of natural numbers$a$ and $b$ is a natural number that is a multiple of both $a$ and $b$.

Common multiples of numbers are numbers that are divisible by the original without a remainder. For example, for the numbers $25$ and $50$, the common multiples will be the numbers $50,100,150,200$, etc.

The least common multiple will be called the least common multiple and denoted by LCM$(a;b)$ or K$(a;b).$

To find the LCM of two numbers, you need:

1. Decompose numbers into prime factors
2. Write out the factors that are part of the first number and add to them the factors that are part of the second and do not go to the first

Example 4

Find the LCM of the numbers $99$ and $77$.

We will find according to the presented algorithm. For this

Decompose numbers into prime factors

$99=3\cdot 3\cdot 11$

Write down the factors included in the first

add to them factors that are part of the second and do not go to the first

Find the product of the numbers found in step 2. The resulting number will be the desired least common multiple

$LCC=3\cdot 3\cdot 11\cdot 7=693$

Compiling lists of divisors of numbers is often very time consuming. There is a way to find GCD called Euclid's algorithm.

Statements on which Euclid's algorithm is based:

If $a$ and $b$ are natural numbers, and $a\vdots b$, then $D(a;b)=b$

If $a$ and $b$ are natural numbers such that $b

Using $D(a;b)= D(a-b;b)$, we can successively decrease the numbers under consideration until we reach a pair of numbers such that one of them is divisible by the other. Then the smaller of these numbers will be the desired greatest common divisor for the numbers $a$ and $b$.

Properties of GCD and LCM

1. Any common multiple of $a$ and $b$ is divisible by K$(a;b)$
2. If $a\vdots b$ , then K$(a;b)=a$

If K$(a;b)=k$ and $m$-natural number, then K$(am;bm)=km$

If $d$ is a common divisor for $a$ and $b$, then K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d) $

If $a\vdots c$ and $b\vdots c$ , then $\frac(ab)(c)$ is a common multiple of $a$ and $b$

For any natural numbers $a$ and $b$ the equality

$D(a;b)\cdot K(a;b)=ab$

Any common divisor of $a$ and $b$ is a divisor of $D(a;b)$

Euclid's algorithm is a way to find the greatest common divisor (gcd) of two integers. The original version of the algorithm, when GCD is found by subtraction, was discovered by Euclid (3rd century BC). At present, division is more often used when calculating the GCD by the Euclid algorithm, since this method is more efficient.

Calculating gcd by division

The greatest common divisor of a pair of numbers is the largest number that divides both numbers of the pair. Let it be required to calculate the GCD for the numbers 108 and 72. The division calculation algorithm will be as follows:

1. Divide the larger number (dividend) by the smaller one (divisor): 108 / 72 = 1, remainder 36.
2. Since the remainder was not equal to zero, we will make the divisor divisible, and the remainder a divisor: 72 / 36 = 2, the remainder is 0.
3. When the remainder is zero, then the divisor is the desired gcd for the pair of given numbers. That is, gcd(108, 72) = 36. Indeed, 108/36 = 3 and 72/36 = 2.

In this algorithm division is repeated until the remainder is zero. When he becomes GCD is the divisor of the last division. For example, you want to find GCD(106, 16):

1. 106 / 16 = 6, remainder 10
2. 16 / 10 = 1, remainder 6
3. 10 / 6 = 1, remainder 4
4. 6 / 4 = 1, remainder 2
5. 4 / 2 = 2, remainder 0
6. gcd(106, 16) = 2

GCD calculation by subtraction

When finding GCD by subtraction, it is also required to reach zero. The algorithm is similar to the division method, only here, at each next stage, the subtrahend and the difference from the previous step become subtracted and reduced. The smaller number is always subtracted from the larger number. This kind of algorithm is only suitable for positive integers.

Let it be required to find GCD(108, 72):

1. 108 - 72 = 36
2. 72 - 36 = 36
3. 36 - 36 = 0
4. gcd(108, 72) = 36

Find gcd(44, 60):

1. 60 - 44 = 16
2. 44 - 16 = 28
3. 28 - 16 = 12
4. 16 - 12 = 4
5. 12 - 4 = 8
6. 8 - 4 = 4
7. 4 - 4 = 0
8. gcd(44, 60) = 4

This algorithm is sometimes described differently. Subtraction ends earlier, at the step when one number divides the other. That is, they combine subtraction with divisibility testing. Then finding the GCD for 44 and 60 will look like this:

1. Does 44 evenly divide 60? No. 60 - 44 = 16.
2. Does 16 evenly divide 44? No. 44 - 16 = 28.
3. Does 16 evenly divide 28? No. 28 - 16 = 12.
4. Does 12 evenly divide 16? No. 16 - 12 = 4.
5. Does 4 evenly divide 12? Yes. So gcd(44, 60) = 4.

Note, GCD is not a quotient, but a divisor. If in the example we divide 12 by 4, we get the quotient 3. But this is not GCD.

Proof of Euclid's algorithm

Let's take into account the fact that if one natural number from a pair divides another, then their gcd will be equal to the smaller of them. You can write it like this:

if a / b is integer, then gcd(a, b) = b. For example, gcd(15, 5) = 5.

Thus, if in the end we come to a pair of numbers, one of which divides the other, then the lesser will be the greatest common divisor for both. It is such a pair of numbers that is searched for by Euclid's algorithm: one number divides the other completely.

Second fact. It is required to prove that if one number is greater than another, then their greatest common divisor is equal to the greatest common divisor for the smaller number from the pair, and the difference between the larger and smaller numbers. This can be written like this:

if a< b, то НОД(a, b) = НОД(a, b - a).

We can prove that gcd(a, b) = gcd(a, b - a) as follows. Let b - a = c. If any number x divides a and b, then it will also divide c. After all, if a and b are different, then the divisor fits into them an integer, but a different number of times. And if you subtract one from the other, then the divisor must also fit an integer number of times into the resulting difference.

If we successively decrease a and b, then sooner or later we will come to such a value of the smaller of them, which completely divides the larger one. The smaller of such a pair will be the greatest common divisor for the original pair of natural numbers. This is what Euclid's algorithm is all about.

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 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 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 d k, 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

Euclid's algorithm

Greatest Common Divisor

Consider the following problem: it is required to write a program for determining the greatest common divisor (GCD) of two natural numbers.

Let's remember mathematics. The greatest common divisor of two natural numbers is the largest natural number by which they are evenly divisible. For example, the numbers 12 and 18 have common divisors: 2, 3, 6. The greatest common divisor is 6. This is written like this:

gcd(12, 18) = 6.

Denote the initial data as M u N. The problem statement is as follows:
Given: M, N
Find: GCD(M, N).

In this case, no additional mathematical formalization is required. The statement of the problem itself is of a formal mathematical nature. There is no formula for calculating GCD(M, N) from the values ​​of M and N. But on the other hand, quite a long time ago, long before the advent of computers, an algorithmic method for solving this problem was known. It's called Euclid's algorithm .

Idea of ​​Euclid's algorithm

The idea of ​​this algorithm is based on the property that if M>N, then

GCD(M, N) = GCD(M - N, N).

In other words, the gcd of two natural numbers is equal to the gcd of their positive difference (the modulus of their difference) and the smaller number.

It is easy to prove this property. Let K be a common divisor M u N (M > N). This means that M \u003d mK, N \u003d nK, where m, n are natural numbers, and m > n. Then M - N \u003d K (m - n), which implies that K is a divisor of the number M - N. Hence, all common divisors of the numbers M and N are divisors of their difference M - N, including the greatest common divisor.

Second obvious property:

GCD(M, M) = M.

For "manual" counting, Euclid's algorithm looks like this:

1) if the numbers are equal, then take any of them as an answer, otherwise continue the algorithm;

2) replace the larger number with the difference between the larger and smaller of the numbers;

3) return to the implementation of paragraph 1.

Consider this algorithm on the example of M=32, N=24:

The structure of the algorithm is a while-loop with nested branching. The cycle repeats until the values ​​of M and N are equal to each other. In branching, the larger of the two values ​​is replaced by their difference.

Now look at the trace table of the algorithm for the initial values ​​M = 32, N = 24.

Step	Operation	M	N	Condition
1	input M	32
2	input N		24
3	M ¹ N			32 ¹ 24, yes
4	M>N			32>24, yes
5	M:=M-N	8
6	M ¹ N			8 ¹ 24, yes
7	M>N			8>24, no
8	N:=N-M		16
9	M ¹ N			8 ¹ 16, yes
10	M>N			8>16, no
11	N:=N-M		8
12	M ¹ N			8 ¹ 8, no
13	terminal M	8
14	end

The end result is the correct one.

Program in AZ and Pascal

We write the algorithm in AI and the program in Pascal.

Questions and tasks

1. Run the Evklid program on your computer. Test it on M=32, N=24; M = 696, N = 234.

2. Write a program to find the greatest common divisor of three numbers using the following formula:

gcd(A, B, C) = gcd(gcd(A, B), C).

3. Write a program to find the least common multiple (LCM) of two numbers using the formula:

A × B = GCD(A, B) × LCM(A, B).