Euclid's algorithm for polynomials.Euclid's algorithm allows you to find the greatest common divisor of two polynomials, i.e. polynomial of greatest degree, by which both given polynomials are divisible without remainder.
The algorithm is based on the fact that for any two polynomials in one variable, f(x) and g(x), there are such polynomials q(x) and r(x), called the quotient and remainder, respectively, that
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, in addition, 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 they say that the polynomial f(x) divided by g(x) without a 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, is the second given polynomial, g(x), by the first remainder - by 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 for 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 equals 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 nonzero remainder r n
and will be the greatest common divisor of the original pair of polynomials f(x) and g(x).
Indeed, if by virtue of 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 g(x) = r n
(x)∙Q(x), and, finally, from equality (1) - that f(x) = r n
(x)∙S(x), where Qand S- some polynomials. In this way, 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 relatively simple.
Definition. If each of two polynomials is divisible by the third without remainder, then it is called the common divisor of the first two.
Greatest common divisor (GCD) of two polynomials is called their highest common divisor.
GCD can be found using the factorization or using the Euclidean algorithm.
Example 40Find GCD polynomials and 
.
Decision.Let us factor out both polynomials:
The decomposition shows that the required GCD is the polynomial ( x– 1).
Example 41Find the gcd of polynomials 
and 
.
Decision.Let us factor both polynomials.
For polynomial 
xx- 1) according to Horner's scheme.
For polynomial 
possible rational roots are the numbers 1, 2, 3 and 6. Using substitution, we make sure that x\u003d 1 is the root. Divide the polynomial by ( x- 1) according to Horner's scheme.
Therefore, where the decomposition of the square trinomial 
was produced by Vieta's theorem.
Comparing the factorization of polynomials, we find that the desired gcd is the polynomial ( x– 1)(x– 2).
Similarly, you can find the GCD for several polynomials.
However, the method of finding the GCD by factoring is not always available. The way to find the 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 the other, the degree of which is not higher than the degree of the first. Further, for the dividend, each time the polynomial that served as the divisor in the previous operation is taken, and the remainder obtained during the same operation is taken for the divisor. This process stops as soon as the remainder is equal to zero. Let us show this algorithm with examples.
Consider the polynomials used in the previous two examples.
Example 42Find the gcd of polynomials 
and 
.
Decision.Divide 
on 
"Corner":
x
Now let's divide the divisor 
for the remainder x– 1:
x+ 1
Since the last division happened without a remainder, the GCD will be x- 1, that is, the polynomial used as the divisor in this division.
Example 43Find the gcd of polynomials 
and 
.
Decision... To find the GCD, we use the Euclidean algorithm. Divide 
on 
"Corner":
1
Let's make the second division. To do this, you would have to divide the previous divisor 
for the remainder 
, but since 
=
, for convenience we will divide the polynomial 
not on 
and on 
... This replacement will not change the solution of 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 that the last divisor, i.e., the polynomial
and will be the desired GCD.
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 
Are polynomials.
A fractional rational function (in what follows we will call it "fraction") is called correctif 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 reducing an incorrect fraction to a correct one is called "separating the whole part".
Example 44Select whole fraction: 
.
Decision.In order to select the whole part of a fraction, it is necessary to divide the numerator of the fraction by its denominator. 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 over. Eventually:
=
... The resulting fraction 
is correct.
Fraction of the species 
is called the simplest if φ ( x
)
Is an irreducible polynomial, and the degree 
less than the degree φ ( x
).
Comment.Note that the degrees of the numerator and the irreducible polynomial in the denominator are compared (excluding the degree of α).
For fractions with real coefficients, there are 4 types of simple fractions:
Any correct fraction 
can be represented as a sum of the simplest fractions, the denominators of which are all possible divisors 
.
Algorithm for decomposing a fraction into simplest:
If the fraction is incorrect, then select the whole part, and decompose the resulting correct fraction into the simplest ones.
We factor out the denominator of the correct fraction.
We write a regular fraction as a sum of the simplest fractions with undefined coefficients.
Bring the sum of fractions on the right side to a common denominator.
We find undefined coefficients:
Either by equating the coefficients at the same degrees of the left and right given numerators;
Or by substituting specific (usually the roots of their common denominator) values x.
We write down the answer taking into account the integer part of the fraction.
Example 45Decompose into protozoa 
.
Decision.Since this fractional rational function is incorrect, we select the whole part:
1
= 1 +
.
Expand the resulting fraction 
into the simplest. First, factor the denominator. To do this, we find its roots using the standard formula:
Let us write the decomposition of a fractional rational function into elementary ones using indefinite coefficients:
Let us bring the right-hand side of the equality to a common denominator:
We compose a system by equating the coefficients at the same degrees in the numerators of the left and right fractions:
Answer: 
.
Example 46Decompose into protozoa 
.
Decision.Since this fraction is correct (that is, the degree of the numerator is less than the degree of the denominator), it is not necessary to select the whole part. Let us factor out the denominator of the fraction:
Let us write the decomposition of this fraction into elementary ones using undefined coefficients:
According to the statement, the denominators of the simplest fractions should be all kindsdivisors of the denominator of the 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 will be too cumbersome. The following technique will help to simplify them: we substitute the roots of the denominator in the numerators in turn.
When x \u003d1:
When x= ‑1:
Now to determine the remaining coefficients ANDand FROMit will be enough to equate the coefficients at the highest degree and the free terms. They can be found without expanding the parentheses:
There is 0 on the left side of the first equation, since the numerator of the left fraction in (2.2) does not contain a term with 
, and in the right fraction of the term with 
coefficient A +
C... The left side of the second equation contains 0, 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: 
.
Division of polynomials. ALGORITHM Euclidean
§1. Division of polynomials
During division, polynomials are represented in canonical form and are arranged in decreasing degrees of any 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 division is the only pair of polynomials - quotient and remainder, which must satisfy the equality:
< делимое > = < делитель > ´ < частное > + < остаток > .
If a polynomial of degreen Pn (x ) is divisible,
Degree polynomialm Rk (x ) is a divisor (n ³ m),
The polynomial Qn - m (x ) - private. The degree of this polynomial is equal to the difference between the degrees of the dividend and the divisor,
A polynomial of degreek Rk (x ) is the remainder (k< m ).
That equality
Pn (x) \u003d Fm (x) × Qn - m (x) + Rk (x) (1.1)
must be fulfilled identically, that is, remain valid for any real values \u200b\u200bof x.
Note again that the degree of the remainderk must be less than the divisor powerm ... The purpose of the remainder is to complete the product of polynomialsFm (x) and Qn - m (x ) to a polynomial equal to the dividend.
If the product of polynomialsFm (x) × Qn - m (x ) gives a polynomial equal to the dividend, then the remainderR \u003d 0. In this case, they say that division is performed without a remainder.
Let us 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 senior term of the dividend 5x5 by the senior term of the divisor x3:
It will be shown below that this is the first term of the quotient.
2. The divisor is multiplied by the next (first first) term of the quotient and this product is subtracted from the dividend:
5x5 + x3 + 1 - 5x2 (x3 + 2) \u003d x3 - 10x2 + 1.
3. The dividend can be represented as
5x5 + x3 + 1 \u003d 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 senior term of the difference x3 is divided by the senior 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, second) term of the quotient and this product is subtracted from the last difference
X3 - 10x2 + 1 - 1 × (x3 + 2) \u003d - 10x2 - 1.
3. Then, the last difference can be represented as
X3 - 10x2 + 1 \u003d 1 × (x3 + 2) + (–10x2 +
If the degree of the next difference turns out to be less than the degree of the divisor (as when repeating 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 in equality (1.2) the result of the transformation of the polynomial x3 - 10x2 + 1 (see (1.3)): 5x5 + x3 + 1 \u003d 5x2 (x3 + 2) + 1× (x3 + 2) + (- 10x2 - 1). Then, after taking the common factor (x3 + 2) outside the brackets, we finally get
5x5 + x3 + 1 \u003d (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 a quotient (5x2 + 1) and remainder (- 10x2 - 1).
It is customary to formalize these actions in the form of a scheme called "dividing by a corner". Moreover, 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 a gap.
| |
5x5 + 10x2 5x2 + 1
| |
X3 + 2
–10x2 + 0x - 1
position: relative; z-index: 1 "\u003e We see that the division of polynomials is reduced to a sequential repetition of actions:
1) at the beginning of the algorithm, the senior term of the dividend, subsequently, the senior term of the next difference is divided by the senior term of the divisor;
2) the result of division gives the next term in the quotient, by which the divisor is multiplied. The resulting work is written under the dividend or the next difference;
3) the lower polynomial is subtracted from the upper polynomial, and if the degree of the resulting 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 obtained difference is less than the degree of the divisor, then the division is complete. In this case, 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 "\u003e
4x2 + 0x - 24x2 ± 2x ± 2
Thus, 6x3 + x2 - 3x - 2 \u003d (2x2 - x - 1) (3x + 2) + 2x.
Example No. 2
A3b2 + b5
A3b2 a2b3
- a2b3 + b5
± a2b3 ± ab4
Ab4 + b5
- ab4 b5
In this way , a5 + b5 \u003d (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 \u003d (x - y) (x4 + x3y + x2y2 + xy3 + y4).
A generalization of the results obtained in examples 2 and 3 are two formulas for abbreviated multiplication:
(x + a) (x2 n - x2 n –1 a + x2 n –2 a 2 -… + a2n) \u003d x 2n + 1 + a2n + 1;
(x - a) (x 2n + x 2n – 1 a + x 2n – 2 a2 +… + a2n) \u003d x 2n + 1 - a2n + 1, where n Î N.
Exercises
Perform 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 ) - quotient, 0 - remainder.
§2. Finding the Greatest Common Divisor of Two Polynomials
1. Euclid's algorithm
If each of two polynomials is divisible by a third without a remainder, then this third polynomial is called the common divisor of the first two.
The greatest common divisor (GCD) of two polynomials is called their greatest common divisor.
Note that any number that is not equal to zero is a common divisor of any two polynomials. Therefore, any non-zero number is called the trivial common divisor of these polynomials.
Euclid's 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 greater degree does not exist.
Euclid's algorithm is implemented as a sequence of divisions. In the first division, the polynomial is viewed more as a dividend, and less as a divisor. If the polynomials for which the GCD is found have the same degrees, then the dividend and the divisor are chosen arbitrarily.
If, at the next division, the remainder of the polynomial has degree greater than or equal to 1, then the divisor becomes divisible, and the remainder becomes a divisor.
If at the next division of the polynomials the remainder is equal to zero, then the GCD of these polynomials is found. It is the divisor at the last division.
If, at the next division of the polynomials, the remainder turns out to be a non-zero number, then for these polynomials there is no GCD other than trivial ones.
Example # 1
Reduce fraction 
.
Decision
Find the GCD of these polynomials using Euclid's algorithm
| |
X3 + 7x2 + 14x + 8 1
- x2 - 3x - 2
| |
X3 + 3x2 + 2x - x - 4
3x2 + 9x + 6
3x2 + 9x + 6
| |
position: absolute; z-index: 49; left: 0px; margin-left: 209px; margin-top: 6px; width: 112px; height: 20px "\u003e 
font-size: 14.0pt; line-height: 150% "\u003e Answer:
font-size: 14.0pt; line-height: 150% "\u003e 2. Possibilities of simplifying the calculations of GCD in the Euclidean algorithm
Theorem
When multiplying the dividend by a non-zero number, the quotient and the remainder are multiplied by the same number.
Evidence
Let P be the dividend, F be the divisor, Q be the quotient, R Is the remainder. Then,
P \u003d F × Q + R.
Multiplying this identity by the numbera ¹ 0, we get
a P \u003d F × (a Q) + a R,
where the polynomial a P can be viewed as a dividend, and the polynomialsa Q and a R - as quotient and remainder obtained by dividing a polynomiala P by a polynomial F ... Thus, when multiplying the dividend by the numbera ¹ 0, quotient and remainder are also multiplied bya, h. d.
Consequence
Multiplying a divisor by a numbera ¹ 0 can be thought of as multiplying the dividend by a number.
Therefore, when multiplying the divisor by the numbera ¹ 0 is the quotient and the remainder is multiplied by.
Example No. 2
Find the quotient Q and remainder R when dividing polynomials
Font-size: 14.0pt; line-height: 150% "\u003e Decision
To pass in the dividend and divisor to integer coefficients, we multiply the dividend by 6, which will lead to multiplication by 6 of the desired quotientQ and remainder R ... After that, we multiply the divisor by 5, which will lead to the multiplication of the quotient 6Q and remainder 6 R on . As a result, the quotient and remainder obtained by dividing polynomials with integer coefficients will differ by times from the sought values \u200b\u200bof the quotientQ and remainder R obtained by dividing these polynomials.
| |
| |
12y4 ± 18x3 30x2y2 6y2 - 2x - 9x2 \u003d
- 4х3 - 12х2у2 - 11х3у + 3х4
± 4х3 6х2у2 ± 10х3у
- 18x2y2 - x3y + 3x4
± 18x2y2 27x3y ± 45x4
- 28х3у + 48х4 \u003d font-size: 14.0pt; line-height: 150% "\u003e Therefore;
Answer: 
, 
.
Note that if the greatest common divisor of these polynomials is found, then multiplying it by any number that is not equal to zero, we also get 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 number. As shown above, the multiplication of 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 fraction 
.
Decision
Applying Euclid's algorithm, we get
| |
X4 x3 ± 3x2 font-size: 14.0pt; line-height: 150% "\u003e 4 1
2x3 + 6x2 + 3x - 2
font-size: 14.0pt; line-height: 150% "\u003e 2) 2 (x4 + x3 - 3x2 + 4) \u003d 2x4 + 2x3 - 6x2 + 8 2x3 + 6x2 + 3x - 2
2x4 6x3 3x2 ± 2x x - 2
- 4x3 - 9x2 + 2x + 8
± 4x3 ± 12x2 ± 6x font-size: 14.0pt; line-height: 150% "\u003e 4
3x2 + 8x + 4
| |
| |
6x3 font-size: 14.0pt "\u003e 16x2 font-size: 14.0pt"\u003e 8x 2x +
1. Euclid's algorithm
If each of two polynomials is divisible by a third without a remainder, then this third polynomial is called the common divisor of the first two.
The greatest common divisor (GCD) of two polynomials is called their greatest common divisor.
Note that any number that is not equal to zero is a common divisor of any two polynomials. Therefore, any non-zero number is called the trivial common divisor of these polynomials.
Euclid's 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 greater degree does not exist.
Euclid's algorithm is implemented as a sequence of divisions. In the first division, the polynomial is viewed more as a dividend, and less as a divisor. If the polynomials for which the GCD is found have the same degrees, then the dividend and the divisor are chosen arbitrarily.
If, during the next division, the remainder of the polynomial has degree greater than or equal to 1, then the divisor becomes divisible, and the remainder becomes a divisor.
If at the next division of the polynomials the remainder is equal to zero, then the GCD of these polynomials is found. It is the divisor at the last division.
If, at the next division of the polynomials, the remainder turns out to be a non-zero number, then for these polynomials there is no GCD other than trivial ones.
Example # 1
Reduce fraction.
2. Possibilities of simplifying the calculations of GCD in the Euclidean algorithm
When multiplying the dividend by a non-zero number, the quotient and the remainder are multiplied by the same number.
Evidence
Let P be a dividend, F a divisor, Q a quotient, R a remainder. Then,
Multiplying this identity by the number 0, we obtain
where the polynomial P can be regarded as a 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, p.t. d
Consequence
Multiplying the divisor by 0 can be thought of as multiplying the dividend by the number.
Therefore, when multiplying the divisor by the number 0, the quotient and the remainder are multiplied by.
Example No. 2
Find the quotient Q and remainder R when dividing polynomials
division polynomial algorithm euclidean
To pass in the dividend and divisor to integer coefficients, we multiply the dividend by 6, which will lead to multiplication by 6 of the desired quotient Q and remainder R. Then, multiply the divisor by 5, which will lead to multiplication of the quotient 6Q and remainder 6R by. As a result, the quotient and remainder obtained by dividing polynomials with integer coefficients will differ by times from the sought values \u200b\u200bof 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 multiplying it by any number that is not equal to zero, we also get 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 number. As shown above, the multiplication of 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.
The use of equations is widespread in our life. They are used in many calculations, building construction and even sports. Man used equations in antiquity and since then their application has only increased. A polynomial is an algebraic sum of products of numbers, variables and their powers. Transforming polynomials usually involves two kinds of problems. The expression needs to be either simplified or decomposed into factors, i.e. represent it as a product of two or more polynomials or a monomial and a polynomial.
To simplify the polynomial, give similar terms. Example. Simplify the expression \\ Find monomials with the same letter part. Fold them up. Write down the resulting expression: \\ You have simplified the polynomial.
For problems that require factoring a polynomial, find the common factor for this expression. To do this, first place out of parentheses those variables that are included in 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 modulus of the resulting number will be the coefficient of the common factor.
Example. Factor the polynomial \\ Factor out \\ as the variable m is included in each term of this expression and its smallest exponent is two. Calculate the common factor. It is equal to five. Thus, the common factor of this expression is \\ Hence: \\
Where can you solve the polynomial equation online?
You can solve the equation on our website https: // site. A free online solver will solve an equation online of any complexity in a matter of seconds. All you have to do is just enter your data into the solver. You can also watch a video instruction and learn how to solve the equation on our website. And if you still have questions, you can ask them in our Vkontakte group http://vk.com/pocketteacher. Join our group, we are always happy to help you.
