Topics in Algebra, Chapter 3.9

2013-02-06 math algebra topics-in-algebra

This page covers section 3.9 (“Polynomial Rings”). Throughout, F is a field.

Topics covered: 3.9

  • F[x]={a0+a1x+anxnnN,a0,,anF} is the set of polynomials with coefficients from the field F.

  • Addition, multiplication and equivalence of polynomials are defined in the obvious ways.

  • Definition: The degree of non-zero fF[x], deg(f), is the coefficient of the highest non-zero power of x in f. The degree is not defined for the zero polynomial.

  • Lemma 3.9.1: If f,gF[x] are non-zero, then deg(fg)=deg(f)+deg(g).

  • Corollary: F[x] is an integral domain.

  • Lemma 3.9.2: Given f,gF[x], g0, there exist r,tF[x] such that f(x)=t(x)g(x)+r(x) with either r=0 or deg(r)<deg(g). This is the Euclidean algorithm.

  • Theorem 3.9.1: F[x] is a Euclidean ring with deg used as norm.

The problems below are paraphrased from/inspired by those given in Topics in Algebra by Herstein. The solutions are my own unless otherwise noted. I will generally try, in my solutions, to stick to the development in the text. This means that problems will not be solved using ideas and theorems presented further on in the book.

Herstein 3.9.1: Find the greatest common divisor in Q[x] of

(a) x36x2+x+4 and x56x+1.

(b) x2+1 and x6+x3+x+1.

(a) Unlike the exercise on Gaussian integer divisors, polynomial long division takes away any interesting guess work in computing the greatest common divisor (we use the algorithm in problem 3.7.4). The numbers for this particular example work out horrendously, but we find (in the notation of 3.7.4) that r3=773017657121

which is a unit in Q, so x36x2+x+4 and x56x+1 are coprime in Q[x].

(b) In stark contrast to the hideous arithmetic of part (a), we find that x2+1 actually divides x6+x3+x+1. Specifically, x6+x3+x+1=(x4x2+x+1)(x2+1)

so their greatest common divisor is x2+1.

Herstein 3.9.2:

(a) Show that x2+x+1 is irreducible over F2=Z/2Z.

(b) Show that x2+1 is irreducible over F7=Z/7Z.

(c) Show that x39 is irreducible over F31=Z/31Z.

(d) Show that x39 is reducible over F11=Z/11Z.

(a) Suppose that x2+x+1=a(x)b(x) with a,bF2[x], neither being a constant. Then we must have deg(a)=deg(b)=1. Write a(x)=αx+β and b(x)=γx+δ, where α,β,γ,δF2 can each take only the values 0 or 1. Expanding the product, we have αγ=1 which implies α=γ=1, and βδ=1 implies β=δ=1. Then the cross term is αδ+βγ=0F2, but the coefficient of x is supposed to be 1. Thus x2+x+1 can not be factored unless one of the factors is a unit, so it is irreducible.

(b) As before, let us try to write x2+1=(αx+β)(γx+δ). We find by expanding that γ=α1 and δ=β1. In fact, we can factor out α and α1 to get x2+1=(x+α1β)(x+αβ1). Equivalently, just call αβ1=η. Then we have x2+1=(x+η)(x+η1)

which has us conclude that η+η1=0. But then 1=ηη1=η2mod7.

However, because 7 is a 4k+3 prime, this is not possible (problem 3.8.4) and therefore x2+1 is irreducible over F7. Note that this argument fails if we work over other fields such as Z/5Z. In that case, we have 221mod5 and 21=3, so (x+2)(x+3)=x2+5x+6=x2+1.

(c) If x39 is reducible, then it must have at least one linear factor by simple considerations of degree. We can therefore write a proposed factorization as x39=(x+α)(x2+βx+γ).

The coefficients give conditions β=α, γ=αβ and αγ=9. Combining all three, we find that α3=9=22mod31.

By brute force we see that this can never happen, so x39 is irreducible over F31.

Alternately, as suggested in this post, we note that F31× is a cyclic group of order 30 so that α30=1. Then if 22 is expressible as a cube, it must be the case that 22101mod31. However, we can easily show that 22105mod31: first switch back to computing (9)10 because 9 is smaller and easier to square by hand. We have 92=12 and then 94=144=11 and 98=121=3. Finally, plugging back in, we get (9)10=9892=(3)(12)=5mod31.

This shows that 9 is not the cube of any number in F31, so the polynomial is irreducible.

(d) The same reasoning as above brings us to the condition α3=2mod11. This can be simplified slightly by applying Fermat’s little theorem. We can see that 5=24=(α3)4=α11α=α2mod11.

From here it can easily be brute forced by hand, and we find that α=7 so β=7 and γ=5 constitutes a solution. Specifically, x39=(x+7)(x27x+5)

over Z/11Z. It is immaterial whether x27x+5 factors further (it doesn’t), because the object was simply to show that x39 is reducible.

Herstein 3.9.3: Let FK be two fields and suppose f,gF[x] are relatively prime. Show that they are relatively prime in K[x].

Because f and g are relatively prime in F[x], there exist α,βF[x] such that α(x)f(x)+β(x)g(x)=1

for all x. The elements α and β also belong to K[x], so this identity holds there, too.

Herstein 3.9.4: Let F=Z/11Z.

(a) Prove that x2+1 is irreducible over F and explicitly prove that F[x]/(x2+1) is a field with 121 elements.

(b) Prove that x2+x+4 is irreducible over F and explicitly prove that F[x]/(x2+x+4) is a field with 121 elements.

(c) Prove that F[x]/(x2+1)F[x]/(x2+x+4).

(a) x2+1 is irreducible over F by precisely the same argument as in problem 3.9.2b. Denote the ideal (x2+1) by I. We have defined F[x]/I={f+IfF[x]},

and we see by the Euclidean algorithm that any representative fF[x] may be written as f(x)=q(x)(x2+1)+r(x)

with r=0 or deg(r)<2 by the Euclidean algorithm. Hence f(x)+I=r(x)+I. We can express r(x)=αx+β, where α,βF each have 11 possible values. Therefore we can enumerate 121 elements in F[x]/I. It is conceivable that there is some overcounting, but if αx+β+I=αx+β+I

then x2+1 must divide (αα)x+(ββ). This is only possible if both coefficients are zero, so α=α and β=β and we must have no duplicates. Therefore there are 121 elements in F[x]/I.

To show that F[x]/I is a field, we take the properties of a ring for granted and would just like to show that every element has a multiplicative inverse. That is, we would like to explicitly produce an inverse of the arbitrary element αx+β+IF[x]/I. If α=0 and β0, then the inverse is β1+I; if β=0 and α0, the inverse is α1x+I because (αx)(α1x)+I=x2+I=1(x2+1)+I=1+I.

Therefore we are left to solve (αx+β)(γx+δ)+I=1+I

for γ and δ, with α,β0. Comparing coefficients quickly indicates the forms γ=ηα1 and δ=ηβ1. Then 1+I=(αx+β)(ηα1x+ηβ1)+I=η(αβ1+(αβ1)1)+I.

It will always be possible to solve this if the latter term in parentheses is non-zero, because η can be chosen as its inverse. Suppose that, for some xF, x+x1=0. Then 1=xx1=x2 or x21mod11. This we know to be impossible by problem 3.8.4. Therefore if we take η=(αβ1+(αβ1)1)1

then the inverse of αx+β+I in F[x]/I is given by η(α1x+β1)+I and, consequently, F[x]/I is a field.

(b) Suppose that x2+x+4 factors in F[x] as x2+x+4=(αx+β)(γx+δ)

with α,β,γ,δF. Then we find γ=α1 and δ=4β1 (ignoring the trivial possibilities that α=0 or β=0) and, plugging in and extracting a factor of 1=αα1, we see that x2+x+4=(x+α1β)(x+4αβ1).

The condition on the x coefficient is then α1β+4αβ1=1 which may be restated as t+4t1=1 for some tF. If we can show that there is no solution to this last equation, then we have shown that x2+x+4 is irreducible over F. Multiply through by t to get t2t+4=0 or t2t+3=1. Now, modulo 11, we have that (t+5)2=t2+10t+25=t2t+3

and we know that (t+5)21mod11 is not possible. Therefore the polynomial is irreducible over F.

Letting J=(x2+x+4), the Euclidean algorithm argument from part (a) shows that there are exactly 121 elements in F[x]/J. Again, we would like to explicitly produce an inverse of αx+β+J in F[x]/J. If α=0 and β0, then the inverse is simply β1+J. If β=0 and α0, then we have 1+J=(αx)(γx+δ)+J=αγx2+αδx+J.

Write this as 1+J=αγ(x2+x+4)+αδxαγx4αγ+J=α(δγ)x4αγ+J.

Then we have δ=γ and 4αγ=1 modulo 11. The latter equation is solved by multiplying through by 8α1. Thus (αx)(8α1x+8α1)+J=1+J.

Finally, we come to the case of α,β0. If (αx+β)(γx+δ)+J=1+J, then the same trick of adding and subtracting terms gives (αδ+βγαγ)x+(βδ4αγ)+J=1+J.

Then δ=β1+4αβ1γ and so 0=αδ+βγαγ=αβ1(αβ4α2β1)γ.

Can αβ4α2β1=0? Multiply through by α1 to put it in the form t2t4=0

where t=βα1. As shown above, this is equivalent to (t+5)2=1 which is not possible modulo 11. Hence we can always solve for γ=αβ1(αβ4α2β1)1,

so the inverse is constructed and F[x]/J is a field.

(c) We would like to construct an explicit isomorphism ϕ:F[x]/IF[x]/J. An important first question is whether such a ϕ can refer to the coefficients α and β of αx+β+I in a well-defined way. The answer is yes: if αx+β+I=αx+β+I, then (αα)x+(ββ) is divisible by x2+1. This is only possible if both coefficients are zero, so α=α and β=β.

A natural guess for the isomorphism is the simple ϕ(αx+β+I)=αx+β+J. A homomorphism must satisfy ϕ(ab)=ϕ(a)ϕ(b) for a,bF[x]/I. However, we can see, for example, that ϕ((x+I)2)=ϕ((x2+1)1+I)=ϕ(1+I)=1+J

while ϕ(x+I)2=x2+J=(x2+x+4)(x+4)+J=(x+4)+J

so this map fails to be a homomorphism.

If we work from the restriction that ϕ be a homomorphism, we know that ϕ(αx+β+I)=ϕ(α+I)ϕ(x+I)+ϕ(β+I).

Then the map will be fully determined by computing its action on 1+I and x+I. We know by problem 3.4.20 that if ϕ is an isomorphism then it maps onto F[x]/J and thus ϕ(1+I)=1+J. From this, it easily follows that ϕ(α+I)=α+J for any αF. For x+I, we have 1+J=ϕ(1+I)=ϕ((x2+1)1+I)=ϕ(x2+I)=ϕ(x+I)2.

This implies that ϕ(x+I) must be an element of F[x]/J which squares to 1+J=x2+x+3+J. Such an element is x5+J, because (x5+J)2=x210x+25+J=x2+x+3+J.

So we posit that ϕ:F[x]/IF[x]/J defined by ϕ(αx+β+I)=αx+β5α+J

is an isomorphism. The only non-trivial property to check is that ϕ respects products. Letting α,β,γ,δF, we have ϕ((αx+β)(γx+δ)+I)=ϕ((αδ+βγ)x+(βδαγ)+I)=(αδ+βγ)x+(βδαγ5αδ5βγ)+J\begin{aligned} \phi((\alpha x+\beta)(\gamma x+\delta)+I)&=\phi((\alpha\delta+\beta\gamma)x+(\beta\delta-\alpha\gamma)+I)\ &=(\alpha\delta+\beta\gamma)x+(\beta\delta-\alpha\gamma-5\alpha\delta-5\beta\gamma)+J \end{aligned}

while ϕ(αx+β+I)ϕ(γx+δ+I)=αγx2+(α(δ5γ)+γ(β5α))x+(β5α)(δ5γ)+J=αγ(x2+x+4)+(α(δ5γ)+γ(β5α)αγ)x+(β5α)(δ5γ)4αγ+J=(αδ+βγ)x+(βδαγ5αδ5βγ)+J.\begin{aligned} \phi(\alpha x+\beta+I)\phi(\gamma x+\delta+I)&\ =&\alpha\gamma x^2+(\alpha(\delta-5\gamma)+\gamma(\beta-5\alpha))x+(\beta-5\alpha)(\delta-5\gamma)+J\ =&\alpha\gamma(x^2+x+4)+(\alpha(\delta-5\gamma)+\gamma(\beta-5\alpha)-\alpha\gamma)x\ &+(\beta-5\alpha)(\delta-5\gamma)-4\alpha\gamma+J\ =&(\alpha\delta+\beta\gamma)x+(\beta\delta-\alpha\gamma-5\alpha\delta-5\beta\gamma)+J. \end{aligned}

Therefore ϕ respects the ring product. It is very easy to check that it respects ring addition and that it is injective, and so we have proven that F[x]/IF[x]/J.

Herstein 3.9.5: Letting F=R, show that F[x]/(x2+1)C as fields.

First we show that x2+1 is irreducible over F. Suppose that x2+1=(αx+β)(γx+δ). Then, comparing coefficients, αγ=1 and βδ=1 imply that α,β0, γ=1/α and δ=1/β. Then the middle coefficient says 0=αδ+βγ=αβ+βα. This gives α2=β2 which in turn implies that α=β=0, a contradiction.

Therefore x2+1 is irreducible over F and lemma 3.9.6 says that I=(x2+1) is maximal in F[x]. Theorem 3.5.1 then says that F[x]/I is a field much like the one studied in problem 3.9.4a. The elements look like α+βx+I with α,βF. The obvious choice for a map to C is ϕ(α+βx+I)=α+iβ

which is well-defined by the comments made in 3.9.4c. One has to be a little careful here: αx+βα+iβ (with the α and β flipped from the definition above) fails to respect the ring multiplication. With the definition of ϕ, we have ϕ((α+βx)(γ+δx)+I)=ϕ(αγβδ+(βγ+αδ)x+I)=αγβδ+(βγ+αδ)i=(α+iβ)(γ+iδ).\begin{aligned} \phi((\alpha+\beta x)(\gamma+\delta x)+I)&=\phi(\alpha\gamma-\beta\delta+(\beta\gamma+\alpha\delta)x+I)\ &=\alpha\gamma-\beta\delta+(\beta\gamma+\alpha\delta)i=(\alpha+i\beta)(\gamma+i\delta). \end{aligned}

The additive property ϕ(a+b)=ϕ(a)+ϕ(b) is very easy to show, so ϕ is a homomorphism. It is also trivially surjective because α+βi is the image of α+βx+I, and trivially injective because ϕ(α+βx+I)=ϕ(αx+β+I) implies (αα)+i(ββ)=0 or α=α and β=β. Therefore, F[x]/IC.

Herstein 3.9.6*: Let F=Q and define the formal derivative fF[x] of polynomial fF[x] in the usual way. Prove that f(x) is divisible by the square of a non-constant polynomial if and only if f(x) and f(x) have a greatest common divisor d(x) of positive degree.

Note that, over Q, the degree of a polynomial’s derivative is exactly one less than the degree of the polynomial. In other fields, this may not be the case. For instance, the derivative of x2 over Z/2Z is zero.

First suppose that fF[x] is divisible by the square of a non-constant polynomial pF[x], writing f(x)=p(x)2q(x).

Then the derivative is f(x)=2p(x)q(x)p(x)+p(x)2q(x) so that pf. As p is a common divisor, it also divides the greatest common divisor d, and so deg(d)deg(p) as desired.

On the other hand, suppose that we know f(x) and f(x) have a non-trivial greatest common divisor d(x). Factor d into primes as d(x)=π1(x)πN(x)

and take any of the primes, say π1. We have that π1 is a common divisor of f and f, so write f(x)=π1(x)p(x) and f(x)=π1(x)q(x). We can also compute the derivative by the chain rule, which gives f(x)=π1(x)p(x)+π1(x)p(x). Equating the two representations gives (q(x)p(x))π1(x)=p(x)π1(x).

Because π1 is prime, it divides either p(x) or π1(x). The latter is impossible, because deg(π1) is strictly smaller than deg(π1). Therefore π1p and π12f.

Herstein 3.9.7: Let F=Z/pZ with p prime, and let fF[x] be irreducible and have degree n. Prove that F[x]/(f) is a field with pn elements.

By lemma 3.9.6, (f) is maximal and, by theorem 3.5.1, F[x]/(f) is a field. A generic element in F[x]/(f) is g+(f) where gF[x]. By the division algorithm, we can write g(x)=q(x)f(x)+r(x)

where r=0 or deg(r)<deg(f). Therefore, g+(f)=r+(f) and so we will always be able to identify an equivalence class by a polynomial of degree smaller than n. The representative of any equivalence class can be written r(x)=a0+a1x++an1xn1

where aiF for each i=1,,n1. With p choices for each of the n coefficients, there are at most pn equivalence classes comprising F[x]/(f). However, there are also no duplicates. Indeed, if r+(f)=r+(f), then rr is divisible by f. Because each of r and r has degree smaller than n, so does their difference. The only way for the difference to be divisible by f is if it is zero, i.e. if r=r. Therefore each of the pn polynomials described above represents a unique equivalence class, and F[x]/(f) has pn elements.

comments powered by Disqus