Division of polynomials. Euclid's algorithm.  Euclidean Algorithm Find the greatest common divisor of polynomials examples

5x5 +10x2 5x2 + 1

X3 + 7x2 + 14x + 8 1

– x2 – 3x – 2

X3 + 3x2 + 2x – x – 4

3x2 + 9x + 6

3x2 + 9x + 6

12у4 ± 18ху3 30x2y2 6y2 – 2xy – 9x2 =

– 4x3 – 12x2y2 – 11x3y + 3x4

± 4ху3 6х2у2 ± 10х3у

– 18x2y2 – x3y + 3x4

± 18х2у2 27х3у ± 45х4

– 28х3у + 48х4 = font-size:14.0pt;line-height:150%">Hence, ;

Answer: , .

Note that if the greatest common divisor of these polynomials is found, then by multiplying it by any number that is not equal to zero, we will also obtain the greatest divisor of these polynomials. This circumstance makes it possible to simplify calculations in the Euclidean algorithm. Namely, before the next division, the dividend or divisor can be multiplied by numbers selected in a special way so that the coefficient of the first term in the quotient is an integer. As shown above, multiplying the dividend and the divisor will lead to a corresponding change in the partial remainder, but such that, as a result, the GCD of these polynomials will be multiplied by some number equal to zero, which is acceptable.

Example No. 3

Reduce a fraction .

Solution

Applying the Euclidean algorithm, we obtain

X4 x3 ± 3x2 font-size:14.0pt; line-height:150%"> 4 1

2x3 + 6x2 + 3x – 2

font-size:14.0pt; line-height:150%">2) 2(x4 + x3 – 3x2 + 4) = 2x4 + 2x3 – 6x2 + 8 2x3 + 6x2 + 3x – 2

2x4 6x3 3x2 ± 2x x – 2

– 4x3 – 9x2 + 2x + 8

± 4х3 ± 12х2 ± 6х font-size:14.0pt; line-height:150%">4

3x2 + 8x + 4

6x3 font-size:14.0pt">16x2 font-size:14.0pt">8x 2x +

Euclidean algorithm for polynomials. The Euclidean algorithm allows you to find the greatest common divisor of two polynomials, i.e. the polynomial of the highest degree by which both given polynomials are divided without remainder.
The algorithm is based on the fact that for any two polynomials in the same variable, f(x) And g(x), there are such polynomials q(x) And r(x) , called the quotient and remainder, respectively, which

f(x) = g(x)∙q(x) + r(x), (*)

in this case the degree of the remainder is less than the degree of the divisor, polynomial g(x), and, in addition, according to these polynomials f(x) And g(x) the quotient and remainder are uniquely found. If the equality (*) has a remainder r(x) is equal to the zero polynomial (zero), then they say that the polynomial f(x) is divided by g(x) without remainder.
The algorithm consists of sequential division with remainder first of the first given polynomial, f(x), on the second, g(x):

f(x) = g(x)∙q 1 (x) + r 1 (x), (1)

then if r 1 (x) ≠ 0, – the second given polynomial, g(x), to the first remainder – to a polynomial r 1 (x):

g(x) = r 1 (x)∙q 2 (x) + r 2 (x), (2)

r 1 (x) = r 2 (x)∙q 3 (x) + r 3 (x), (3)

then if r 3 (x) ≠ 0, – second remainder to third:

r 2 (x) = r 3 (x)∙q 4 (x) + r 4 (x), (4)

etc. Since at each stage the degree of the next remainder decreases, the process cannot continue indefinitely, so at some stage we will definitely come to a situation where the next, n+ 1st remainder r n+ 1 equals zero:

Then the last non-zero remainder r n and will be the greatest common divisor of the original pair of polynomials f(x) And g(x).
Indeed, if due to equality ( n+ 2) substitute 0 instead r n + 1 (x) into equality ( n+ 1), then – the resulting equality r n – 1 (x) = r n (x)∙q n + 1 (x) instead of r n – 1 (x) – into equality ( n), it turns out that r n – 2 (x) = r n (x)∙q n + 1 (x) q n (x) + r n (x), i.e. r n – 2 (x) = r n (x)(q n + 1 (x) q n (x) + 1), etc. In equality (2) after substitution we obtain that g(x) = r n (x)∙Q(x), and, finally, from equality (1) – that f(x) = r n (x)∙S(x), Where Q And S– some polynomials. Thus, r n (x) is the common divisor of the two original polynomials, and the fact that it is the largest (i.e., the greatest possible degree) follows from the procedure of the algorithm.
If the greatest common divisor of two polynomials does not contain a variable (i.e. is a number), the original polynomials f(x) And g(x) are called mutually prime.

Definition. If each of two polynomials is divisible by a third polynomial, then it is called a common divisor of the first two.

Greatest Common Divisor (GCD) two polynomials is called their highest degree common divisor.

GCD can be found using irreducible factorization or using the Euclidean algorithm.

Example 40 Find the gcd of polynomials
.

Solution. Let's factor both polynomials:

From the expansion it is clear that the required GCD will be the polynomial ( X– 1).

Example 41 Find gcd of polynomials
And
.

Solution. Let's factor both polynomials.

For a polynomial
XX– 1) according to Horner’s scheme.

For a polynomial
possible rational roots are the numbers 1, 2, 3 and 6. Using substitution we verify that X= 1 is the root. Divide the polynomial by ( X– 1) according to Horner’s scheme.

Therefore, , where the expansion of the quadratic trinomial
was produced using Vieta's theorem.

Comparing the factorization of polynomials, we find that the required GCD will be the polynomial ( X– 1)(X– 2).

Similarly, you can find GCD for several polynomials.

However, the method of finding GCD by factorization is not always available. A method that allows one to find a GCD for all cases is called the Euclidean algorithm.

The scheme of the Euclid algorithm is as follows. One of two polynomials is divided by another, the degree of which is not higher than the degree of the first. Further, the dividend is each time taken to be the polynomial that served as the divisor in the previous operation, and the remainder obtained in the same operation is taken as the divisor. This process stops as soon as the remainder is zero. Let's demonstrate this algorithm with examples.

Let's look at the polynomials used in the two previous examples.

Example 42 Find gcd of polynomials
And
.

Solution. Let's divide
on
"corner":

x

Now let's divide the divisor
for the remainder X– 1:

x+ 1

Since the last division occurred without a remainder, the GCD will be X– 1, i.e. the polynomial used as a divisor in this division.

Example 43 Find gcd of polynomials
And
.

Solution. To find the GCD we will use the Euclidean algorithm. Let's divide
on
"corner":

1

Let's make a second division. To do this we would have to divide the previous divisor
for the remainder
, but since
=
, for convenience we will divide the polynomial
not on
, and on
. Such a replacement will not change the solution to the problem, since the gcd of a pair of polynomials is determined up to a constant factor. We have:

The remainder turned out to be equal to zero, which means the last divisor, i.e., a polynomial

and will be the desired GCD.

1. Fractional rational functions

Definitions and statements for 2.5 can be found in .

A fractional rational function with real coefficients is called an expression of the form , Where
And
- polynomials.

A fractional-rational function (hereinafter we will call it a “fraction”) is called correct, if the degree of the polynomial in the numerator is strictly less than the degree of the polynomial in the denominator. Otherwise it is called wrong.

The algorithm for converting an improper fraction to a proper fraction is called “isolating the whole part.”

Example 44 Select the whole part of the fraction:
.

Solution. In order to isolate the whole part of a fraction, you need to divide the numerator of the fraction by its denominator. Divide the numerator of this fraction by its denominator using a “corner”:

Since the degree of the resulting polynomial is less than the degree of the divisor, the division process is completed. As a result:

=
. The resulting fraction
is correct.

Fraction of the form
is called simplest if φ( x ) is an irreducible polynomial, and the degree
less than the degree φ( x ).

Comment. Please note that the powers of the numerator and the irreducible polynomial in the denominator are compared (ignoring the power of α).

For fractions with real coefficients, there are 4 types of simple fractions:

Any proper fraction can be represented as a sum of simple fractions, the denominators of which are all possible divisors
.

Algorithm for decomposing a fraction into its simplest form:

If the fraction is improper, then we select the whole part, and we decompose the resulting proper fraction into simple ones.

We factor the denominator of the proper fraction into factors.

We write a proper fraction as a sum of simple fractions with undetermined coefficients.

We bring the sum of the fractions on the right side to a common denominator.

Finding the undetermined coefficients:

Either by equating the coefficients for the same powers of the left and right reduced numerators;

Or by substituting specific (usually the roots of their common denominator) values x.

We write the answer taking into account the whole part of the fraction.

Example 45 Break it down to its simplest
.

Solution. Since this fractional-rational function is incorrect, we select the whole part:

1

= 1 +
.

Let's expand the resulting fraction
to the simplest. First, let's factorize the denominator. To do this, we find its roots using the standard formula:

Let us write down the expansion of a fractional rational function into its simplest forms, using undetermined coefficients:

Let's bring the right side of the equality to a common denominator:

We compose a system by equating the coefficients for the same powers in the numerators of the left and right fractions:

Answer:
.

Example 46 Break it down to its simplest
.

Solution. Since this fraction is proper (that is, the degree of the numerator is less than the degree of the denominator), there is no need to highlight the whole part. Let's factorize the denominator of the fraction:

Let us write down the decomposition of this fraction into the simplest ones, using undetermined coefficients:

According to the statement, the denominators of the simplest fractions must be all kinds of divisors of the denominator of the fraction:

. (2.2) It would be possible to create a system of equations by equating the numerators of the left and right fractions, but in this example the calculations would be too cumbersome. The following technique will help to simplify them: we substitute the roots of the denominator into the numerators one by one.

At x = 1:

At X= ‑1:

Now to determine the remaining coefficients A And WITH It will be enough to equate the coefficients of the highest degree and the free terms. They can be found without opening the parentheses:

The left side of the first equation contains 0, since the numerator of the left fraction in (2.2) does not contain the term with , and in the right fraction the term with coefficient A + C. On the left side of the second equation there is 0, since in the numerator of the left fraction in (2.2) the free term is equal to zero, and in the numerator of the right fraction in (2.2) the free term is equal to (‑ A + B + C + D). We have:

Answer:
.

1. Euclidean algorithm

If each of two polynomials is divisible by a third polynomial, then this third polynomial is called a common divisor of the first two.

The greatest common divisor (GCD) of two polynomials is their common divisor of the greatest degree.

Note that any number not equal to zero is a common divisor of any two polynomials. Therefore, any number not equal to zero is called a trivial common divisor of these polynomials.

The Euclidean algorithm proposes a sequence of actions that either leads to finding the gcd of two given polynomials, or shows that such a divisor in the form of a polynomial of the first or higher degree does not exist.

The Euclidean algorithm is implemented as a sequence of divisions. In the first division, the polynomial of the greater degree is treated as the dividend, and the lesser - as the divisor. If the polynomials for which the GCD is found have the same degrees, then the dividend and divisor are chosen arbitrarily.

If, during the next division, the polynomial in the remainder has a degree greater than or equal to 1, then the divisor becomes the dividend and the remainder becomes a divisor.

If the next division of the polynomials results in a remainder equal to zero, then the gcd of these polynomials has been found. It is the divisor of the last division.

If, during the next division of polynomials, the remainder turns out to be a number not equal to zero, then for these polynomials there are no gcds other than trivial ones.

Example No. 1

Reduce a fraction.

2. Possibilities for simplifying GCD calculations in the Euclidean algorithm

When multiplying the dividend by a number not equal to zero, the quotient and remainder are multiplied by the same number.

Proof

Let P be the dividend, F the divisor, Q the quotient, R the remainder. Then,

Multiplying this identity by the number 0, we get

where the polynomial P can be considered as the dividend, and the polynomials Q and R as the quotient and remainder obtained by dividing the polynomial P by the polynomial F. Thus, when multiplying the dividend by the number 0, the quotient and remainder are also multiplied by, h.t. d

Consequence

Multiplying the divisor by the number 0 can be thought of as multiplying the dividend by the number.

Therefore, when a divisor is multiplied by a number, 0 is the quotient and the remainder is multiplied by.

Example No. 2

Find the quotient Q and remainder R when dividing polynomials

division polynomial algorithm Euclidean

To go to integer coefficients in the dividend and divisor, we multiply the dividend by 6, which will lead to the multiplication of the desired quotient Q and the remainder R by 6. After that, we multiply the divisor by 5, which will lead to the multiplication of the quotient 6Q and the remainder 6R by. As a result, the quotient and remainder obtained by dividing polynomials with integer coefficients will differ by a factor of several times from the desired values ​​of the quotient Q and remainder R obtained by dividing these polynomials.

Hence, ;

Note that if the greatest common divisor of these polynomials is found, then by multiplying it by any number that is not equal to zero, we will also obtain the greatest divisor of these polynomials. This circumstance makes it possible to simplify calculations in the Euclidean algorithm. Namely, before the next division, the dividend or divisor can be multiplied by numbers selected in a special way so that the coefficient of the first term in the quotient is an integer. As shown above, multiplying the dividend and the divisor will lead to a corresponding change in the partial remainder, but such that, as a result, the GCD of these polynomials will be multiplied by some number equal to zero, which is acceptable.

BASIC INFORMATION FROM THEORY

Definition 4.1.

The polynomial j(x) in P[x] is called common divisor polynomials g(x) and f(x) from P[x] if f(x) and g(x) are divisible by j(x) without remainder.

Example 4.1. Given two polynomials: (x) g(x)= x 4 − 3x 3 − 4x 2 + 2x + 2 О R[x]. The common divisors of these polynomials are: j 1 (x) = x 3 − 4x 2 + 2 = О R[x], j 2 (x) =(x 2 − 2x − 2) О R[x], j 3 (x) =(x − 1) О R[x], j 4 (x) = 1 О R[x]. (Check!)

Definition 4.2.

Greatest common divisornonzero polynomials f(x) and g(x) from P[x] is a polynomial d(x) from P[x] that is their common divisor and is itself divisible by any other common divisor of these polynomials.

Example 4.2. For the polynomials from Example 4.1. f(x)= x 4 − 4x 3 + 3x 2 + 2x − 6 О R[x], g(x)= x 4 − 3x 3 − 4x 2 + 2x + 2 О R[x] the greatest common divisor is the polynomial d(x) = j 1 (x) = x 3 − 4x 2 + 2 О R[x], since this is a polynomial d(x) is divided by all their other common divisors j 2 (x), j 3 (x),j4(x).

The greatest common divisor (GCD) is indicated by the symbol:

d(x) = (f(x), g(x)).

A greatest common divisor exists for any two polynomials f(x),g(x) О P[x] (g(x) No. 0). Its existence determines Euclidean algorithm which is as follows.

We divide f(x) on g(x). The remainder and quotient obtained by division are denoted by r 1 (x) And q 1 (x). Then if r 1 (x)¹ 0, divide g(x) on r 1 (x), we get the remainder r2(x) and private q2(x) etc. Degrees of resulting residues r 1 (x), r 2 (x),... will decrease. But the sequence of non-negative integers is limited from below by the number 0. Consequently, the division process will be finite, and we will arrive at the remainder r k (x), into which the previous remainder will be completely divided r k – 1 (x). The entire division process can be written as follows:

f(x)= g(x) × q 1 (x) + r 1 (x), deg r 1 (x)< deg g(x);

g(x)= r 1 (x)× q 2 (x) + r 2 (x), deg r2(x) < deg r 1(x);

. . . . . . . . . . . . . . . . . . . . . . . .

r k – 2 (x)= r k – 1 (x)× qk(x) + r k (x), deg r k (x)< deg r k – 1 (x);

r k – 1 (x) = r k (x) × q k +1 (x).(*)

Let's prove that r k (x) will be the greatest common divisor of the polynomials f(x) And g(x).

1) Let us show that r k (x) is common divisor data polynomials.

Let us turn to the penultimate equality:

r k –-2 (x)= r k –-1 (x)× qk(x) + r k (x), or r k –-2 (x)= r k (x) × q k +1 (x) × qk(x) + r k (x).

Its right side is divided into r k (x). Therefore, the left-hand side is also divisible by r k (x), those. r k –-2 (x) divided by r k (x).

r k –- 3 (x)= r k –- 2 (x)× q k – 1 (x) + r k –- 1 (x).

Here r k –- 1 (x) And r k –- 2 (x) are divided into r k (x), it follows that the sum on the right side of the equality is divisible by r k (x). This means that the left side of the equality is also divisible by r k (x), those. r k –- 3 (x) divided by r k (x). Moving in this way successively upward, we obtain that the polynomials f(x) And g(x) are divided into r k (x). Thus, we showed that r k (x) is common divisor polynomial data (definition 4.1.).

2) Let us show that r k (x) divided by any other common divisor j(x) polynomials f(x) And g(x), that is greatest common divisor these polynomials .

Let's turn to the first equality: f(x)=g(x) × q 1 (x) + r 1 (x).

Let d(x)– some common divisor f(x) And g(x). Then, according to the divisibility properties, the difference f(x)–g(x) × q 1 (x) also divided into d(x), that is, the left side of the equality f(x)–g(x) × q 1 (x)= r 1 (x) divided by d(x). Then r 1 (x) will be divided by d(x). Continuing the reasoning in a similar way, successively descending through the equalities, we obtain that r k (x) divided by d(x). Then, according to definition 4.2.r k (x) will be greatest common divisor polynomials f(x) And g(x): d(x) = (f(x), g(x)) = r k (x).

Greatest common divisor of polynomials f(x) And g(x) is unique up to a factor - a polynomial of degree zero, or, one might say, up to association(definition 2.2.).

Thus, we have proven the theorem:

Theorem 4.1. /Euclidean algorithm/.

If for polynomials f(x),g(x) О P[x] (g(x)¹ 0) the system of equalities and inequalities is correct(*), then the last non-zero remainder will be the greatest common divisor of these polynomials.

Example 4.3. Find the greatest common divisor of polynomials

f(x)= x 4 + x 3 +2x 2 + x + 1 and g(x)= x 3 –2x 2 + x –2.

Solution.

1 step. 2 step.

Let us write the division steps in the form of a system of equalities and inequalities, as in (*) :

f(x)= g(x) × q 1 (x) + r 1 (x), deg r 1 (x)< deg g(x);

g(x)= r 1 (x)× q2(x).

According to Theorem 4.1./Euclidean algorithm/ the last non-zero remainder r 1 (x) = 7x 2 + 7 will be the greatest common divisor d(x) these polynomials :

(f(x), g(x)) = 7x 2 + 7.

Since divisibility in a polynomial ring is defined up to association ( Property 2.11.) , then as GCD we can take not 7x 2 + 7, but ( 7x 2 + 7) = x 2 + 1.

Definition 4.3.

The greatest common divisor with leading coefficient 1 will be called normalized greatest common divisor.

Example 4.4. In example 4.2. the greatest common divisor was found d(x) = (f(x), g(x)) = 7x 2 + 7 polynomials f(x)= x 4 + x 3 +2x 2 + x + 1 and g(x)= x 3 –2x 2 + x –2. Replacing it with its associated polynomial d1(x)= x 2 + 1, we obtain the normalized greatest common divisor of these polynomials( f(x), g(x)) = x 2 + 1.

Comment. Using the Euclidean algorithm to find the greatest common divisor of two polynomials, we can draw the following conclusion. Greatest common divisor of polynomials f(x) And g(x) does not depend on whether we consider f(x) And g(x) over the field P or over its extension P'.

Definition 4.4.

Greatest common divisorpolynomials f 1 (x), f 2 (x), f 3 (x),… f n (x) Î P[x] is called such a polynomial d(x)Î P[x], which is their common divisor and is itself divisible by any other common divisor of these polynomials.

Since Euclid's algorithm is only suitable for finding the greatest common divisor of two polynomials, to find the greatest common divisor of n polynomials, we need to prove the following theorem.