{VERSION 3 0 "IBM INTEL LINUX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "" 1 24 0 0 0 0 0 0 0 0 0 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 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } 1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 33 "The extended Euclidean Al gorithm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 128 "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." }} {PARA 0 "" 0 "" {TEXT -1 120 "In other words: a and b are Z-linear com binations of d (i.e. multiples of d) and d is a Z-linear combination o f 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 Eucl idean Algorithm." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "a:=72;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG\"#s" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "b:=50;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG \"#]" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "d:=igcdex(a,b,'s',' t');" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "s*a + t*b;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "s;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#!\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "t;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#8" }}}{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;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%\"sG%\"tG6$\"#T!#f" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "s*a + t*b;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 233 "Of course, by adding o r 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 uniquely determined. Or we coul d 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 similar." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "a:=x^3-1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG,&* $)%\"xG\"\"$\"\"\"\"\"\"!\"\"F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "b:=x^4-1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG,&*$)%\"xG\" \"%\"\"\"\"\"\"!\"\"F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "d :=gcdex(a,b,x,'s','t');" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG,&!\" \"\"\"\"%\"xGF'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "s*a+t*b; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*&%\"xG\"\"\",&*$)F%\"\"$\"\"\"F &!\"\"F&F&F,*$)F%\"\"%F+F&F,F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&!\"\"\"\"\"%\" xGF%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "If R is the ring Q[x], t he ideal (a,b)=R*a+R*b equals the ideal (d)=R*d, so d is an R-linear c ombination 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 eq uation will still hold if we replace [s,t] by [s,t] + some multiple of [b, -a]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(s*a+t*b );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&!\"\"\"\"\"%\"xGF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "ra:=randpoly(x,degree=2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#raG,(*$)%\"xG\"\"#\"\"\"!#&)F(!#b!#P\"\" \"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "s, t := expand(s+ra*b ), expand(t-ra*a);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%\"sG%\"tG6$, .%\"xG\"#a*$)F)\"\"'\"\"\"!#&)*$)F)\"\"#F.\"#&)*$)F)\"\"&F.!#b*$)F)\" \"%F.!#P\"#P\"\"\",.!#OF=F4F3F0F/F8\"#bF)F7*$)F)\"\"$F.F<" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(s*a+t*b);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#,&!\"\"\"\"\"%\"xGF%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 425 "So if ra is some arbitrary polynomial, we can add ra*b t o s (and substract ra*a from t) and the equation s*a+t*b=d remains val id. If s is an element 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). Nam ely, q is the quotient of the division of s by b. So we can make the s olution [s,t] of the equation s*a+t*b=d unique by requiring that degre e(s,x) " 0 "" {MPLTEXT 1 0 1045 "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)%&GCDEXGR6%%\"aG%\"bG%\" xG6(%\"cG%\"rG%\"qG%\"dG%\"sG%\"tG6\"F1@%/9%\"\"!C%>8$-%(contentG6$9$9 &@$/*&F<\"\"\"F8!\"\"!\"\">F8,$F8FC6%F@*&FAFAF8FBF5C%>8%-%$remG6&F6%8'8)8(-9!6%F4FJF=6%FRFT-%'expandG6#,&FS\"\"\"*&FTFgnFOFgnFCF1F1 F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "a;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#,&*$)%\"xG\"\"$\"\"\"\"\"\"!\"\"F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "b;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*$ )%\"xG\"\"%\"\"\"\"\"\"!\"\"F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "d,s,t:=GCDEX(a,b,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6%%\" dG%\"sG%\"tG6%,&!\"\"\"\"\"%\"xGF+,$F,F*F+" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 16 "expand(s*a+t*b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #,&!\"\"\"\"\"%\"xGF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "a: =x^50-1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG,&*$)%\"xG\"#]\"\"\" \"\"\"!\"\"F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "b:=x^32-1; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG,&*$)%\"xG\"#K\"\"\"\"\"\"! \"\"F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "d,s,t:=GCDEX(a,b, x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6%%\"dG%\"sG%\"tG6%,&!\"\"\"\" \"*$)%\"xG\"\"#\"\"\"F+,0*$)F.\"#5F0F**$)F.\"\"'F0F*F,F**$)F.\"#9F0F** $)F.\"#GF0F**$)F.\"#CF0F**$)F.\"#?F0F*,8F+F+F8F+F2F+F5F+F;F+F>F+FAF+*$ )F.\"#KF0F+*$)F.\"#YF0F+*$)F.\"#UF0F+*$)F.\"#QF0F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(s*a+t*b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&!\"\"\"\"\"*$)%\"xG\"\"#\"\"\"F%" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 2 "d;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&!\"\" \"\"\"*$)%\"xG\"\"#\"\"\"F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 210 "You can verify (for a pro of you need to use the principle of mathematical induction because the algorithm uses recursion) 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 t his ring can be represented uniquely by a polynomial in x of degree sm aller than degree(f,x). We can 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 replace your result by rem(result,f,x) and i t 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). Basically all we need for that are the Maple fun ctions expand and rem." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 478 "Now we want to divide as well. Suppose that g in Q[ x]/(f), so we can represent g uniquely by a polynomial of degree < deg ree(f,x). We want to do divisions, so we want to compute 1/g if it exi sts. In other words, we want to find (if it exists) an element t of Q[ x]/(f) such that t*g = 1. In the ring Q[x]/(f) a polynomial equals 1 w hen 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] suc h 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 other 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 i n the ideal (f,g), in other words 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 that 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 Algorithm." }}}{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 n ow 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 go ing to compute 1/x." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 121 "Note that 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 element 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 tha t every non-zero polynomial g of degree < degree(f,x) will have no fac tors in common with f, because f simply doesn't have any non-trivial f actors of degree < degree(f,x). In other words: every non-zero g in Q[ x]/(f) will have 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 irreducible then we can also divide by any non-zero element. Such a ring is called a field." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 158 "Note that if f is reducible, suppose f = f1*f2 wi th degrees f1,f2 smaller than degree of f, then you could not divide b y 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 an 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 \+ is an irreducible polynomial we can multiply in the field Q[x]/(f) by \+ expand and rem. We can divide by the Extended Euclidean Algorithm (cal led gcdex in Maple, for the help page type ?gcdex ). It would be easie r to be able to just write * and / for products and quotients, and to \+ have 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 i n Q[x]/(f) should then be denoted by: RootOf(f,x). This RootOf should \+ be interpreted as: \"some unspecified root of the polynomial f\". So i f 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 no t 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 "33 2 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 }