• 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

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 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 more replace 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 is 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 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.

Ask a question about modern education, express an idea or solve an urgent problem, you can Education Forum

This article is about finding the greatest common divisor (gcd) two and more numbers. First, consider the Euclid algorithm, it allows you to find the GCD of two numbers. After that, we will dwell on a method that allows us to calculate the GCD of numbers as a product of their common prime factors. Next, we will deal with finding the greatest common divisor of three or more numbers, and also give examples of calculating the GCD of negative numbers.

Page navigation.

Euclid's algorithm for finding GCD

Note that if we had turned to the prime number table from the very beginning, we would have found out that the numbers 661 and 113 are prime, from which we could immediately say that their greatest common divisor is 1.

Answer:

gcd(661, 113)=1 .

Finding GCD by Factoring Numbers into Prime Factors

Consider another way to find the GCD. The greatest common divisor can be found by factoring numbers into prime factors. Let's formulate the rule: GCD of two integers positive numbers a and b is equal to the product of all common prime factors in the expansions of the numbers a and b into prime factors.

Let us give an example to explain the rule for finding the GCD. Let us know the expansions of the numbers 220 and 600 into prime factors, they have the form 220=2 2 5 11 and 600=2 2 2 3 5 5 . Common prime factors involved in the expansion of the numbers 220 and 600 are 2 , 2 and 5 . Therefore gcd(220, 600)=2 2 5=20 .

Thus, if we decompose the numbers a and b into prime factors and find the product of all their common factors, then this will find the greatest common divisor of the numbers a and b.

Consider an example of finding the GCD according to the announced rule.

Example.

Find the greatest common divisor of 72 and 96.

Solution.

Let's factorize the numbers 72 and 96:

That is, 72=2 2 2 3 3 and 96=2 2 2 2 2 3 . Common prime factors are 2 , 2 , 2 and 3 . So gcd(72, 96)=2 2 2 3=24 .

Answer:

gcd(72, 96)=24 .

In conclusion of this section, we note that the validity of the above rule for finding the gcd follows from the property of the greatest common divisor, which states that 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

Finding the greatest common divisor of three or more numbers can be reduced to successively finding the gcd of two numbers. We mentioned this when studying the properties of GCD. There we formulated and proved the theorem: the greatest common divisor of several numbers a 1 , a 2 , …, a k is equal to the number d k , which is found during sequential calculation

Let's see how the process of finding the GCD of several numbers looks like by considering the solution of the example.

Example.

Find the greatest common divisor of the four numbers 78 , 294 , 570 and 36 .

Solution.

In this example a 1 =78 , a 2 =294 , a 3 =570 , a 4 =36 .

First, using the Euclid algorithm, we determine the greatest common divisor d 2 of the first two numbers 78 and 294 . When dividing, we get the equalities 294=78 3+60 ; 78=60 1+18 ; 60=18 3+6 and 18=6 3 . Thus, d 2 =GCD(78, 294)=6 .

Now let's calculate d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). Again we apply the Euclid algorithm: 570=6·95 , therefore, d 3 =GCD(6, 570)=6 .

It remains to calculate d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). Since 36 is divisible by 6, then d 4 \u003d GCD (6, 36) \u003d 6.

Thus, the greatest common divisor of the four given numbers is d 4 =6 , that is, gcd(78, 294, 570, 36)=6 .

Answer:

gcd(78, 294, 570, 36)=6 .

Decomposing numbers into prime factors also allows you to calculate the GCD of three or more numbers. In this case, the greatest common divisor is found as the product of all common prime factors of the given numbers.

Example.

Calculate the GCD of the numbers from the previous example using their prime factorizations.

Solution.

We decompose the numbers 78 , 294 , 570 and 36 into prime factors, we get 78=2 3 13 , 294=2 3 7 7 , 570=2 3 5 19 , 36=2 2 3 3 . The common prime factors of all given four numbers are the numbers 2 and 3. Hence, GCD(78, 294, 570, 36)=2 3=6.

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 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 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 English language"greatest common divisor" is spelled "greatest common divisor", and its common notation is :

(here "" denotes divisibility, i.e. "" stands for "divides")

When one of the numbers is equal to zero and the other is non-zero, their greatest common divisor, by definition, will be this second number. When both numbers are zero, the result is undefined (any infinitely large number will do), we put in this case the greatest common divisor zero. Therefore, we can talk about such a rule: if one of the numbers is equal to zero, then their greatest common divisor is equal to the second number.

Euclid's algorithm, discussed below, solves the problem of finding the greatest common divisor of two numbers and for .

This algorithm was first described in Euclid's Elements (circa 300 BC), although it is quite possible that this algorithm has an earlier origin.

Algorithm

The algorithm itself is extremely simple and is described by the following formula:

Implementation

int gcd (int a, int b) ( if (b == 0 ) return a; else return gcd (b, a % b) ; )

Using the C++ ternary conditional operator, the algorithm can be written even shorter:

int gcd (int a, int b) ( return b ? gcd (b, a % b) : a; )

Finally, here is the non-recursive form of the algorithm:

int gcd (int a, int b) ( while (b) ( a % = b; swap (a, b) ; ) return a; )

Correctness proof

First, note that with each iteration of the Euclidean algorithm, its second argument is strictly decreasing, therefore, since it is non-negative, then the Euclidean algorithm always ends.

For correctness proofs we need to show that for any >.

Let us show that the value on the left side of the equality is divisible by the real one on the right, and the value on the right is divisible by the value on the left. Obviously, this will mean that the left and right parts are the same, which will prove the correctness of Euclid's algorithm.

Denote . Then, by definition, and .

But then it follows:

So, remembering the statement , we get the system:

Let us now use the following simple fact: if for some three numbers is satisfied: and , then it is executed and: . In our situation, we get:

Or, substituting its definition as , we get:

So, we have done half of the proof: we have shown that the left side divides the right one. The second half of the proof is done in a similar way.

Working hours

The running time of the algorithm is estimated Lame's theorem, which establishes a surprising connection between the Euclid algorithm and the Fibonacci sequence:

If > and for some , then Euclid's algorithm will make at most recursive calls.

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 zero, the algorithm ends with the number 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 (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)).)