{VERSION 3 0 "SGI MIPS UNIX" "3.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 33 "The extended Euclidean Alg
orithm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
249 "If a and b are positive integers, and d is the gcd, then we have \+
that the ideal (d) equals the ideal (a,b), so: Z*d = Z*a + Z*b. In oth
er words: a and b are Z-linear combinations of d (i.e. multiples of d)
 and d is a Z-linear combination of a and b." }}{PARA 0 "" 0 "" {TEXT 
-1 112 "So d = s*a + t*b for some integers s and t. These s and t can \+
be computed with the Extended Euclidean Algorithm." }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 6 "a:=72;" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 6 "b:=50;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "d
:=igcdex(a,b,'s','t');" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "s
*a + t*b;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "s;" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "t;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 113 "Note that s and t are not uniquely determined. If you replace \+
[s,t] by [s + b, t - a] you'll get the same result." }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 17 "s, t := s+b, t-a;" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 10 "s*a + t*b;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 233 "Of course, by adding or substracting a suitable multiple of [b
,-a] to [s,t] we can get s in the range 0..b-1, and then s,t will be u
niquely determined. Or we could bring t in the range -(a-1) .. 0, that
 would give us the same result." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 44 "For polynomials this all works very simil
ar." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "a:=x^3-1;" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "b:=x^4-1;" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 24 "d:=gcdex(a,b,x,'s','t');" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 8 "s*a+t*b;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 10 "expand(%);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "If R is the \+
ring Q[x], the ideal (a,b)=R*a+R*b equals the ideal (d)=R*d, so d is a
n R-linear combination of a and b." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 12 "d = s*a+t*b." }}{PARA 0 "" 0 "" {TEXT -1 
86 "This equation will still hold if we replace [s,t] by [s,t] + some \+
multiple of [b, -a]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "exp
and(s*a+t*b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "ra:=randpo
ly(x,degree=2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "s, t := \+
expand(s+ra*b), expand(t-ra*a);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 16 "expand(s*a+t*b);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 425 "So i
f ra is some arbitrary polynomial, we can add ra*b to s (and substract
 ra*a from t) and the equation s*a+t*b=d remains valid. If s is an ele
ment of Q[x], we have seen that we can always find a unique polynomial
 q such that s-q*b will have degree < degree(b). Namely, q is the quot
ient of the division of s by b. So we can make the solution [s,t] of t
he equation s*a+t*b=d unique by requiring that degree(s,x)<degree(b,x)
." }}{PARA 0 "" 0 "" {TEXT -1 110 "If you compare degrees in this equa
tion you will see that this condition implies that degree(t,x)<degree(
a,x)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 106 
"Concluding: If a and b are polynomials, and d is the gcd, then there \+
are unique polynomials s,t such that:" }}{PARA 0 "" 0 "" {TEXT -1 14 "
1) d = s*a+t*b" }}{PARA 0 "" 0 "" {TEXT -1 26 "2) degree(s,x)<degree(b
,x)" }}{PARA 0 "" 0 "" {TEXT -1 27 "3) degree(t,x)<degree(a,x)." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 131 "Now we w
ill study how to compute these s and t, in the case of polynomials. Th
e case of integers (the igcdex) works very similarly." }}{PARA 0 "" 0 
"" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 118 "In the Euclidean Algo
rithm we reduce the ideal (a,b) to the ideal (a',b) where a'=rem(a,b,x
)=a-q*b where q=quo(a,b,x)." }}{PARA 0 "" 0 "" {TEXT -1 47 "Then, by r
ecursion we can find s',t' such that:" }}{PARA 0 "" 0 "" {TEXT -1 36 "
s'*a' + t'*b = d where d is the gcd." }}{PARA 0 "" 0 "" {TEXT -1 25 "S
o s'*(a-q*b) + t'*b = d." }}{PARA 0 "" 0 "" {TEXT -1 25 "So s'*a  + (t
'-s'*q) = d." }}{PARA 0 "" 0 "" {TEXT -1 36 "So we should take s,t = s
', t'-s'*q." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 21 "Let's implement this." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 466 "GCDEX:=proc(a,b,x)\n  # Produce d,s,t such that:\n  # d = gcd(a
,b)\n  # d = s*a+t*b\n  # degree(s,x)<degree(b,x)\n  # degree(t,x)<deg
ree(a,x)\n  local c,r,q,d,s,t;\n  if b=0 then\n      c:=content(a,x);
\n      # The following line avoids that it gives gcd = -1.\n      if \+
a/c = -1 then c:=-c fi;\n      a/c, 1/c, 0\n  else\n      r:=rem(a,b,x
,'q');\n      # interchange s,t because I interchanged a (or r) and b.
\n      d,t,s := procname(b,r,x);\n      d, s, expand(t-s*q)\n  fi\nen
d;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "a;" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 2 "b;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 20 "d,s,t:=GCDEX(a,b,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
16 "expand(s*a+t*b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "a:=
x^50-1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "b:=x^32-1;" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "d,s,t:=GCDEX(a,b,x);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(s*a+t*b);" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "d;" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "You can veri
fy that the conditions on the degrees of s and t will hold when we use
 our algorithm GCDEX." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 
"" {TEXT -1 413 "Previous time we looked at the ring Q[x]/(f) where f \+
is an element of Q[x]. Every element in this ring can be represented u
niquely by a polynomial in x of degree smaller than degree(f,x). We ca
n add and multiply in this ring, when we multiply and the result would
 get result >= degree(f,x) then you just reduce modulo f, i.e. you rep
lace your result by rem(result,f,x) and it will have degree < degree(f
,x) again." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 127 "So we know how to add and multiply in the ring Q[x]/(f). Basic
ally all we need for that are the Maple functions expand and rem." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 478 "Now we w
ant to divide as well. Suppose that g in Q[x]/(f), so we can represent
 g uniquely by a polynomial of degree < degree(f,x). We want to do div
isions, so we want to compute 1/g if it exists. In other words, we wan
t to find (if it exists) an element t of Q[x]/(f) such that t*g = 1. I
n the ring Q[x]/(f) a polynomial equals 1 when its remainder modulo f \+
is 1. So this means that when g is given by a polynomial in Q[x], that
 we want to find a polynomial t in Q[x] such that:" }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 23 "  rem( t*g, f, x)  = 1." 
}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "In othe
r words: t*g = q*f + r  where q = quo(s*g,f,x) and r=rem(s*g,f,x)=1." 
}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "So:  s*
f + t*g = 1  where t = -q." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 
"" 0 "" {TEXT -1 63 "This means: 1 is in the ideal (f,g), in other wor
ds gcd(f,g)=1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 102 "Conclusion: There exists a polynomial t in Q[x] such tha
t t*g=1 in Q[x]/(f) if and only if gcd(f,g)=1." }}{PARA 0 "" 0 "" 
{TEXT -1 63 "Furthermore: we can find t by the Extended Euclidean Algo
rithm." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "f:=x^3-2;" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "g:=x^2-5*x+3;" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "d, s, t := GCDEX(f,g,x);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "t;" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 63 "So the gcd is 1. And t*g should now be 1 modulo f. Let'
s check:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "g*t;" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(%);" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 11 "rem(%,f,x);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
60 "One more example. Take g = x. So we're going to compute 1/x." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 121 "Note tha
t Q[x]/(x^3-2) is isomorphic to Q[ 2^(1/3) ], so computing 1/x is just
 like computing 1/2^(1/3). And we know that" }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "1 / 2^(1/3) =  1/2 * ( 2^(1/3) \+
)^2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 5 "g:=x;" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 22 "d,s,t := GCDEX(f,g,x);" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 2 "t;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 125 "Every elem
ent g in Q[x]/(f) is represented by a polynomial of degree < degree(f,
x). Now 1/g exists if and only if gcd(f,g)=1." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 131 "Suppose now that f is an
 irreducible element of Q[x], i.e. there do not exist polynomials f1, \+
f2 of lower degree such that f1*f2=f." }}{PARA 0 "" 0 "" {TEXT -1 0 "
" }}{PARA 0 "" 0 "" {TEXT -1 275 "Then you will see that every non-zer
o polynomial g of degree < degree(f,x) will have no factors in common \+
with f, because f simply doesn't have any non-trivial factors of degre
e < degree(f,x). In other words: every non-zero g in Q[x]/(f) will hav
e an inverse 1/g in Q[x]/(f)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 194 "Q[x]/(f) is a commutative ring, i.e. we \+
can add and multiply and multipication is commutative. If f is irreduc
ible then we can also divide by any non-zero element. Such a ring is c
alled a field." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 158 "Note that if f is reducible, suppose f = f1*f2 with degr
ees f1,f2 smaller than degree of f, then you could not divide by f1 in
 the ring Q[x]/(f). We conclude:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 71 "Q[x]/(f) is a field if and only if f is a
n irreducible element of Q[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 749 "When f i
s an irreducible polynomial we can multiply in the field Q[x]/(f) by e
xpand and rem. We can divide by the Extended Euclidean Algorithm (call
ed gcdex in Maple, for the help page type ?gcdex ). It would be easier
 to be able to just write * and / for products and quotients, and to h
ave only one Maple command that will evaluate expressions in the ring \+
Q[x]/(f). This is done by the command evala. The element x modulo f in
 Q[x]/(f) should then be denoted by: RootOf(f,x). This RootOf should b
e interpreted as: \"some unspecified root of the polynomial f\". So if
 alpha := RootOf(x^3-2,x) then you can not say that alpha equals 2^(1/
3), you should think of alpha as an unspecified root of x^3-2, and not
 just one of the three roots in particular." }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 2 "f;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "A:
=(x^4+2*x)/(x+1)+x^5/(x-2);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n:=normal(A);" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "n,d:=numer(A), denom(A);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "gcdex(f,d,1,x,'s','t');" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "t;" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 4 "t*n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "
A_simplified := rem(%,f,x);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "No
w we'll simplify A modulo f using Maple's evala and RootOf." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "alpha:=RootOf(f,x);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "Ar:=subs(x=alpha,A);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "Ar:=evala(Ar);" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 115 "The name of the command evala stand for \+
EVALuate Algebraic. This is Maple's command for handling algebraic num
bers." }}}}{MARK "61" 0 }{VIEWOPTS 1 1 0 1 1 1803 }