Extension fields and multiplicative inverses\251Mike May, S.J., maymk@slu.edu, Saint Louis Universityrestart:Given a field K, and a polynomial f(x), we know that the quotient ring L = K[x]/(f(x)) is a field if and only if f(x) is irreducible. In that case the ideal (f(x)) is both prime and maximal.The proof that L is a field is straight forward, using the maximality of the ideal (f(x)). Unfortunately, the proof that L is a field only gives an existence proof for inverses. It does not give an efficient means to compute in the extension field L This worksheet gives an easy way to use Maple to find inverses, and thus to compute in these extension fields.

We start with the Gaussian rationals, a field in which we know how to compute.The field of Gaussian rationals Q[I], is isomorphic to the quotient ring Q[x]/(NiMsJiokJSJ4RyIiIyIiIkYnRic=). This means that the usual ring operations of addition, subtraction, and multiplication are done by working in the polynomial ring Q[x], then taking the remainder after dividing by NiMsJiokJSJ4RyIiIyIiIkYnRic=. To look at specific cases, let NiQvJSJ1RywmJSJhRyIiIiomJSJiR0YnJSJJR0YnRicvJSJ2RywmJSJjR0YnKiYlImRHRidGKkYnRic=. Compute u + v, u - v, and u*v.u := a + b* x; v := c + d*x; f := x^2 + 1;'u' + 'v' = rem(u + v, f, x); 'u' - 'v' = rem(u - v, f, x); 'u' * 'v' = rem(u * v, f, x);Thus: NiMvLCYlInVHIiIiJSJ2R0YmLCglImFHRiYlImNHRiYqJiwmJSJiR0YmJSJkR0YmRiYlIklHRiZGJg== NiMvLCYlInVHIiIiJSJ2RyEiIiwoJSJhR0YmJSJjR0YoKiYsJiUiYkdGJiUiZEdGKEYmJSJJR0YmRiY= NiMvKiYlInVHIiIiJSJ2R0YmLCgqJiUiYUdGJiUiZEdGJkYmKiYlImJHRiZGK0YmISIiKiYsJkYpRiYqJkYtRiYlImNHRiZGJkYmJSJJR0YmRiY=.The harder problem is doing division, with the sticking point being an efficient method of finding multiplicative inverses. In Q[I], the inverse of NiMvJSJ1RywmJSJhRyIiIiomJSJiR0YnJSJJR0YnRic= is NiMvKiYsJiUiYUciIiIqJiUiYkdGJyUiSUdGJyEiIkYnKiYsJkYmRidGKEYnRidGJUYnRisqJkYlRicsJiokRiYiIiNGJyokRilGMUYnRis=. This rule for inverses is specific to the Gaussian rationals. We need to find a method that produces multiplicative inverses using only the fact that NiMvJSJmRywmKiQlInhHIiIjIiIiRilGKQ== is prime. Such a method could be generalized to other fields.Since NiMlImZH is prime and NiMlInVH is not in the ideal generated by NiMlImZH, the gcd of NiMlInVH and NiMlImZH is 1. This means there are polynomials A and B with NiMvLCYqJiUidUciIiIlIkFHRidGJyomJSJmR0YnJSJCR0YnRidGJw==. In the ring L = Q[x]/(NiMlImZH), NiMvJSJmRyIiIQ==, so the polynomial A will be the multiplicative inverse of NiMlInVH in L We can recover A with the Maple command gcdex.'u' = u; 'f' = f; gcdex(u, f,x, 'uinv', 'g'): u*uinv + f * g; simplify(u*uinv + f * g); 'u'^(-1) = uinv;This gives the correct inverse for u.It will be useful to turn the process above into a procedure we can call.invf := proc(u, f, x) local uinv, g: gcdex(u, f, x, 'uinv', 'g'): uinv; end;Once we have multiplicative inverses it is straight forward to do division.'u'/'v' = rem(u*invf(v, f, x), f, x);

1) Let u and v be defined as above. Compute NiMqJCUidUciIiU=. and NiMqJiUidkciIiIlInVHISIi.2) Compute NiMqJiwmIiIjIiIiKiYiIiRGJiUiSUdGJkYmRigsJiIiJUYmKiYiIiZGJkYpRiZGJiEiIg==, and NiMqJiwmIiImIiIiKiYiIihGJiUiSUdGJkYmRiYqJCwmIiIkRiYqJiIiJUYmRilGJkYmIiInISIi.

The procedure worked out above is valid whenever NiMlImZH is an irreducible polynomial over Q[x]. For a different extension field, you can either change the definition of NiMlImZH , or supply NiMlImZH directly to the procedures defined.The one additional Maple command that may be of use is factor(f);which lets you see if NiMlImZH is irreducible.

3) Let NiQvJSJ1RywmJSJhRyIiIiomJSJiR0YnJSJ4R0YnRicvJSJ2RywmJSJjR0YnKiYlImRHRidGKkYnRic=. Find NiUqJiUidUciIiIlInZHRiUqJEYkIiIlKiZGJUYlRiYhIiI=, and NiMqJiUidUciIiIlInZHISIi when NiMvJSJmRywmKiQlInhHIiIjIiIiIiIkRik=.4) Repeat the previous exercise with NiMvJSJmRywmKiQlInhHIiImIiIiIiIjRik=.

Our general theorem has L = K[x]/(f(x)) being a field, whenever K is a field and f(x) is an irreducible polynomial over K. So far we have been looking at the case when K is Q, the field of rationals. Our other favorite starting field is NiMvJiUiRkc2IyUicEclIlpH/NiMlI3BaRw==, the the prime field of p elements. The procedure outlined above still works in that case, but the Maple syntax changes a little bit. To work over the finite prime fields, we capitalize the Maple commands and append "mod p" to them. Thus we use: Rem(u+v, f, x) mod p; instead of rem(u+v, f, x); Gcdex(u, f, x, 'uinv', 'g') mod p; instead of gcdex(u, f, x, 'uinv', 'g');and Factor(f) mod p; instead of factor(f); Consider the case with NiMvJSJwRyIiJg== and NiMvJSJmRywoKiQlInhHIiIkIiIiRidGKUYpRik=. Verify that NiMlImZH is irreducible over NiMmJSJGRzYjJSJwRw==.p := 5; f := x^3 + x + 1; Factor(f) mod p;Evaluate NiUsJiUidUciIiIlInZHRiUqJkYkRiVGJkYlKiQlInhHIiIk, and NiMqJCUidUciIiQ= in NiMvJSJMRyYlIkZHNiMlInBH/(NiMlImZH).'u' + 'v' = Rem(u+v, f, x) mod p; 'u' * 'v' = Rem(u*v, f, x) mod p; x^3 = Rem(x^3, f, x) mod p; 'u'^3 = expand(u^3); 'u'^3 = Rem(u^3, f, x) mod p;We want a new inverse procedure for fields of finite characteristic.invfp := proc(u, f, x, p) local uinv, g: Gcdex(u, f, x, 'uinv', 'g') mod p: uinv; end;Using this inverse procedure, we do some computations.x^(-1) = invfp(x,f,x,p); 'u'/'v' = Rem(u*invfp(v,f,x,p), f, x) mod p; (2 + 3*x)/(1+x) = Rem((2 + 3*x)*invfp(1 + x,f,x,p), f, x) mod p;

5) Find a cubic polynomial, f, that is irreducible over F[3]. Evaluate NiMqJCUieEciIig= and NiMpJSJ4RywkIiIiISIi in NiMvJSJMRyYlIkZHNiMiIiQ=[x]/(NiMlImZH). Find the multiplicative order of x in L.6) Open your text (Abstract Algebra by Dummit and Foote) to page 431, Section 13.1, and do problems 1, 2, and 3.