Find polynomial nodes online with solution. Finding the greatest common divisor of polynomials. Lab Options

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 the 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 will be the numbers 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
"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
"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.

The algorithm for converting an improper fraction to a proper one is called "selecting the integer 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.

We bring to a common denominator the sum of the 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:

We write the decomposition of a fractional-rational function into simple 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 A And WITH 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) zero, and the numerator of the right fraction in (2.2) has a free term equal to (- A + B + C + D). We have:

Answer:
.

DIVISION OF POLYNOMIALS. EUCLID ALGORITHM

§1. Division of polynomials

When dividing, polynomials are presented in canonical form and are arranged in descending powers of a letter, relative to which the degree of the dividend and divisor is determined. The degree of the dividend must be greater than or equal to the degree of the divisor.

The result of the division is the only pair of polynomials - the quotient and the remainder, which must satisfy the equality:

< делимое > = < делитель > ´ < частное > + < остаток > .

If the degree polynomial n Pn (x ) is divisible,

degree polynomial m Rk (x ) is a divisor of ( n ³ m ),

Polynomial Qn – m (x ) is private. The degree of this polynomial is equal to the difference between the degrees of the dividend and the divisor,

A polynomial of degree k Rk (x ) is the remainder of ( k< m ).

That equality

Pn(x) = Fm(x) × Qn – m(x) + Rk(x) (1.1)

must hold identically, that is, remain valid for any real values ​​of x.

Again, we note that the degree of the remainder k must be less than the power of the divisor m . The purpose of the remainder is to complete the product of polynomials Fm (x) and Qn - m (x ) to a polynomial equal to the dividend.

If the product of polynomials Fm (x) × Qn – m (x ) gives a polynomial equal to the dividend, then the remainder R = 0. In this case, we say that the division is carried out without a remainder.

We will consider the algorithm for dividing polynomials using a specific example.

Let it be required to divide the polynomial (5x5 + x3 + 1) by the polynomial (x3 + 2).

1. Divide the highest term of the dividend 5x5 by the highest term of the divisor x3:

It will be shown below that this is how the first term of the quotient is found.

2. The divisor is multiplied by the next (initially the first) term of the quotient and this product is subtracted from the dividend:

5x5 + x3 + 1 - 5x2(x3 + 2) = x3 - 10x2 + 1.

3. The dividend can be represented as

5x5 + x3 + 1 = 5x2(x3 + 2) + (x3 - 10x2 +

If in action (2) the degree of the difference turns out to be greater than or equal to the degree of the divisor (as in the example under consideration), then with this difference the actions indicated above are repeated. Wherein

1. The highest term of the difference x3 is divided by the highest term of the divisor x3:

It will be shown below that in this way the second term in the quotient is found.

2. The divisor is multiplied by the next (now the second) term of the quotient and this product is subtracted from the last difference

X3 - 10x2 + 1 - 1 × (x3 + 2) = - 10x2 - 1.

3. Then, the last difference can be represented as

X3 - 10x2 + 1 = 1 × (x3 + 2) + (-10x2 +

If the degree of the next difference turns out to be less than the degree of the divisor (as in the case of repetition in action (2)), then the division is completed with a remainder equal to the last difference.

To confirm that the quotient is the sum (5x2 + 1), we substitute into equality (1.2) the result of the transformation of the polynomial x3 - 10x2 + 1 (see (1.3)): 5x5 + x3 + 1 = 5x2(x3 + 2) + 1× (x3 + 2) + (- 10x2 - 1). Then, after taking the common factor (x3 + 2) out of brackets, we finally get

5x5 + x3 + 1 = (x3 + 2)(5x2 + 1) + (- 10x2 - 1).

Which, in accordance with equality (1.1), should be considered as the result of dividing the polynomial (5x5 + x3 + 1) by the polynomial (x3 + 2) with the quotient (5x2 + 1) and the remainder (- 10x2 - 1).

It is customary to draw up these actions in the form of a scheme called “division by a corner”. At the same time, in the record of the dividend and subsequent differences, it is desirable to produce the terms of the sum over all decreasing powers of the argument without skipping.

X3 + 2

-10x2 + 0x - 1

position:relative; z-index:1">We see that the division of polynomials is reduced to the sequential repetition of actions:

1) at the beginning of the algorithm, the senior member of the dividend, subsequently, the senior member of the next difference is divided by the senior member of the divisor;

2) the result of division gives the next term in the quotient, by which the divisor is multiplied. The resulting product is written under the divisible or regular difference;

3) the lower polynomial is subtracted from the upper polynomial and, if the degree of the obtained difference is greater than or equal to the degree of the divisor, then actions 1, 2, 3 are repeated with it.

If the degree of the resulting difference is less than the degree of the divisor, then the division is completed. The last difference is the remainder.

Example #1

position:absolute;z-index: 9;left:0px;margin-left:190px;margin-top:0px;width:2px;height:27px">

4x2 ± 2x ± 2

Thus, 6x3 + x2 - 3x - 2 = (2x2 - x - 1) (3x + 2) + 2x.

Example #2

A3b2+b5

A3b2 a2b3

– a2b3 + b5

± a2b3 ± ab4

Ab4 + b5

– ab4 b5

Thus , a5 + b5 = (a + b)(a4 – a3b + a2b2 – ab3 + b4).

Example №3

x5 x4y x4 + x3y + x2y2 + xy3 + y4

X3y2 - y5

X3y2 ± x2y3

Hu 4 - y 5

Hu 4 - y 5

Thus x5 - y5 = (x - y)(x4 + x3y + x2y2 + xy3 + y4).

A generalization of the results obtained in examples 2 and 3 are two reduced multiplication formulas:

(x + a) (x2 n - x2 n -1 a + x2 n -2 a 2 - ... + a2n) \u003d x 2n + 1 + a2n + 1;

(х – a)(х 2n + х 2n–1 a + х 2n–2 a2 + … + a2n) = х 2n+1 – a2n + 1, where n н N.

Exercises

Execute Actions

1. (- 2x5 + x4 + 2x3 - 4x2 + 2x + 4): (x3 + 2).

Answer: - 2x2 + x +2 - quotient, 0 - remainder.

2. (x4 - 3x2 + 3x + 2): (x - 1).

Answer: x3 + x2 - 2x + 1 - quotient, 3 - remainder.

3. (x2 + x5 + x3 + 1): (1 + x + x2).

Answer: x3 - x2 + x + 1 - quotient, 2x - remainder.

4. (x4 + x2y2 + y4): (x2 + xy + y2).

Answer: x2 - xy + y2 - quotient, 0 - remainder.

5. (a 3 + b 3 + c 3 - 3 abc): (a + b + c).

Answer: a 2 - (b + c) a + (b 2 - bc + c 2 ) is the quotient, 0 is the remainder.

§2. Finding the Greatest Common Divisor of Two Polynomials

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 of the greatest degree.

Note that any number is not 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 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 .

Solution

Find the gcd of these polynomials using the Euclid algorithm

position:absolute;z-index: 49;left:0px;margin-left:209px;margin-top:6px;width:112px;height:20px"> font-size:14.0pt;line-height:150%">Answer: font-size:14.0pt;line-height:150%"> 2. Possibilities of simplifying GCD calculations in the Euclid algorithm

Theorem

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 - remainder. Then,

P = F × Q + R.

Multiplying this identity by the number a ¹ 0, we get

a P = F × (a Q) + a R,

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

Consequence

Multiplying a Divisor by a Number a¹ 0 can be thought of as multiplying a dividend by a number.

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

Example #2

Find the quotient Q and the remainder R when dividing polynomials

Font-size:14.0pt;line-height:150%"> Solution

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

3) 3(2x3 + 6x2 + 3x - 2) = 6x3 + 18x2 + 9x - 6 3x2 + 8x + 4

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

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. The polynomial is algebraic sum 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.

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 of the greatest degree.

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.

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