Euclidean algorithm for finding nodes of two polynomials.  Euclid's algorithm. Lab Options

Let nonzero polynomials f(x) and φ(x) be given. If the remainder of dividing f(x) by φ(x) is zero, then the polynomial φ(x) is called the divisor of the polynomial f(x). The following assertion holds: the polynomial φ(x) will be a divisor of the polynomial f(x) if and only if there exists a polynomial ψ(x) satisfying the equality f(x)=φ(x)ψ(x). A polynomial φ(x) is called a common divisor of arbitrary polynomials f(x) and g(x) if it is a divisor of each of these polynomials. According to the properties of divisibility, the number of common divisors of the polynomials f(x) and g(x) includes all zero-degree polynomials. If these polynomials have no other common divisors, then they are called coprime and write (f(x), g(x))=1. In the general case, the polynomials f(x) and g(x) may have common divisors depending on x.

As for integers, the concept of their greatest common divisor is introduced for polynomials. The greatest common divisor of non-zero polynomials f(x) and g(x) is their common divisor d(x), which is divisible by any common divisor of these polynomials. The greatest common divisor of the polynomials f(x) and g(x) is denoted by gcd, d(x), (f(x), g(x)). Note that this definition of GCD also takes place for integers, although another one, known to all students, is more often used.

This definition raises a number of questions:

1. Is there a GCD for arbitrary non-zero polynomials f(x) and g(x)?

2. How to find the GCD of polynomials f(x) and g(x)?

3. How many greatest common divisors do the polynomials f(x) and g(x) have? And how to find them?

There is a way to find the gcd of integers called the sequential division algorithm or Euclid's algorithm. It is also applicable to polynomials and consists in the following.

Euclid's algorithm. Let polynomials f(x) and g(x) be given, degree f(x) ≥ degree g(x). We divide f(x) by g(x), we get the remainder r 1 (x). We divide g(x) by r 1 (x), we get the remainder r 2 (x). We divide r 1 (x) by r 2 (x). So we continue the division until the division is complete. That remainder r k (x), which completely divides the previous remainder r k -1 (x), and will be the greatest common divisor of the polynomials f (x) and g (x).

Let us make the following remark, useful in solving examples. Applying the Euclidean algorithm to polynomials to find the gcd, we can, in order to avoid fractional coefficients, multiply the dividend or reduce the divisor by any number not equal to zero, and not only starting any of the successive divisions, but also in the process of this division itself. This will lead to a distortion of the quotient, but the remainders of interest to us will acquire only a certain factor of zero degree, which, as we know, is allowed when looking for divisors.

Example 1 Find the GCD of polynomials f(x)=x 3 –x 2 –5x–3,
g(x)=x 2 +x–12. Divide f(x) by g(x):

The first remainder of r 1 (x) after the reduction by 9 will be x-3. We divide g(x) by r 1 (x):

.

The division was complete. Therefore, r 1 (x) \u003d x–3 is the GCD of the polynomials x 3 –x 2 –5x–3 and x 2 +x–12.

Example 2 Find the gcd of polynomials f(x)=3x 3 +2x 2 –4x–1,
g(x)=5x 3 –3x 2 +2x–4. Multiply f(x) by 5 and divide 5f(x) by g(x):

The first remainder r 1 (x) will be 19x 2 -26x + 7. Divide g(x) by the first remainder after multiplying g(x) by 19:

Multiply by 19 and continue dividing:

We reduce by 1955 and get the second remainder r 2 (x) = x-1. We divide r 1 (x) by r 2 (x):

.

The division is complete, therefore, r 2 (x)=x-1 is the GCD of the polynomials f(x) and g(x).

Example 3 Find the gcd of polynomials f(x)=3x 3 –x 2 +2x–4,
g(x)=x 3 -2x 2 +1.

. .

.

Answer:(f(x), g(x))=х–1.

This way of finding the gcd shows that if the polynomials f(x) and g(x) have both rational or real coefficients, then the coefficients of their greatest common divisor will also be rational or, respectively, real.

The polynomials f(x), g(x) and d(x) are related by the following relation, which is often used in various questions and is described by the theorem.

If d(x) is the greatest common divisor of the polynomials f(x) and g(x), then one can find polynomials u(x) and v(x) such that f(x)u(x)+g(x)v (x)=d(x). In this case, we can assume that if the degrees of the polynomials f(x) and g(x) are greater than zero, then the degree of u(x) is less than the degree of g(x), and the degree of v(x) is less than the degree of f(x).

Let us show by example how to find polynomials u(x) and v(x) for given polynomials f(x) and g(x).

Example 4 Find polynomials u(x) and v(x) such that f(x)u(x)+g(x)v(x)=d(x) if

A) f(x)=x 4 -3x 3 +1, g(x)=x 3 -3x 2 +1;

B) f (x) \u003d x 4 -x 3 + 3x 2 -5x + 2, g (x) \u003d x 3 + x-2.

A. We find the GCD of the polynomials f(x) and g(x) using the Euclid algorithm, only now in the process of division it is impossible to reduce and multiply by suitable numbers, as we did in examples 1, 2, 3.

(1) (2)

Thus, the common divisor of the polynomials f(x) and g(x) is –1.

According to the division made, we write the equalities:

f(x)=g(x)х+(–х+1) (1 *)

g (x) \u003d (-x + 1) (-x 2 + 2x + 2) -1. (2*)

From equality (2 *) we express d(x)= –1=g(x)–(–x+1)(–x 2 +2x+2). From equality (1 *) we find –х+1=f(x)–g(x)х and substitute its value into equality (2*): d(x)= –1=g(x)–(f(x )–g(x)х)(–x 2 +2x+2).

Now we group the terms on the right side with respect to f(x) and g(x):

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

Therefore, u(x)=x 2 –2x–2, v(x)= –x 3 +2x 2 +2x+1.

The greatest common divisor of the polynomials f(x) and g(x) is the 2x-2 polynomial. We express it using equalities (1) and (2):

Answer:

OPTIONS OF LABORATORY WORK

Option 1

1. Find GCD of polynomials:

a) х 4 –2х 3 –х 2 –4х–6, 2х 4 –5х 3 +8х 2 –10х+8.

b) (x–1) 3 (x+2) 2 (2x+3), (x–1) 4 (x+2)x.

f (x) \u003d x 6 -4x 5 + 11x 4 -27x 3 + 37x 2 -35x + 35,

g(x)=x 5 -3x 4 +7x 3 -20x 2 +10x-25.

Option 2

1. Find GCD of polynomials:

a) x 4 -3x 3 -3x 2 + 11x-6, x 4 -5x 3 + 6x 2 + x-3.

b) (2x+3) 3 (x-2) 2 (x+1) and its derivative.

2. Find polynomials u(x) and v(x) so that f(x)u(x)+g(x)v(x)=d(x), d(x)=(f(x), g(x)) if

f(x)=3x 7 +6x 6 -3x 5 +4x 4 +14x 3 -6x 2 -4x+4, g(x)=3x 6 -3x 4 +7x 3 -6x+2.

Option 3

1. Find GCD of polynomials:

a) 2x 4 + x 3 + 4x 2 -4x-3, 4x 4 -6x 3 -4x 2 + 2x + 1.

b) (x + 1) 2 (2x + 4) 3 (x + 5) 5, (x-2) 2 (x + 2) 4 (x-1).

2. Find polynomials u(x) and v(x) so that f(x)u(x)+g(x)v(x)=d(x), d(x)=(f(x), g(x)) if

f (x) \u003d 3x 3 -2x 2 + 2x + 2, g (x) \u003d x 2 -x + 1.

Option 4

1. Find GCD of polynomials:

a) 3x 4 -8 3 + 7x 2 -5x + 2, 3x 4 -2x 3 -3x 2 + 17x-10.

b) (x + 7) 2 (x-3) 3 (2x + 1) and its derivative.

2. Find polynomials u(x) and v(x) so that f(x)u(x)+g(x)v(x)=d(x), d(x)=(f(x), g(x)) if

f (x) \u003d x 4 -x 3 -4x 2 + 4x + 1, g (x) \u003d x 2 -x-1.

Option 5

1. Find GCD of polynomials:

a) 2x 4 -3x 3 -x 2 + 3x-1, x 4 + x 3 -x-1.

b) x 4 (x-1) 2 (x + 1) 3, x 3 (x-1) 3 (x + 3).

2. Find polynomials u(x) and v(x) so that f(x)u(x)+g(x)v(x)=d(x), d(x)=(f(x), g(x)) if

f (x) \u003d 3x 5 + 5x 4 -16x 3 -6x 2 -5x-6, g (x) \u003d 3x 4 -4x 3 -x 2 -x-2.

Option 6

1. Find GCD of polynomials:

a) x 4 -2x 3 + 4x 2 -2x + 3, x 4 + 5x 3 + 8x 2 + 5x + 7.

b) x 3 (x + 1) 2 (x-1) and its derivative.

2. Find polynomials u(x) and v(x) so that f(x)u(x)+g(x)v(x)=d(x), d(x)=(f(x), g(x)) if

f (x) \u003d x 5 -5x 4 -2x 3 + 12x 2 -2x + 12, g (x) \u003d x 3 -5x 2 -3x + 17.

Option 7

1. Find GCD of polynomials:

a) x 4 + 3x 3 -3x 2 + 3x-4, x 4 + 5x 3 + 5x 2 + 5x + 4.

b) (2x + 1) (x-8) (x + 1), (x 3 +1) (x-1) 2 x 3.

2. Find polynomials u(x) and v(x) so that f(x)u(x)+g(x)v(x)=d(x), d(x)=(f(x), g(x)) if

f(x)=4x 4 -2x 3 -16x 2 +5x+9, g(x)=2x 3 -x 2 -5x+4.

Option 8

1. Find GCD of polynomials:

a) x 4 -3x 3 -2x 2 + 4x + 6, 2x 4 -6x 3 + 2x 2 -7x + 3.

b) (x 3 -1) (x 2 -1) (x 2 +1), (x 3 +1) (x-1) (x 2 +2).

2. Find polynomials u(x) and v(x) so that f(x)u(x)+g(x)v(x)=d(x), d(x)=(f(x), g(x)) if

f (x) \u003d 2x 4 + 3x 3 -3x 2 -5x + 2, g (x) \u003d 2x 3 + x 2 -x-1.

Option 9

1. Find GCD of polynomials:

a) 2x 4 + x 3 -5x 2 + 3x + 2, 3x 4 + 8x 3 + 3x 2 -3x-2.

b) (x 3 +1) (x + 1) 2 (2x + 3) and its derivative.

2. Find polynomials u(x) and v(x) so that f(x)u(x)+g(x)v(x)=d(x), d(x)=(f(x), g(x)) if

f (x) \u003d 3x 4 -5x 3 + 4x 2 -2x + 1, g (x) \u003d 3x 3 -2x 2 + x-1.

Option 10

1. Find GCD of polynomials:

a) x 4 -5x 3 + 7x 2 -3x + 2, 2x 4 -x 3 -7x 2 + 3x-2.

b) (x + 1) (x 2 -1) (x 3 +1), (x 3 -1) (x 2 + x) x.

2. Find polynomials u(x) and v(x) so that f(x)u(x)+g(x)v(x)=d(x), d(x)=(f(x), g(x)) if

f (x) \u003d x 5 + 5x 4 + 9x 3 + 7x 2 + 5x + 3, g (x) \u003d x 4 + 2x 3 + 2x 2 + x + 1.

2015-2020 lektsii.org -

1. Euclid's algorithm

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

The greatest common divisor (gcd) of two polynomials is their common divisor more.

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

Euclid's algorithm suggests 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 greater degree does not exist.

Euclid's algorithm is implemented as a sequence of divisions. In the first division, a polynomial of a greater degree is considered as a dividend, and a polynomial of a lesser degree is considered as a divisor. If the polynomials for which the GCD is found have the same degree, then the dividend and the divisor are chosen arbitrarily.

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

If at the next division of polynomials a remainder equal to zero is obtained, then the gcd of these polynomials is found. It is the divisor at the last division.

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

Example #1

Reduce fraction.

2. Possibilities of simplifying GCD calculations in the Euclid algorithm

When multiplying a dividend by a non-zero number, 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 the remainder, obtained by dividing the polynomial P by the polynomial F. Thus, when multiplying the dividend by the number 0, the quotient and the remainder are also multiplied by, h.t. d

Consequence

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

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

Example #2

Find the quotient Q and the remainder R when dividing polynomials

division polynomial algorithm euclid

To go to the dividend and divisor to integer coefficients, multiply the dividend by 6, which will multiply the desired quotient Q and the remainder R by 6. After that, multiply the divisor by 5, which will multiply 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 from the desired values ​​of the quotient Q and the remainder R obtained by dividing these polynomials.

Consequently, ;

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 Euclid 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, the multiplication of the dividend and the divisor will lead to a corresponding change in the private remainder, but such that as a result the GCD of these polynomials will be multiplied by some number equal to zero, which is acceptable.

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

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

GCD can be found using irreducible factorization or using Euclid's algorithm.

Example 40 Find the gcd of a polynomial
.

Solution. Let's factorize both polynomials:

It can be seen from the expansion that the desired gcd will be a polynomial ( X– 1).

Example 41 Find gcd of polynomials
and
.

Solution. Let us factorize both polynomials.

For polynomial
XX- 1) according to Horner's scheme.

For polynomial
possible rational roots are 1, 2, 3 and 6. By 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 square trinomial
was made according to Vieta's theorem.

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

Similarly, one can find GCD for several polynomials.

However, the method of finding the GCD by factoring is not always available. The way to find GCD for all cases is called Euclid's algorithm.

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

Consider the polynomials used in the previous two examples.

Example 42 Find gcd of polynomials
and
.

Solution. Let's divide
on the
"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 use the Euclid algorithm. Let's divide
on the
"corner":

1

Let's do the second division. To do this, one would have to divide the previous divisor
for the remainder
, but since
=
, for convenience we will divide the polynomial
not on
, and on
. From such a replacement, the solution of the problem will not change, 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 that 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 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.

Casting algorithm improper fraction to the correct one is called "selection of the whole part".

Example 44 Select the integer part of a fraction:
.

Solution. In order to isolate the integer part of a fraction, it is necessary to divide the numerator of the fraction by its denominator. We divide the numerator of this fraction by its denominator with a “corner”:

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

=
. The resulting fraction
is correct.

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

Comment. Note that the degrees of the numerator and the irreducible polynomial in the denominator are compared (without taking into account the degree 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
.

The algorithm for decomposing a fraction into simplest ones:

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

Factor out the denominator of a proper fraction.

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

Lead to common denominator sum of fractions on the right side.

We find indefinite coefficients:

Or by equating the coefficients at the same powers of the left and right reduced numerators;

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

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

Example 45 Break it down into simple
.

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

1

= 1 +
.

Let's break down the resulting fraction
to the simplest. First, we factor out the denominator. To do this, we find its roots using the standard formula:

Let's write the decomposition fractional rational function to the simplest ones, using indefinite coefficients:

We bring the right side of the equality to a common denominator:

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

Answer:
.

Example 46 Break it down into simple
.

Solution. Since this fraction is correct (i.e., the degree of the numerator is less than the degree of the denominator), it is not necessary to select the integer part. Let's factorize the denominator of a fraction:

We write the expansion of this fraction into simple ones, using indefinite coefficients:

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

. (2.2) It would be possible to compose 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 trick will help simplify them: we substitute the roots of the denominator into the numerators in turn.

At x = 1:

At X= ‑1:

Now to determine the remaining coefficients BUT and FROM it will suffice to equate the coefficients at the highest degree and the free terms. They can be found without opening parentheses:

The left side of the first equation is 0, since the numerator of the left fraction in (2.2) has no term with , and in the right fraction of the term with coefficient A + C. There is 0 on the left side of the second equation, since the free term in the numerator of the left fraction in (2.2) is equal to zero, and the free term in the numerator of the right fraction in (2.2) is (- A + B + C + D). We have:

Answer:
.

The use of equations is widespread in our lives. They are used in many calculations, construction of structures and even sports. Equations have been used by man since ancient times and since then their use has only increased. A polynomial is an algebraic sum of products of numbers, variables and their powers. Polynomial transformation usually involves two kinds of problems. The expression must either be simplified or factored, i.e. represent it as a product of two or more polynomials or a monomial and a polynomial.

To simplify the polynomial, bring like terms. Example. Simplify the expression \ Find monomials with the same letter part. Stack them up. Write down the resulting expression: \ You have simplified the polynomial.

In problems that require factoring a polynomial, determine the common factor of the given expression. To do this, first take out the brackets those variables that are part of all members of the expression. Moreover, these variables should have the smallest indicator. Then calculate the greatest common divisor of each of the coefficients of the polynomial. The module of the resulting number will be the coefficient of the common factor.

Example. Factorize the polynomial \ Parenthesize \ because the variable m is included in each term of this expression and its smallest exponent is two. Calculate the common multiplier factor. It is equal to five. Thus, the common factor of this expression is \ Hence: \

Where can I solve a polynomial equation online?

You can solve the equation on our website https: // site. Free online solver will allow you to solve an online equation of any complexity in seconds. All you have to do is just enter your data into the solver. You can also watch the video instruction and learn how to solve the equation on our website. And if you have any questions, you can ask them in our Vkontakte group http://vk.com/pocketteacher. Join our group, we are always happy to help you.

Euclid's algorithm for polynomials. Euclid's algorithm allows you to find the greatest common divisor of two polynomials, i.e. the polynomial of the greatest degree by which both given polynomials are divisible 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), (*)

the degree of the remainder is less than the degree of the divisor, the polynomial g(x), and, moreover, according to the given polynomials f(x) and g(x) the quotient and the remainder are uniquely found. If in equality (*) the remainder r(x) is equal to the zero polynomial (zero), then we say that the polynomial f(x) divided by g(x) without a remainder.
The algorithm consists of sequential division with a 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, is the second given polynomial, g(x), to the first remainder - to the 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, - the second remainder to the 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 is zero:

r n–2 (x) = r n–1 (x)∙q n (x) + r n (x),	(n)
r n–1 (x) = r n (x)∙q n+1 (x) + r n+1 (x),	(n+1)
r n+1 (x) = 0.	(n+2)

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 the equality ( n+ 2) substitute 0 for 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 are some polynomials. In this way, r n (x) is a common divisor of the two original polynomials, and the fact that it is the largest (that is, of the highest 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 coprime.