Euclid's algorithm is an algorithm for finding the greatest common divisor (gcd) of a pair of integers.

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 the given two numbers. Simply put, this is the big number, by which the two numbers for which the gcd is sought can be divided without 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 more 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)

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'll set the greatest common divisor to zero in this case. 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 it holds: and , then it holds 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.

The largest common de-li-tel of two-tu-ral-numbers $a$ and $b$ - $gcd(a, b)$ - is the largest number , on some swarm the numbers $a$ and $b$ are de-lyat-Xia without a trace.

For finding $ GCD (a, b) $, you can-but-step-drink the following natural way: de-live both numbers la by powers of prime numbers: $a = 2^(\alpha_1) \cdot 3^(\alpha_2) \cdot \ldots \cdot p^(\alpha_n)_n$ , $b = 2 ^(\beta_1) \cdot 3^(\beta_2) \cdot \ldots \cdot p^(\beta_n)_n$ , ($\alpha_k$ and $\beta_k$ can be null). Then $$gcd(a, b) = 2^(\min(\alpha_1, \beta_1)) \cdot 3^(\min(\alpha_2, \beta_2)) \cdot \ldots \cdot p^(\ min(\alpha_n, \beta_n))_n.$$ $ get it: $2625 = 2^0 \cdot 3^1 \cdot 5^3 \cdot 7^1, 8100 = 2^2 \cdot 3^4 \cdot 5^2 \cdot 7^0$, means $gcd(2625, 8100) = 2^0 \cdot 3^1 \cdot 5^2 \cdot 7^0 = 75$.

The essential shortcoming of this way is that dividing a large number into simple multipliers is not so pro- a hundred, but more precisely - not so fast.

Euclid in the 7th book “Beginning” describes the al-go-rhythm of finding the “general measure of two numbers”. Al-go-rhythm describe-san geo-met-ri-che-ski, as on-hod-de-tion of the general measure of two cuts. It comes down to “after-to-va-tel-no-mu from-nya-ty” from more from-cut-less from-cut. Now this al-go-rhythm from-ve-walls is like an al-go-rhythm Ev-kli-da for finding the most-bol-she-go-go-de-li-te -la two on-tu-ral-nyh chi-villages.

The basic idea, on some basis, os-no-van al-go-rhythm, consists in the fact that $GCD$ chi-sat $a$ and $b$ are equal $ GCD$ chi-sat $b$ and $a-b$. From-here-yes, it follows that if you pour $a$ onto $b$ with a remainder, i.e. put in the form $a = b \cdot q + r$, then $gcd(a, b) = gcd(b, r)$.

Let's describe the beautiful geo-met-ri-che-skuyu inter-ter-pre-ta-tion al-go-rit-ma, inter-active-tiv-naya re-a-li-za -tion of someone-swarm before-lo-the-on-the-she.

In a rectangle-no-ke with side lengths $a$ and $b$ beyond the edge-shi-va-em max-si-mal-but-possible square . In the rest of the rectangle-mo-coal-no-ke again for-the-edge-shi-va-em is a mak-si-mal-but possible square. And so on and on until the whole outgoing rectangle is not over-painted. The length of a hundred-ro-ny sa-mo-go-ma-lazi-ko-th square-ra-ta and will be equal to $ GCD (a, b) $.

More in-fraction-but geo-met-ri-che-sky in-ter-pre-ta-tion op-sa-on the same, and para-ral-lel-but with-ve-de-but arith-me-ti-che-description of al-go-rit-ma Ev-kli-da.

In-ter-pre-ta-tion al-go-rit-ma	Al-go-rhythm Ev-cli-da
In a rectangle with a length of sides $a$ and $b$ $(a \gt b)$ beyond the edges of the si-mal-but-th-me-ra (with a hundred $b$). This operation is repeated for a non-painted part as much as possible.	The larger number $a$ is de-lit with the remainder on the smaller number $b$: $a = b \cdot q_1 + r_1$.
If such squares cover the entire rectangle, then the number $b$ is $GCD$.	If the remainder of $r_1$ from the de-le-tion of ra-veins is nu-lu, then the smaller number $b$ is $GCD$.
If there remains a rectangle-nick (with a hundred-ro-on-mi $b$ and $r_1$), it has the most-pain- neck possible number of squares of max-si-mal-but-th-measure-ra (with a side of $r_1$).	If the remainder of $r_1$ is not equal to zero, then the smaller number $b$ is de-lit with the remainder on $r_1$: $b = r_1 \cdot q_2 + r_2 $.
If a square with a hundred $r_1$ covers the whole rectangle, then $r_1$ is $GCD$.	If in the result of the second de-le-tion the remainder of $r_2$ is equal to zero, then $r_1$ is $GCD$.
If there is a rectangle-nick (with a hundred-ro-on-mi $r_1$ and $r_2$), it has the most-pain- neck possible number of squares of max-si-small-size-me-ra (with a side of $r_2$).	If the remainder of $r_2$ during the second de-le-ni is not equal to zero, then $r_1$ is de-lit by $r_2$: $r_1 = r_2 \cdot q_3 + r_3$ .
And so on and on until the whole right-angle-nick is not square-ra-ta-mi. (Sooner or later, this will happen, because a hundred square-ra-ts will reduce-sha-ut-sya and in any case, you can half-thread of the remaining right-mo-coal-nick quad-ra-ta-mi with a hundred-ro-one unit).	And so on and so on until the rest of the current $r_n$ is equal to zero (ra-but or later it will happen, because -ku the rest-ki reduce-sha-ut-sya).
The length of one hundred mi-no-small-but-go square is the $ GCD $ of the starting numbers.	The last not equal to zero residual current $r_(n-1)$ is the $GCD$ of the original numbers.

Al-go-rhythm Ev-kli-yes is a powerful instrument, used in solving various personal problems dachas. For example, he uses to solve equations in integer numbers, representing numbers in the form of an infinity -break-nyh (chain-th) draw-beat, it can be generalized for finding the most-big-she-go-go-de-li-te-la of two multiple go-member.

Literature

Euclid. Na-cha-la Ev-cli-da. Books VII, X. - M.-L.: GITTL, 1950.

R. Courant, G. Robins. What is that ma-te-ma-ti-ka? - M.: MTsNMO, 2010.

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

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