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