Finding nodes and nodes of polynomials. The greatest common divisor of polynomials. coprime polynomials. 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 -
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 a matter of 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 offers 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 non-zero number, 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 multiplying it by any number that is not equal to zero, we also get largest divisor 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 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 THE THEORY
Definition 4.1.
The polynomial j(x) from 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 + 2х + 2 О R[x]. Common divisors of these polynomials: 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 Divisorof non-zero polynomials f(x) and g(x) from P[x] is such 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 + 2х + 2 н R[x] the greatest common divisor is the polynomial d(x) = j 1 (x) = x 3 − 4x 2 + 2 н R[x], because this polynomial d(x) is divisible by all their other common divisors j 2 (x), j 3 (x),j 4 (x).
The greatest common divisor (GCD) is denoted by the symbol:
d(x) = (f(x), g(x)).
The greatest common divisor exists for any two polynomials f(x),g(x) н P[x] (g(x)¹ 0). Its existence determines Euclid's algorithm, which is as follows.
Divide f(x) on the g(x). Let us denote the remainder and the quotient obtained by division r 1 (x) and q 1 (x). Then if r 1 (x)¹ 0, divide g(x) on the r 1 (x), we get the remainder r 2 (x) and private q 2 (x) etc. Degrees of resulting residues r 1 (x), r 2 (x),… will decrease. But the sequence of non-negative integers is bounded from below by the number 0. Therefore, the division process will be finite, and we will arrive at the remainder rk(x), by which the previous remainder is completely divided rk – 1 (x). The whole 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 r 2 (x) < deg r 1 (x);
. . . . . . . . . . . . . . . . . . . . . . . .
r k – 2 (x)= r k – 1 (x)× q k (x) + rk(x), deg rk(x)< deg rk – 1 (x);
r k – 1 (x) = rk(x) × q k +1 (x).(*)
Let's prove that rk(x) will be the greatest common divisor of polynomials f(x) and g(x).
1) Let us show that rk(x) is an common divisor polynomial data.
Let's look at the penultimate equation:
rk –-2 (x)= r k –-1 (x)× q k (x) + rk(x), or rk –-2 (x)= rk(x) × q k +1 (x) × q k (x) + rk(x).
Its right side is divided into rk(x). Therefore, the left side is also divisible by rk(x), those. rk –-2 (x) divided by rk(x).
rk --- 3 (x)= rk --- 2 (x)× q k – 1 (x) + r k -- 1 (x).
Here r k -- 1 (x) and rk --- 2 (x) are divided into rk(x), it follows that the sum on the right side of the equality is also divisible by rk(x). So the left side of the equality is also divisible by rk(x), those. rk --- 3 (x) divided by rk(x). Moving up in this way sequentially, we get that the polynomials f(x) and g(x) are divided into rk(x). Thus, we have shown that rk(x) is an common divisor polynomial data (Definition 4.1.).
2) Let us show that rk(x) divided by any other common divisor j(x) polynomials f(x) and g(x), that is, is greatest common divisor these polynomials .
Let's look at the first equation: f(x)=g(x) × q 1 (x) + r 1 (x).
Let be d(x) is some common divisor f(x) and g(x). Then, by the properties of divisibility, the difference f(x)–g(x) × q 1 (x) also divided into d(x), that is, the left side of the equation f(x)–g(x) × q 1 (x)= r 1 (x) divided by d(x). Then and r 1 (x) will be divided into d(x). Continuing the reasoning in a similar way, successively descending down the equalities, we obtain that rk(x) divided by d(x). Then, according to definition 4.2.rk(x) will be greatest common divisor polynomials f(x) and g(x): d(x) = (f(x), g(x)) = rk(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 proved the theorem:
Theorem 4.1. /Euclid's algorithm/.
If for polynomials f(x),g(x) н P[x] (g(x)¹ 0) correct system of equalities and inequalities(*), 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)\u003d x 3 -2x 2 + x -2.
Decision.
1 step. 2 step.
| x 4 + x 3 +2x 2 + x + 1 | x 3 –2x 2 + x –2 | x 3 –2x 2 + x –2 | 7x2+7 | |
| –(x 4 -2x 3 + x 2 - 2x) | x+3 = q 1 (x) | –(x 3 + x) | 1/7x.–2/7 = q 2 (x) | |
| 3x 3 + x 2 + 3x + 1 – ( 3x 3 -6x 2 + 3x -6) | –2x 2 –2 –( –2x2 –2) | |||
| 7x 2 + 7 = r 1 (x) | 0 = r 2 (x) |
We write the division steps as 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)× q 2 (x).
According to Theorem 4.1./Euclid's 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 instead of 7x 2 + 7 we can take as the GCD, but ( 7x2 + 7) = x2 + 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. found the greatest common divisor d(x) = (f(x), g(x)) = 7x 2 + 7 polynomials f(x)= x 4 + x 3 +2x 2 + x + 1 and g(x)\u003d x 3 -2x 2 + x -2. Replacing it with its associated polynomial d 1 (x)= x 2 + 1, we obtain the normalized greatest common divisor of these polynomials ( f(x), g(x)) = x2 + 1.
Comment. Applying the Euclidean algorithm in finding the greatest common divisor of two polynomials, we can make 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 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 suitable only for finding the greatest common divisor of two polynomials, then in order to find the greatest common divisor of n polynomials, it is required to prove the following theorem.
