{VERSION 5 0 "IBM INTEL NT" "5.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 
0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
257 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 
{CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 
0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times
" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 4 4 1 0 1 0 2 2 0 1 }
{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 1 1 
2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 18 1 
{CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 
12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times
" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 44 "Extension fields and mult
iplicative inverses" }}{PARA 19 "" 0 "" {TEXT -1 54 "\251Mike May, S.J
., maymk@slu.edu, Saint Louis University" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 8 "restart:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 191 "Give
n 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 c
ase the ideal (f(x)) is both prime and maximal." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 363 "The proof that L is a fi
eld is straight forward, using the maximality of the ideal (f(x)).  Un
fortunately, 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 fi
nd inverses, and thus to compute in these extension fields." }}{PARA 
0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG }{EXCHG }{SECT 0 {PARA 4 "" 0 "" 
{TEXT -1 36 "Case 1: The Gaussian rationals, Q[I]" }}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 78 "We start with the Gaussian rationals, a field in w
hich we know how to compute." }}{PARA 0 "" 0 "" {TEXT -1 79 "The field
 of Gaussian rationals Q[I], is isomorphic to the quotient ring Q[x]/(
" }{XPPEDIT 18 0 "x^2 + 1" "6#,&*$%\"xG\"\"#\"\"\"F'F'" }{TEXT -1 184 
").  This means that the usual ring operations of addition, subtractio
n, and multiplication are done by working in the polynomial ring Q[x],
 then taking the remainder after dividing by " }{XPPEDIT 18 0 "x^2 +1
" "6#,&*$%\"xG\"\"#\"\"\"F'F'" }{TEXT -1 34 ".  To look at specific ca
ses, let " }{XPPEDIT 18 0 "u = a + b*I, v = c + d*I" "6$/%\"uG,&%\"aG
\"\"\"*&%\"bGF'%\"IGF'F'/%\"vG,&%\"cGF'*&%\"dGF'F*F'F'" }{TEXT -1 33 "
.  Compute u + v, u - v, and u*v." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 43 "u := a + b* x;  v := c + d*x; f := x^2 + 1;" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 89 "'u' + 'v' = rem(u + v, f, x)
;\n'u' - 'v' = rem(u - v, f, x);\n'u' * 'v' = rem(u * v, f, x);" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 5 "Thus:" }}{PARA 0 "" 0 "" {TEXT -1 
5 "     " }{XPPEDIT 18 0 "u + v = (a + c) + (b + d)* I" "6#/,&%\"uG\"
\"\"%\"vGF&,(%\"aGF&%\"cGF&*&,&%\"bGF&%\"dGF&F&%\"IGF&F&" }}{PARA 0 "
" 0 "" {TEXT -1 5 "     " }{XPPEDIT 18 0 "u - v = (a - c) + (b - d)* I
" "6#/,&%\"uG\"\"\"%\"vG!\"\",(%\"aGF&%\"cGF(*&,&%\"bGF&%\"dGF(F&%\"IG
F&F&" }}{PARA 0 "" 0 "" {TEXT -1 5 "     " }{XPPEDIT 18 0 "u * v = (a \+
* d - b * d) + (a * d + b * c)* I" "6#/*&%\"uG\"\"\"%\"vGF&,(*&%\"aGF&
%\"dGF&F&*&%\"bGF&F+F&!\"\"*&,&*&F*F&F+F&F&*&F-F&%\"cGF&F&F&%\"IGF&F&
" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 149 "The harder p
roblem is doing division, with the sticking point being an efficient m
ethod of finding multiplicative inverses.  In Q[I], the inverse of " }
{XPPEDIT 18 0 "u = a + b * I" "6#/%\"uG,&%\"aG\"\"\"*&%\"bGF'%\"IGF'F'
" }{TEXT -1 4 " is " }{XPPEDIT 18 0 "(a - b *I)/((a + b*I)*(a - b*I)) \+
= (a - b*I)/(a^2 + b^2)" "6#/*&,&%\"aG\"\"\"*&%\"bGF'%\"IGF'!\"\"F'*&,
&F&F'*&F)F'F*F'F'F',&F&F'*&F)F'F*F'F+F'F+*&,&F&F'*&F)F'F*F'F+F',&*$F&
\"\"#F'*$F)F6F'F+" }{TEXT -1 154 ".  This rule for inverses is specifi
c to the Gaussian rationals.  We need to find a method that produces m
ultiplicative inverses using only the fact that " }{XPPEDIT 18 0 "f = \+
x^2 + 1" "6#/%\"fG,&*$%\"xG\"\"#\"\"\"F)F)" }{TEXT -1 63 " is prime.  \+
Such a method could be generalized to other fields." }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 6 "Since " }{XPPEDIT 18 0 "f" "6#%\"fG" }{TEXT -1 
14 " is prime and " }{XPPEDIT 18 0 "u" "6#%\"uG" }{TEXT -1 34 " is not
 in the ideal generated by " }{XPPEDIT 18 0 "f" "6#%\"fG" }{TEXT -1 
14 ", the gcd of  " }{XPPEDIT 18 0 "u" "6#%\"uG" }{TEXT -1 6 "  and " 
}{XPPEDIT 18 0 "f" "6#%\"fG" }{TEXT -1 54 " is 1.  This means there ar
e polynomials A and B with " }{XPPEDIT 18 0 "u*A + f *B = 1" "6#/,&*&%
\"uG\"\"\"%\"AGF'F'*&%\"fGF'%\"BGF'F'F'" }{TEXT -1 25 ".  In the ring \+
L = Q[x]/(" }{XPPEDIT 18 0 "f" "6#%\"fG" }{TEXT -1 4 "),  " }{XPPEDIT 
18 0 "f = 0" "6#/%\"fG\"\"!" }{TEXT -1 63 ", so the polynomial A will \+
be the multiplicative  inverse of   " }{XPPEDIT 18 0 "u" "6#%\"uG" }
{TEXT -1 54 "  in L  We can recover A with the Maple command gcdex." }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 104 "'u' = u; 'f' = f;\ngcdex(
u, f,x, 'uinv', 'g'):\nu*uinv + f * g;\nsimplify(u*uinv + f * g);\n'u'
^(-1) = uinv;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "This gives the c
orrect inverse for u." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 
"" {TEXT -1 73 "It will be useful to turn the process above into a pro
cedure we can call." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 108 "inv
f := proc(u, f, x)\n        local uinv, g:\n        gcdex(u, f, x, 'ui
nv', 'g'):\n        uinv;\n        end;" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 75 "Once we have multiplicative inverses it is straight forwa
rd to do division." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "'u'/'
v' = rem(u*invf(v, f, x), f, x);" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 
0 "" }{TEXT 256 10 "Exercises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "
1)  Let u and v be defined as above.  Compute " }{XPPEDIT 18 0 "u^4" "
6#*$%\"uG\"\"%" }{TEXT -1 6 ". and " }{XPPEDIT 18 0 "v/u" "6#*&%\"vG\"
\"\"%\"uG!\"\"" }{TEXT -1 1 "." }}}{EXCHG }{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 12 "2)  Compute " }{XPPEDIT 18 0 "(2+3*I)^3/(4 + 5*I)" "6#*&,
&\"\"#\"\"\"*&\"\"$F&%\"IGF&F&F(,&\"\"%F&*&\"\"&F&F)F&F&!\"\"" }{TEXT 
-1 6 ", and " }{XPPEDIT 18 0 "(5+7*I)/(3 +4*I)^6" "6#*&,&\"\"&\"\"\"*&
\"\"(F&%\"IGF&F&F&*$,&\"\"$F&*&\"\"%F&F)F&F&\"\"'!\"\"" }{TEXT -1 1 ".
" }}}{EXCHG }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 60 "Case II, L = Q[x]/
(f(x)) for an irreducible polynomial f(x) " }}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 51 " The procedure worked out above is valid whenever  " }
{XPPEDIT 18 0 "f" "6#%\"fG" }{TEXT -1 119 "  is an irreducible polynom
ial over Q[x].  For a different extension field, you can either  chang
e the definition of   " }{XPPEDIT 18 0 "f" "6#%\"fG" }{TEXT -1 16 "  ,
 or supply   " }{XPPEDIT 18 0 "f" "6#%\"fG" }{TEXT -1 38 "   directly \+
to the procedures defined." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 
"" 0 "" {TEXT -1 54 "The one additional Maple command that may be of u
se is" }}{PARA 0 "" 0 "" {TEXT -1 15 "     factor(f);" }}{PARA 0 "" 0 
"" {TEXT -1 24 "which lets you see if   " }{XPPEDIT 18 0 "f" "6#%\"fG
" }{TEXT -1 17 "  is irreducible." }}}{SECT 0 {PARA 5 "" 0 "" {TEXT 
-1 0 "" }{TEXT 257 10 "Exercises:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
9 "3)  Let  " }{XPPEDIT 18 0 "u = a + b*x,  v = c + d*x" "6$/%\"uG,&%
\"aG\"\"\"*&%\"bGF'%\"xGF'F'/%\"vG,&%\"cGF'*&%\"dGF'F*F'F'" }{TEXT -1 
9 ".  Find  " }{XPPEDIT 18 0 "u*v, u^4, 1/v" "6%*&%\"uG\"\"\"%\"vGF%*$
F$\"\"%*&F%F%F&!\"\"" }{TEXT -1 6 ", and " }{XPPEDIT 18 0 "u/v" "6#*&%
\"uG\"\"\"%\"vG!\"\"" }{TEXT -1 10 "   when   " }{XPPEDIT 18 0 "f = x^
2 + 3" "6#/%\"fG,&*$%\"xG\"\"#\"\"\"\"\"$F)" }{TEXT -1 1 "." }}}
{EXCHG }{EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "4)  Repeat the previous ex
ercise with  " }{XPPEDIT 18 0 "f = x^5 + 2" "6#/%\"fG,&*$%\"xG\"\"&\"
\"\"\"\"#F)" }{TEXT -1 1 "." }}}{EXCHG }}}{SECT 0 {PARA 4 "" 0 "" 
{TEXT -1 24 "Case III, Finite fields " }}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 241 "Our general theorem has  L = K[x]/(f(x)) being a field, whenev
er 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  " }{XPPEDIT 18 0 "F[p] = Z" "6#
/&%\"FG6#%\"pG%\"ZG" }{TEXT -1 1 "/" }{XPPEDIT 18 0 "pZ" "6#%#pZG" }
{TEXT -1 251 ",   the the prime field of p elements.  The procedure ou
tlined above still works in that case, but the Maple syntax changes a \+
little bit.  To work over the finite prime fields, we capitalize the M
aple commands and append \"mod p\" to them.  Thus we use:" }}{PARA 0 "
" 0 "" {TEXT -1 79 "      Rem(u+v, f, x) mod p;                 instea
d of          rem(u+v, f, x);" }}{PARA 0 "" 0 "" {TEXT -1 91 "      Gc
dex(u, f, x, 'uinv', 'g') mod p;    instead of         gcdex(u, f, x, \+
'uinv', 'g');" }}{PARA 0 "" 0 "" {TEXT -1 3 "and" }}{PARA 0 "" 0 "" 
{TEXT -1 78 "     Factor(f) mod p;                           instead o
f          factor(f);" }}{PARA 0 "" 0 "" {TEXT -1 2 "  " }}{PARA 0 "" 
0 "" {TEXT -1 25 "Consider the case with   " }{XPPEDIT 18 0 "p = 5" "6
#/%\"pG\"\"&" }{TEXT -1 7 "  and  " }{XPPEDIT 18 0 "f = x^3 + x + 1" "
6#/%\"fG,(*$%\"xG\"\"$\"\"\"F'F)F)F)" }{TEXT -1 17 ".  Verify that   \+
" }{XPPEDIT 18 0 "f " "6#%\"fG" }{TEXT -1 23 "  is irreducible over  \+
" }{XPPEDIT 18 0 "F[p]" "6#&%\"FG6#%\"pG" }{TEXT -1 1 "." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "p := 5;\nf := x^3 + x + 1;\nFactor(
f) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 10 "Evaluate  " }
{XPPEDIT 18 0 "u + v,  u * v,  x^3" "6%,&%\"uG\"\"\"%\"vGF%*&F$F%F&F%*
$%\"xG\"\"$" }{TEXT -1 7 ",  and " }{XPPEDIT 18 0 "u^3" "6#*$%\"uG\"\"
$" }{TEXT -1 4 " in " }{XPPEDIT 18 0 "L = F[p]" "6#/%\"LG&%\"FG6#%\"pG
" }{TEXT -1 2 "/(" }{XPPEDIT 18 0 "f" "6#%\"fG" }{TEXT -1 2 ")." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 147 "'u' + 'v' = Rem(u+v, f, x) \+
mod p;\n'u' * 'v' = Rem(u*v, f, x) mod p;\nx^3 = Rem(x^3, f, x) mod p;
\n'u'^3 = expand(u^3); \n'u'^3 = Rem(u^3, f, x) mod p;" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 69 "We want a new inverse procedure for field
s of finite charachteristic." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 118 "invfp := proc(u, f, x, p)\n        local uinv, g:\n        Gcde
x(u, f, x, 'uinv', 'g') mod p:\n        uinv;\n        end;" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Using this inverse procedure, we d
o some computations." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 134 "x^
(-1) = invfp(x,f,x,p);\n'u'/'v' = Rem(u*invfp(v,f,x,p), f, x) mod p;\n
(2 + 3*x)/(1+x) = Rem((2 + 3*x)*invfp(1 + x,f,x,p), f, x) mod p;" }}}
{SECT 0 {PARA 5 "" 0 "" {TEXT -1 10 "Exercises:" }}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 66 "5)  Find a cubic polynomial,  f,  that is irreducibl
e over F[3].  " }}{PARA 0 "" 0 "" {TEXT -1 14 "     Evaluate " }
{XPPEDIT 18 0 "x^7" "6#*$%\"xG\"\"(" }{TEXT -1 5 " and " }{XPPEDIT 18 
0 "x^(-1)" "6#)%\"xG,$\"\"\"!\"\"" }{TEXT -1 5 " in  " }{XPPEDIT 18 0 
"L = F[3]" "6#/%\"LG&%\"FG6#\"\"$" }{TEXT -1 5 "[x]/(" }{XPPEDIT 18 0 
"f" "6#%\"fG" }{TEXT -1 2 ")." }}{PARA 0 "" 0 "" {TEXT -1 45 "     Fin
d the multiplicative order of x in L." }}}{EXCHG }{EXCHG }{EXCHG }
{EXCHG }}}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }
{PAGENUMBERS 0 1 2 33 1 1 }