## Chapter 4: Polynomials: Solved problems

1. Use the Euclidean algorithm to find gcd( x8-1, x6-1) in Q[x] and write it as a linear combination of x8 -1 and x6 -1.

Solution: Let x8-1 = f(x) and x6-1 = g(x). We have f(x) = x2 g(x) + (x2-1), and g(x) = (x4+x2+1) (x2 -1), so this shows that gcd( x8-1, x6-1) = x2 - 1, and x2-1 = f(x) - x2 g(x).

(b) Factor x8-1 and x6-1 into products of polynomials that are irreducible over Q.

Solution: (Partial)
x8 - 1 = (x4-1)(x4+1) = (x-1)(x+1)(x2+1)(x4+1). The factor x2+1 is irreducible because it has no roots in Q; x4+1 is irreducible because substituting x+1 gives the polynomial x4+4x3+6x2+4x+2, which satisfies Eisenstein's criterion for p=2.

(c) Use your answer from (b) to compute gcd( x8-1, x6-1) in Q[x].

Solution: (x-1)(x+1)

2. Over the field of rational numbers, use the Euclidean algorithm to show that 2x3-2x2-3x+1 and 2x2-x-2 are relatively prime.

Solution: Let 2x3-2x2-3x+1 = f(x) and 2x2-x-2 = g(x). The polynomilas factor as follows.

f(x) = (x+1)(2x2-4x+1)
g(x) = (2x2-x-2)

Dividing f by g we first obtain f(x) = (x - 1/2) g(x) - 3x/2. At the next step we can use x rather than 3x/2; that is, dividing g by x gives (???) g(x) = (2x-1) g(x) - 2. The constant remainder at the second step implies that gcd (f(x),g(x)) = 1.

3. Over the field of rational numbers, find the greatest common divisor of
x4+x3+2x2+x+1 and x3-1,
and express it as a linear combination of the given polynomials.

Solution: Let x4+x3+2x2+x+1 = f(x) and x3-1 = g(x). The two polynomials factor as follows:

f(x) = (x2+1)(x2+x+1)
g(x) = (x-1)(x2+1+1)

We first obtain f(x) = (x+1) g(x) + 2(x2+x+1), and then the next step yields g(x) = (x-1) (x2+x+1), so gcd (f(x), g(x)) = x2+x+1, and (x2+x+1) = (1/2) f(x) - (1/2) (x+1) g(x).

4. Over the field of rational numbers, find the greatest common divisor of 2x4-x3+x2+3x+1 and 2x3-3x2+2x+2 and express it as a linear combination of the given polynomials.

Solution: To simplify the computations, let 2x4-x3+x2+3x+1 = f(x) and 2x3-3x2+2x+2 = g(x). These factor as follows:

f(x) = (2x+1)(x3-x2+x+1)
g(x) = (2x+1)(x2-2x+2)

Using the Euclidean algorithm, we first obtain f(x)= (x+1) g(x) + (2x2-x-1), and then g(x) = (x-1) (2x2-x-1) + (2x+1). At the next step we obtain 2x2-x-1 = (x-1)(2x+1), so 2x+1 is the greatest common divisor (we must then divide by 2 to make it monic).

Beginning with the last equation and back-solving, we get

2x+1 = g(x) - (x-1)(2x2-x-1)
= g(x) - (x-1)(f(x) - (x+1)g(x))
= g(x) + (x2-1) g(x) - (x-1) f(x)
= x2 g(x) - (x-1) f(x)

This gives the final answer, x + 1/2 = 1/2 x2 g(x) + (-1/2)(x-1) f(x).

5. Are the following polynomials irreducible over Q?

(a) 3 x5 + 18 x2 + 24 x + 6

Solution: Dividing by 3 we obtain x5 + 6x2 +8x +2, and this satisfies Eisenstein's criterion for p=2.

(b) 7 x3 + 12 x2 + 3 x + 45

Solution: Reducing the coefficients modulo 2 gives the polynomial x3 +x +1, which is irreducible in Z2 [x]. This implies that the polynomial is irreducible over Q.

(c) 2 x10 + 25 x3 + 10 x2 - 30

Solution: Eisenstein's criterion is satisfied for p=5.

6. Factor x5-10x4+24x3+9x2-33x-12 over Q.

Solution: The possible rational roots of f(x) = x5-10x4+24x3+9x2-33x-12 are ± 1, ± 2, ± 3, ± 4, ± 6, ± 12. We have f(1) = 21, so for any root we must have (r-1) | 21, so this eliminates all but ± 2, 4, -6 as possibilities. Then f(2) = 32, f(-2) = -294, and finally we obtain the factorization f(x) = (x-4)(x4-6x3+9x+3). The second factor is irreducible over Q since it satisfies Eisenstein's criterion for p = 3.

7. Factor x5-2x4-2x3+12x2-15x-2 over Q.

Solution: The possible rational roots are ± 1, ± 2, and since 2 is a root we have the factorization x5-2x4-2x3+12x2-15x-2 = (x-2)(x4-2x2+8x+1). The only possible rational roots of the second factor are 1 and -1, and these do not work. (It is important to note that since the degree of the polynomial is greater than 3, the fact that it has no roots in Q does not mean that it is irreducible over Q.)

Since the polynomial has no linear factors, the only possible factorization has the form x4-2x2+8x+1 = (x2+ax+b)(x2+cx+d). This leads to the equations a+c=0, ac+b+d = -2, ad+bc = 8, and bd = 1. We have either b=d=1, in which case a+c=8, or b=d=-1, in which case a+c=-8. Either case contradicts a+c=0, so x4-2x2+8x+1 is irreducible over Q. As an alternate solution, we could reduce x4-2x2+8x+1 modulo 3 to get p(x) = x4+x2+2x+1. This polynomial has no roots in Z3, so the only possible factors are of degree 2. The monic irreducible polynomials of degree 2 over Z3 are x2+1, x2+x+2, and x2+2x+2. Since the constant term of p(x) is 1, the only possible factorizations are p(x) = (x2+x+2)2, p(x) = (x2+2x+2)2, or p(x) = (x2+x+2)(x2+2x+2). In the first the coefficient of x is 1; the second has a nonzero cubic term; in the third the coefficient of x is 0. Thus p(x) is irreducible over Z3, and hence over Q.

8. (a) Show that x2 + 1 is irreducible over Z3.

Solution: To show that p(x) = x2 + 1 is irreducible over Z3, we only need to check that it has no roots in Z3, and this follows from the computations p(0) = 1, p(1) = 2, and p(-1) = 2.

(b) List the elements of the field F = Z3[x] / < x2 + 1 >.

Solution: The congruence classes are in one-to-one correspondence with the linear polynomials, so we have the nine elements [0], [1], [2], [x], [x+1], [x+2], [2x], [2x+1], [2x+2].

(c) In the multiplicative group of nonzero elements of F, show that [x+1] is a generator, but [x] is not.

Solution: The multiplicative group of F has 8 elements, and since [x]2 = [-1], it follows that [x] has order 4 and is not a generator. On the other hand, [x+1]2 = [x2+2x+1] = [-1+2x+1] = [2x] = [-x], and so [x+1]4 = [-x]2 = [-1], which shows that [x+1] does not have order 2 or 4. The only remaining possibility (by Lagrange's theorem) is that [x+1] has order 8, and so it is a generator for the multiplicative group of F.

9. (a) Express x4 + x as a product of polynomials irreducible over Z5.

Solution: In general, we have x4+x = x (x3+1) = x (x+1) (x2-x+1). The factor p(x) = x2-x+1 is irreducible over Z5 since it can be checked that it has no roots in Z5. (We get p(0) = 1, p(1) = 1, p(-1) = 3, p(2) = 3, p(-2) = 2.)

(b) Show that x3 + 2x2 +3 is irreducible over Z5.

Solution: If p(x) = x3 + 2x2 +3, then p(0) = 3, p(1) = 1, p(-1) = -1, p(2) = 4, and p(-2) = 3, so p(x) is irreducible over Z5.

10. Express 2x3+x2+2x+2 as a product of polynomials irreducible over Z5.

Solution: We first factor out 2, using (2)(-2) = -4 1 (mod 5). This reduces the question to factoring p(x) = x3-2x2+x+1. (We could also multiply each term by 3.) Checking for roots shows that p(0) = 1, p(1) = 1, p(-1) = -3, p(2) = 3, and p(-2) -2, so p(x) itself is irreducible over Z5.

11. Construct an example of a field with 343 = 73 elements.

Solution: We only need to find a cubic polynomial over Z7 that has no roots. The simplest case would be to look for a polynomial of the form x3 + a. The cube of any element of Z7 gives either 1 or -1, so x3 = 2 has no root over Z7, and thus p(x) = x3 - 2 is an irreducible cubic over Z7. Using the modulus p(x), the elements of Z7 [x] / < p(x) > correspond to polynomials of degree 2 or less, giving the required 73 elements. With this modulus, the identities necessary to determine multiplication are [x3] = [5] and [x4] = [5x].

12. In Z2[x] / < x3+x+1 >, find the multiplicative inverse of [x+1].

Solution: We first give a solution using the Euclidean algorithm. For p(x) = x3+x+1 and f(x) = x+1, the first step of the Euclidean algorithm gives p(x) = (x2+x) f(x) + 1. Thus p(x) -(x2+x)f(x) = 1, and so reducing modulo p(x) gives [-x2-x][f(x)] = [1], and thus [x+1]-1 = [- x2-x] = [x2+x].

We next give an alternate solution, which uses the identity [x3] = [x+1] to solve a system of equations. We need to solve [1] = [x+1][ax2+bx+c] or

[1] = [ax3+bx2+cx +ax2+bx+c]
= [ax3+(a+b)x2+(b+c)x +c]
= [a(x+1)+(a+b)x2+(b+c)x+c]
= [(a+b)x2+(a+b+c)x+(a+c)],

so we need a+b 0 (mod 2), a+b+c 0 (mod 2), and a+c 1 (mod 2). This gives c 0 (mod 2), and therefore a 1 (mod 2), and then b 1 (mod 2). Again, we see that [x+1]-1 = [x2+x].

13. Find the multiplicative inverse of [x2 +x +1]

(a) in Q[x] / < x3 - 2 >;

Solution: Using the Euclidean algorithm, we have

x3 - 2 = (x2 + x + 1) (x - 1) + (-1), and so [x2 + x + 1]-1 = [x - 1].

This can also be done by solving a system of 3 equations in 3 unknowns.

(b) in Z3[x]/ < x3+2x2+x+1 >.

Solution: Using the Euclidean algorithm, we have

x3 + 2x2 + x + 1 = (x + 1) (x2 + x + 1) + (- x) and
x2 + x + 1 = (- x - 1) (-x) + 1.

Then a substitution gives us

1 = (x2 + x + 1) + (x + 1) (-x)
= (x2 + x + 1) + (x + 1) ( (x3 + 2x2 + x + 1) - (x + 1) (x2 + x + 1))
= (-x2 - 2x) (x2 + x + 1) + (x + 1)(x3 + x2 + 2x + 1) .

Thus [x2 + x + 1]-1 = [-x2 - 2x] = [2 x2 + x]. This can be checked by finding [x2 + x + 1] [2 x2 + x], using the identities [x3] = [x2 - x - 1] and [x4] = [x - 1].

This can also be done by solving a system of equations, or, since the set is finite, by taking successive powers of [x2+x+1]. The latter method isn't really practical, since the multiplicative group has order 26, and this element turns out to have order 13.

14. In Z5 [x] / < x3+x+1 >, find [x]-1 and [x+1]-1, and use your answers to find [x2+x]-1.

Solution: Using the division algorithm, we obtain x3+x+1 = x(x2+1)+1, and so [x][x2+1] = [-1]. Thus [x]-1 = [-x2-1].

Next, we have x3+x+1 = (x+1)(x2-x+2)-1, and so [x+1]-1 = [x2-x+2].

Finally, we have

[x2+x]-1 = [x]-1 [x+1]-1 = [-x2-1] [x2-x+2]
= [-x4+x3-2x2-x2+x-2] .

Using the identities [x3] = [-x-1] and [x4] = [-x2-x], this reduces to

[x2+x]-1
= [-x4+x3-2x2-x2+x-2]
= [x2+x-x-1-3x2+x-2]
= [-2x2+x-3]
= [3x2+x+2].

15. Factor x4+x+1 over Z2[x] / < x4+x+1>.

Solution: There are 4 roots of x4+x+1 in the given field, given by the cosets corresponding to x, x2, x+1, x2+1. This can be shown by using the multiplication table, with the elements in the form 10, 100, 11, and 101, or by computing with polynomials, using the fact that (a+b)2 =a2+b2 since 2ab=0. We have

x4+x+1 0,

(x2)4+(x2)+1 =(x4)2+x2+1 (x+1)2+x2+1 x2+1+x2+1 0,

(x+1)4 +(x+1)+1 x4+1+x x+1+1+x 0, and

(x2+1)4+(x2+1)+1 (x4)2+1+x2 (x+1)2+1+x2 x2+1+1+x2 0.

Thus x4+x+1 factors as a product of 4 linear terms.

16. In Z5 [x] / < x3+x+1 >, find [x+3][x2+2x+1], and find the multiplicative inverse of [x+3].

Solution: We need to use the identity [x3] = [-x-1]. We have [x+3][x2+2x+1] = [x3+2x2+x+3x2+6x+3] = [x3+2x+3] = [-x-1+2x+3] = [x+2].

Using the Euclidean algorithm to find the multiplicative inverse of [x+3], we find x3+x+1 = (x2+2x)(x+3) + 1, so x3+x+1 - (x2+2x)(x+3) = 1, and [x+3]-1 = [-x2-2x] = [4x2+3x].