{VERSION 6 0 "IBM INTEL LINUX" "6.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 Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{PSTYLE "Normal
" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 
-1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 
-1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 0 }1 0 0 -1 -1 -1 0 0 0 
0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 
0 0 0 0 0 0 1 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Error" 
7 8 1 {CSTYLE "" -1 -1 "" 0 1 255 0 255 1 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 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 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Plot" 0 13 1 
{CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 
0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 11 "Resultants." }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 70 "Lets assume that f
 and g are polynomials in x and have no common root." }}{PARA 0 "" 0 "
" {TEXT -1 27 "Let s and t be polynomials." }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "Then:  s*f is divisible by g  o
nly when s is divible by g." }}{PARA 0 "" 0 "" {TEXT -1 59 "And:   t*g
 is divisible by f only when t is divisible by f." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 "Now assume:" }}{PARA 0 "
" 0 "" {TEXT -1 29 "degree(s,x) < degree(g,x) and" }}{PARA 0 "" 0 "" 
{TEXT -1 26 "degree(t.x) < degree(f,x)." }}{PARA 0 "" 0 "" {TEXT -1 0 
"" }}{PARA 0 "" 0 "" {TEXT -1 45 "So then: s*f is divisible by g only \+
when s=0." }}{PARA 0 "" 0 "" {TEXT -1 47 "And      : t*g is divisible \+
by f only when t=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 56 "Hence, with these degree conditions on s and t, we have
:" }}{PARA 0 "" 0 "" {TEXT -1 42 " (*) s*f + t*g = 0   if and only if \+
s=t=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
129 "It is easy to see that (*) will be false when gcd(f,g) is not con
stant. Because then just take s := g/gcd(f,g), t := -f/gcd(f,g)." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Let n=deg
ree(f,x)" }}{PARA 0 "" 0 "" {TEXT -1 18 "and m=degree(g,x)." }}{PARA 
0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 119 "Let V_n be the
 vector space of all polynomials in x of degree less than n. The dimen
sion of this vector space equals n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }
}{PARA 0 "" 0 "" {TEXT -1 68 "Now (s,t) -> s*f + t*g  is a linear map \+
L from V_m * V_n to V_(n+m)." }}{PARA 0 "" 0 "" {TEXT -1 286 "We have \+
seen that: kernel(L) = 0 if and only if f and g have no common factor.
 Now the transpose of the matrix of this map is called the Sylvester m
atrix. So, the determinant of the Sylvester matrix is 0 if and only if
 kernel(L)<>0, which happens if and only f and g have a common root." 
}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 94 "Now the
 resultant of f and g is defined as the determinant of the Sylvester m
atrix of f and g." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "restar
t; with(linalg):" }}{PARA 7 "" 1 "" {TEXT -1 80 "Warning, the protecte
d names norm and trace have been redefined and unprotected\n" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "f:=add(a[i]*x^i,i=0..3); g:=
add(b[i]*x^i,i=0..3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,*&%\"a
G6#\"\"!\"\"\"*&&F'6#F*F*%\"xGF*F**&&F'6#\"\"#F*)F.F2F*F**&&F'6#\"\"$F
*)F.F7F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,*&%\"bG6#\"\"!\"
\"\"*&&F'6#F*F*%\"xGF*F**&&F'6#\"\"#F*)F.F2F*F**&&F'6#\"\"$F*)F.F7F*F*
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "sylvester(f,g,x);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#K%'matrixG6#7(7(&%\"aG6#\"\"$&F)6#\"\"
#&F)6#\"\"\"&F)6#\"\"!F4F47(F4F(F,F/F2F47(F4F4F(F,F/F27(&%\"bGF*&F9F-&
F9F0&F9F3F4F47(F4F8F:F;F<F47(F4F4F8F:F;F<Q(pprint06\"" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "det(%);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#,`o*()&%\"aG6#\"\"$\"\"#\"\"\")&%\"bG6#F+F)F+&F'6#\"\"!
F+!\"\"*&)F0F)F+)&F.F(F)F+F3*()&F.6#F*F)F+F&F+)F0F*F+F+*&)F&F)F+)&F.F1
F)F+F+*,F)F+F%F+)F@F*F+F0F+F7F+F3*,F)F+F&F+F@F+F<F+)F7F*F+F+*,F*F+F%F+
FBF+&F'F/F+F:F+F3**)FFF*F+F&F+)F:F*F+F@F+F+**F&F+)&F'F;F*F+F:F+FBF+F+*
()FLF)F+F7F+FBF+F3**F%F+)F-F*F+FFF+F@F+F+*()FFF)F+FDF+F@F+F+*.F*F+F&F+
FPF+FFF+F0F+F7F+F+*.F)F+F&F+FBF+FFF+FLF+F7F+F+*.F)F+F%F+F@F+F0F+F:F+F-
F+F+**F%F+FLF+F-F+FBF+F3*.F&F+F@F+F0F+FLF+F7F+F-F+F3*,F*F+FLF+F-F+F<F+
FDF+F+*.F&F+FLF+F-F+FFF+F:F+F@F+F3*,FKF+F-F+FFF+F7F+F@F+F+*,F&F+FLF+FP
F+F0F+F:F+F+**FKF+FPF+F0F+F7F+F3*.F&F+F0F+F7F+FFF+F:F+F@F+F+*.F)F+F0F+
FDF+FFF+FLF+F@F+F3*.F)F+F&F+F<F+F7F+F:F+F-F+F3**FFF+F:F+F<F+FDF+F+*,FH
F+F:F+FLF+F7F+F@F+F3*,FFF+F&F+FIF+F0F+F-F+F3*.FFF+F:F+F0F+FLF+F7F+F-F+
F+*.F*F+FKF+F:F+F@F+F0F+F7F+F+*.F*F+F&F+F-F+FHF+F7F+F@F+F3**FHF+FDF+F-
F+F0F+F3*.F*F+FLF+F&F+FIF+F0F+F@F+F3**FLF+FIF+F<F+F7F+F3" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "resultant(f,g,x);" }}{PARA 12 "" 1 
"" {XPPMATH 20 "6#,`o*()&%\"aG6#\"\"$\"\"#\"\"\")&%\"bG6#F+F)F+&F'6#\"
\"!F+!\"\"*&)F0F)F+)&F.F(F)F+F3*()&F.6#F*F)F+F&F+)F0F*F+F+*&)F&F)F+)&F
.F1F)F+F+*,F)F+F%F+)F@F*F+F0F+F7F+F3*,F)F+F&F+F@F+F<F+)F7F*F+F+*,F*F+F
%F+FBF+&F'F/F+F:F+F3**)FFF*F+F&F+)F:F*F+F@F+F+**F&F+)&F'F;F*F+F:F+FBF+
F+*()FLF)F+F7F+FBF+F3**F%F+)F-F*F+FFF+F@F+F+*()FFF)F+FDF+F@F+F+*.F*F+F
&F+FPF+FFF+F0F+F7F+F+*.F)F+F&F+FBF+FFF+FLF+F7F+F+*.F)F+F%F+F@F+F0F+F:F
+F-F+F+**F%F+FLF+F-F+FBF+F3*.F&F+F@F+F0F+FLF+F7F+F-F+F3*,F*F+FLF+F-F+F
<F+FDF+F+*.F&F+FLF+F-F+FFF+F:F+F@F+F3*,FKF+F-F+FFF+F7F+F@F+F+*,F&F+FLF
+FPF+F0F+F:F+F+**FKF+FPF+F0F+F7F+F3*.F&F+F0F+F7F+FFF+F:F+F@F+F+*.F)F+F
0F+FDF+FFF+FLF+F@F+F3*.F)F+F&F+F<F+F7F+F:F+F-F+F3**FFF+F:F+F<F+FDF+F+*
,FHF+F:F+FLF+F7F+F@F+F3*,FFF+F&F+FIF+F0F+F-F+F3*.FFF+F:F+F0F+FLF+F7F+F
-F+F+*.F*F+FKF+F:F+F@F+F0F+F7F+F+*.F*F+F&F+F-F+FHF+F7F+F@F+F3**FHF+FDF
+F-F+F0F+F3*.F*F+FLF+F&F+FIF+F0F+F@F+F3**FLF+FIF+F<F+F7F+F3" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "f:=17*x^5+x^2+x+1;" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%\"fG,**&\"#<\"\"\")%\"xG\"\"&F(F(*$)F*\"\"
#F(F(F*F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "g:=x^3+2*x
^2+b[1]*x+9;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,**$)%\"xG\"\"$
\"\"\"F**&\"\"#F*)F(F,F*F**&&%\"bG6#F*F*F(F*F*\"\"*F*" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "sylvester(f,g,x);" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#K%'matrixG6#7*7*\"#<\"\"!F)\"\"\"F*F*F)F)7*F)F(F)F)F
*F*F*F)7*F)F)F(F)F)F*F*F*7*F*\"\"#&%\"bG6#F*\"\"*F)F)F)F)7*F)F*F.F/F2F
)F)F)7*F)F)F*F.F/F2F)F)7*F)F)F)F*F.F/F2F)7*F)F)F)F)F*F.F/F2Q(pprint26
\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "det(%);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#,.\"*wME)G\"\"\"*&\"(O'>;F%&%\"bG6#F%F%F%*&\"'d?
IF%)F(\"\"#F%!\"\"*&\"%lCF%)F(\"\"$F%F%*&\"%,EF%)F(\"\"%F%F%*&\"$*GF%)
F(\"\"&F%F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "R:=resultant
(f,g,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"RG,.\"*wME)G\"\"\"*&\"
(O'>;F'&%\"bG6#F'F'F'*&\"'d?IF')F*\"\"#F'!\"\"*&\"%lCF')F*\"\"$F'F'*&
\"%,EF')F*\"\"%F'F'*&\"$*GF')F*\"\"&F'F1" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "f:=(x-a/(a-1))*(x-1);" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG*&,&%\"xG\"\"\"*&%\"aGF(,&F*F(
F(!\"\"F,F,F(,&F'F(F(F,F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
17 "g:=(x-1/(1-a))*x;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG*&,&%\"
xG\"\"\"*&F(F(,&F(F(%\"aG!\"\"F,F,F(F'F(" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 12 "f:=numer(f);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"f
G*&,(*&%\"xG\"\"\"%\"aGF)F)F(!\"\"F*F+F),&F(F)F)F+F)" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 12 "g:=numer(g);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"gG*&,(*&%\"xG\"\"\"%\"aGF)F)F(!\"\"F)F)F)F(F)" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "factor(resultant(f,g,x));" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6#*(,&%\"aG\"\"\"F&!\"\"F&,&F%F&F&F&F&)
F%\"\"#F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "solve(%);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6&!\"\"\"\"\"\"\"!F%" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 36 "subs(a=0,[f,g]); # Two common roots." }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#7$,$*&%\"xG\"\"\",&F&F'F'!\"\"F'F)*&,&
F'F'F&F)F'F&F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "subs(a=-1
,[f,g]); # Common root x=1/2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$*&,&
*&\"\"#\"\"\"%\"xGF(!\"\"F(F(F(,&F)F(F(F*F(*&F%F(F)F(" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "subs(a=1,[f,g]);  # Common root x=i
nfinity" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$,&\"\"\"F%%\"xG!\"\"F&" }
}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "What happened in this example is
 the following:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 382 "f has a root 1/(a-1) and g has a root 1/(1-a) which both
 become infinity when a=1. So for a=1 the polynomials f and g have a c
ommon root x=infinity, and therefore a=1 is a root of the resultant. A
t a=1 the polynomials f and g are 1-x and x, and don't have a non-triv
ial gcd. Having a common root infinity should be interpreted as that f
or a=1 both degrees of f and g have decreased." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 30 "Lets look again at: s*f+t
*g=0." }}{PARA 0 "" 0 "" {TEXT -1 15 "n:=degree(f,x);" }}{PARA 0 "" 0 
"" {TEXT -1 15 "m:=degree(g,x);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 75 "and we're looking for polynomials s,t of \+
degree <n and degree <m such that:" }}{PARA 0 "" 0 "" {TEXT -1 16 "(*)
 s*f+t*g = 0." }}{PARA 0 "" 0 "" {TEXT -1 298 "In the above example n=
m=2. So we're looking for polynomials s,t of degree <2 such that (*) h
olds. Now when we take a=1, then the polynomials f and g both get a lo
wer degree, we get polynomials  f_\{a=1\} and g_\{a=1\} of degree lowe
r than n and m. We can easily find a solution of (*) when a=1,  take:
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 10 "s:=g_
\{a=1\}" }}{PARA 0 "" 0 "" {TEXT -1 11 "t:=-f_\{a+1\}" }}{PARA 0 "" 0 
"" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 444 "These have degree < n
 and < m, and when a=1 they become solutions of (*). Therefore, the de
terminant of the Sylvester matrix must vanish when a becomes 1. And th
erefore, a=1 must be a root of resultant(f,g,x), even though f and g d
on't have a common factor when a=1. But with our notion of \"common ro
ot\" which includes infinity when both degrees decrease, then we can s
till say that there is a common root if and only if the resultant vani
shes." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 28 "
Lets see some more examples." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 15 "f:=randpoly(x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,.\"#z
\"\"\"*&\"#bF')%\"xG\"\"&F'!\"\"*&\"#PF')F+\"\"%F'F-*&\"#NF')F+\"\"$F'
F-*&\"#(*F')F+\"\"#F'F'*&\"#]F'F+F'F'" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 15 "g:=randpoly(x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
\"gG,.\"#X\"\"\"*&\"#cF')%\"xG\"\"&F'F'*&\"#\\F')F+\"\"%F'F'*&\"#jF')F
+\"\"$F'F'*&\"#dF')F+\"\"#F'F'*&\"#fF'F+F'!\"\"" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 27 "ifactors(resultant(f,g,x));" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#7$!\"\"7%7$\"\"&\"\"\"7$\"%R5F(7$\"2Z%)o2rdx=\"F(" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v:=%[2];" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%\"vG7%7$\"\"&\"\"\"7$\"%R5F(7$\"2Z%)o2rdx=\"F(" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "v:=[seq(i[1],i=v)];" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7%\"\"&\"%R5\"2Z%)o2rdx=\"" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "for p in v do Gcd(f,g) mod p
 od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"\"\"\"$F%" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"\"\"$)**F%" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#,&%\"xG\"\"\"\"1f6:E%y;M&F%" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 78 "For any other prime number, the polynomials f and g will \+
have no common root.." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "f:=-80*x^5+x^3+x+1;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,**&\"#!)\"\"\")%\"xG\"\"&F(!\"
\"*$)F*\"\"$F(F(F*F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 
"g:=15*x^7+x^6+x+9;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,**&\"#:
\"\"\")%\"xG\"\"(F(F(*$)F*\"\"'F(F(F*F(\"\"*F(" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 17 "resultant(f,g,x);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#!4b=Gc[lk.C\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 15 "v:=ifactors(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7$!\"\"
7%7$\"\"&\"\"\"7$\".>\\WM-T\"F*7$\"'4f<F*" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 22 "v:=[seq(i[1],i=v[2])];" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"vG7%\"\"&\".>\\WM-T\"\"'4f<" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 33 "for p in v do  Gcd(f,g) mod p od;" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"
xG\"\"\"\".-2Y#QO6F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"\"
\"'hs;F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 141 "As we see, the resul
tant is 0 modulo 5, and there is a common root (infinity), but no comm
on factor. For all prime numbers that do not divide" }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "igcd( lcoeff(f,x), lcoe
ff(g,x) )" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
81 "we have that Gcd(f,g) mod p  is 1 if and only if p does not divide
 the resultant." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 102 "When p divides igcd( lcoeff(f,x), lcoeff(g,x) ) then we \+
can not be sure if Gcd(f,g) mod p is 1 or not." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 25 
"Elimination by resultant." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
19 "Xt := -2*t/(1+t^2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#XtG,$*(
\"\"#\"\"\"%\"tGF(,&F(F(*$)F)F'F(F(!\"\"F-" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 22 "Yt := (1-t^2)/(1+t^2);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#YtG*&,&\"\"\"F'*$)%\"tG\"\"#F'!\"\"F',&F'F'F(F'F," }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "plot( [Xt, Yt, t=-100..100
] );" }}{PARA 13 "" 1 "" {GLPLOT2D 433 433 433 {PLOTDATA 2 "6%-%'CURVE
SG6$7]q7$$\"3K+!)**>+!)**>!#>$!3o,+)**>+!)***!#=7$$\"3qvKI1U$44#F*$!3!
3x*3eP\"y***F-7$$\"3'e5!3vbEx@F*$!3;k'QjZHw***F-7$$\"3&Q)\\E\\XG$G#F*$
!3#4B-g'HR(***F-7$$\"3wn3%z'*p4S#F*$!33-f4cs6(***F-7$$\"3uJTyw/zIDF*$!
3UcE$o.(z'***F-7$$\"3#*3#)Rl<NkEF*$!3[zYq%)*\\k***F-7$$\"3S#[!\\0zN=GF
*$!3[IiPSw-'***F-7$$\"3W(on#p^a(*HF*$!3;3a$=N1b***F-7$$\"3m#H,#>8O+KF*
$!3W?#H<`x[***F-7$$\"3O$R7*=0vRMF*$!3#\\VHsI#3%***F-7$$\"3P*=O,<]Bo$F*
$!3))eMt[y@$***F-7$$\"3s@U;8*>***RF*$!3s^\"Q!=r*>***F-7$$\"3W1EzRD5zVF
*$!3I\"f9$HrS!***F-7$$\"3%*[AJyJL>[F*$!3\"ouVHE!Q))**F-7$$\"3Fe8^\"eLM
I&F*$!33Ip]$*o#f)**F-7$$\"3g0+]VapAgF*$!3A9lR$4Z=)**F-7$$\"3S0))QhfD/o
F*$!3nTz]%>Co(**F-7$$\"3Q16db;]8!)F*$!3cOj\"H=Sy'**F-7$$\"3y_yTHqZ3&*F
*$!3!)e&)f!z\"pa**F-7$$\"3;;1drhE&>\"F-$!3&H_0f'*4$G**F-7$$\"3SGsJ+'y;
e\"F-$!3<eK_\"QAT()*F-7$$\"3:O\\Q7'\\9!>F-$!3F,0cb-c<)*F-7$$\"31h<)3Nz
3Q#F-$!3HZq!Q-OCr*F-7$$\"3Ycj!e:N3p#F-$!3GUbYt%o6j*F-7$$\"3/HOGI^9\"4$
F-$!3&Hai.D[-^*F-7$$\"3e^&y&p9=EOF-$!3#)*)*Q\")3y$>$*F-7$$\"3UM'o];%\\
sVF-$!3C&\\Xu%GS$**)F-7$$\"3I#>A2ESu!\\F-$!3<u8wOz.8()F-7$$\"3x#3\")fP
#QvbF-$!3h%e)z%f7:I)F-7$$\"3w-\\\">zED(fF-$!3p1qP'QJ0-)F-7$$\"3!Q<Z')
\\E*>kF-$!3')[_:8z5nwF-7$$\"3N$*Qwa9SBpF-$!36Y+7vGr:sF-7$$\"3vb]q#*y^'
[(F-$!3dj/K;UjHmF-7$$\"3'ow&H\"Q-j5)F-$!3?4*za!QebeF-7$$\"3kI$>t!4uj()
F-$!3_Y!))=M5j\"[F-7$$\"3WD&RwK*e\"4*F-$!3ket:'=$\\kTF-7$$\"3g3;CXxG.%
*F-$!3bnzS<Cn-MF-7$$\"3NP))eDZLz'*F-$!3VWRzKn17DF-7$$\"3%4#\\M@B'3*)*F
-$!3i&)**GNzPt9F-7$$\"37^t!H*RO'***F-$!3W*e#*z4Akp#F*7$$\"3;/.B]))QQ**
F-$\"3Ex]R)GW$36F-7$$\"3FG3b2&*pT'*F-$\"3Sb`C&H`Gl#F-7$$\"3_vg,&H)*f,*
F-$\"3Ve+n%*3rDVF-7$$\"3x>fT.d9ozF-$\"3`0;be\"RA/'F-7$$\"3&R)\\3'3\"zG
kF-$\"3EzV%4dw'fwF-7$$\"3;oX=mrS#R%F-$\"3LzU'z2%p$)*)F-7$$\"3-/0:dMIb>
F-$\"3O))*ei^wp!)*F-7$$!3Ro\"Rf)fy.yF*$\"3t1`shR]p**F-7$$!3,WX1!\\'=IM
F-$\"3?rDHMfG$R*F-7$$!3`&)4l)f4ks&F-$\"3g1aelF1)>)F-7$$!35az)oHS:^(F-$
\"3LM)QUvp7g'F-7$$!3#z!3hKZ&\\v)F-$\"3?q<d*>jA$[F-7$$!3!>jBs/$o;&*F-$
\"3))4<qAsFrIF-7$$!3'HTX'G#er*)*F-$\"3jC&4\\4v/V\"F-7$$!3axl=,N$*****F
-$!3;gCJ1z(ok$!#?7$$!3K*3r\">\"=J\"**F-$!3nlJ9N&G`J\"F-7$$!3kb$f\\LJUq
*F-$!38jE-(=.TT#F-7$$!3Cv%Qqv%z@%*F-$!3Wi%=;#p3^LF-7$$!3]+U77=@*4*F-$!
3R;lH,?\"y9%F-7$$!3%*)\\X#\\@ve()F-$!3^qf*3vw`#[F-7$$!3K1\"[h'y%[T)F-$
!3E-cB-\"3GS&F-7$$!3rsiHppcw!)F-$!3_iRs&**Hl*eF-7$$!3zg!p5Kv$\\xF-$!3;
i)**>Ky.K'F-7$$!3#*>'eAKJ!RrF-$!35AAB+ZW-qF-7$$!3W=jqZg%Hf'F-$!3+kNZYr
%)=vF-7$$!3x(y6Omc\"4hF-$!3\\aV#Gzcp\"zF-7$$!3`\")p/17p\"o&F-$!3`(ox.7
=\"H#)F-7$$!3EBZCz9Co\\F-$!3_n4q\\B^y')F-7$$!3g3X;CUi-WF-$!3qe06Q9py*)
F-7$$!3b9f$R!)>Hm$F-$!3p8#f7l**\\I*F-7$$!3&*ox-vtjHJF-$!3/(QTpv]w\\*F-
7$$!3g@0)=<$**GFF-$!3\\oX,#*fU?'*F-7$$!3fAyx5)4yT#F-$!3_Y@W$\\3Lq*F-7$
$!3.Z#[.n/!Q>F-$!3rr#G-n4/\")*F-7$$!3KW^v%\\,gh\"F-$!3_>\">l<j&o)*F-7$
$!3h,dnj=1-7F-$!3N7H)\\Z*[F**F-7$$!3yAab&))f!3'*F*$!3W\"QcFdNP&**F-7$$
!3Er^JH1TW!)F*$!3;$fPB@\"fn**F-7$$!3rwMBL/n7oF*$!3cp!R;xmn(**F-7$$!3Hu
Svf\"p%))fF*$!3SOd%Q,`?)**F-7$$!3DiY<AaF.`F*$!3?1SYLx#f)**F-7$$!3$*)Rq
-56]![F*$!3f$4(=j#\\%))**F-7$$!3G]:8:VQdVF*$!3QK3X!4-0***F-7$$!3!GgYo-
#>1SF*$!3;3]F!*>(>***F-7$$!3+g-1Uw)[p$F*$!3URVGr:<$***F-7$$!3A`!)4_\")
)RV$F*$!3oF#QM7-T***F-7$$!3=TH$RS,w>$F*$!3KBx;lj)[***F-7$$!3o39W\\'z()
*HF*$!3SY()**[E]&***F-7$$!3he`0WJ\\>GF*$!3+I5&*QW-'***F-7$$!3\"HZZ(*)[
nhEF*$!3!o@*y:rX'***F-7$$!3leCvi\"o9`#F*$!3m,@(4K&z'***F-7$$!3c@VGl)pq
R#F*$!3OmM@:m7(***F-7$$!3$G-VB'GS)G#F*$!3?52Gj7Q(***F-7$$!3g))[(**4#*G
=#F*$!3OY[:2sh(***F-7$$!3SC:T&\\J14#F*$!3K!*38\"R9y***F-7$$!3K+!)**>+!
)**>F*F+-%'COLOURG6&%$RGBG$\"#5!\"\"$\"\"!F_jlF^jl-%+AXESLABELSG6$Q!6
\"Fcjl-%%VIEWG6$%(DEFAULTGFhjl" 1 2 0 1 10 0 2 9 1 4 2 1.000000 
45.000000 45.000000 0 0 "Curve 1" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
288 "We have two rational functions Xt and Yt in Q(t). Here Q(t) stand
s for all rational functions in t with rational numbers as coefficient
s. From the picture we can clearly see that Xt and Yt are algebraicall
y dependent. This means that there exist a polynomial P in two variabl
es such that:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 13 "P(Xt,Yt) = 0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 
"" 0 "" {TEXT -1 104 "In our example we can easily see in the picture \+
that this polynomial is (when we use variables x and y):" }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 19 "P(x,y) = x^2+y^2-1
." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 107 "How
 could we have computed that? Well, when we substitute x=Xt and y=Yt t
hen the x^2+y^2-1 should become 0." }}{PARA 0 "" 0 "" {TEXT -1 205 "An
other way to say that is when: x-Xt and y-Yt have a common root t=some
 number then x^2+y^2-1 = 0. So we're searching for some expression x^2
+y^2-1 that vanishes whenever x-Xt and y-Yt have a common root." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "Xt;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#,$*(\"\"#\"\"\"%\"tGF&,&F&F&*$)F'F%F&F&!\"\"F+" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "Yt;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#*&,&\"\"\"F%*$)%\"tG\"\"#F%!\"\"F%,&F%F%F&F%F*" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "x-Xt;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#,&%\"xG\"\"\"*(\"\"#F%%\"tGF%,&F%F%*$)F(F'F%F%!\"\"F%" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "y-Yt;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#,&%\"yG\"\"\"*&,&F%F%*$)%\"tG\"\"#F%!\"\"F%,&F%F%F(F%F,
F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "resultant(%,%%,t);" }
}{PARA 8 "" 1 "" {TEXT -1 40 "Error, (in resultant) invalid arguments
\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 122 "The sylvester matrix is de
fined for polynomials in t, not for rational functions. But that's eas
y to handle, because when:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 
"" 0 "" {TEXT -1 46 "x-Xt  and y-Yt have a common root, then so do:" }
}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "numer(x-
Xt), numer(y-Yt)   (numer=numerator)." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 12 "numer(x-Xt);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(%\"
xG\"\"\"*&F$F%)%\"tG\"\"#F%F%*&F)F%F(F%F%" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 12 "numer(y-Yt);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,*%
\"yG\"\"\"*&F$F%)%\"tG\"\"#F%F%F%!\"\"*$F'F%F%" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 18 "resultant(%,%%,t);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#,(*&\"\"%\"\"\")%\"xG\"\"#F&F&F%!\"\"*&F%F&)%\"yGF)F&F&
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "P:=sort(primpart(%));" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG,(*$)%\"xG\"\"#\"\"\"F**$)%\"y
GF)F*F*F*!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Another example
. Lets look at the curve:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "
" 0 "" {TEXT -1 119 "\{ ( t^3+t-3/t ,  (t+1)/t^3)  \} where t runs thr
ough the set of all real numbers and infinity. What is the curve we ge
t:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Xt := t^2+t-1/t;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#XtG,(*$)%\"tG\"\"#\"\"\"F*F(F**&F*F
*F(!\"\"F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Yt := (t+1)/t
^3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#YtG*&,&%\"tG\"\"\"F(F(F(F'!
\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "P:=resultant( numer(
x-Xt), numer(y-Yt), t);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG,6*(
\"\"#\"\"\"%\"yGF()%\"xGF'F(F(F(F(F+!\"\"*(F'F(F+F(F)F(F(*&\"\"%F(F)F(
F,*(\"\"$F(F+F()F)F'F(F,*&F2F(F*F(F(*&F2F()F+F1F(F,*&\"\"&F(F2F(F(*$)F
)F1F(F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 \+
0" 11 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }