{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 }{CSTYLE "" -1 256 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 257 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 262 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 1 18 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 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 256 27 "Formulas f or the resultant." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "f:=mul (x-alpha.i,i=1..3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "g:=m ul(x-beta.j,j=1..5);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 161 "Now f an d g have a non-trivial gcd if and only if there exists an i and a j su ch that alpha.i=beta.j, which happens if and only if the following pro duct equals 0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "P:=mul(mul (alpha.i-beta.j,i=1..3),j=1..5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "R:=resultant(f,g,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "normal( resultant(f,g,x) / P);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 30 "normal( resultant(g,f,x) / P);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 257 8 "Theorem:" }}{PARA 0 "" 0 " " {TEXT -1 43 "Let f = the product of x-alpha.i for i=1..n" }}{PARA 0 "" 0 "" {TEXT -1 41 "Let g= the product of x-beta.j for j=1..m" }} {PARA 0 "" 0 "" {TEXT -1 74 "Then resultant(f,g,x) = the product of al l alpha.i-beta.j, i=1..n, j=1..m." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 258 6 "Proof:" }}{PARA 0 "" 0 "" {TEXT -1 50 "Let P be this product, and let R be the resultant." }} {PARA 0 "" 0 "" {TEXT -1 168 "From the definition of P and R we see th at P and R are in A[alpha.1], i.e. P and R are polynomials in alpha.1 \+ with coefficients in A=Z[alpha2,..alpha.n,beta1,..beta.m]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 "Now P and R have \+ the same roots (viewed as a polynomial in alpha.1), namely:" }}{PARA 0 "" 0 "" {TEXT -1 14 "beta.1..beta.m" }}{PARA 0 "" 0 "" {TEXT -1 115 "And we can easily see that P is a square-free polynomial in alpha.1 b ecause all of these roots have multiplicity 1." }}{PARA 0 "" 0 "" {TEXT -1 100 "Therefore R/P is still a polynomial in alpha.1, but its \+ coefficients are fractions of elements of A." }}{PARA 0 "" 0 "" {TEXT -1 413 "But the matrix sylvester(f,g,x) has only m rows that contain t he variable alpha.1, and this variable appears there with degree at mo st 1, so the degree of R=det(sylvester(f,g,x)) as a polynomial in alph a.1 is at most m. Therefore R/P is a polynomial in alpha.1 of degree a t most 0. So R/P does not contain any variable alpha.1 anymore. By the same arguments, R/P does not contain any of the alpha.i or beta.j. So :" }}{PARA 0 "" 0 "" {TEXT -1 88 "R/P is in the fraction field of A, b ut contains none of the variables alpha.i or beta.j." }}{PARA 0 "" 0 " " {TEXT -1 71 "So: R/P is a rational number, it is independent of all \+ these variables." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 429 "What remains to be done is to prove that this rational n umber is 1. Since R/P does not depend on the alpha.i and beta.j, we ma y choose them any way we want (as long as we avoid that P=0 because th en we're dividing by 0). We can take alpha.i=0 and beta.j=-1 for all i ,j. Then P will be 1, and R will be the determinant of the sylvester m atrix. Looking at that matrix one easily sees that R=1, so R/P=1, whi ch completes the proof." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 259 12 "Corollary 1:" }}{PARA 0 "" 0 "" {TEXT -1 41 "Let f = a_n * (x-alpha.1)*...*(x-alpha.n)" }}{PARA 0 "" 0 "" {TEXT -1 38 "Let g= b_m * (x-beta.1)*...*(x-beta.m)" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 5 "Then:" }}{PARA 0 " " 0 "" {TEXT -1 82 "resultant(f,g,x) = (a_n)^m * (b_m)^n * mul(mul( al pha.i-beta.j , i=1..n), j=1..m)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 138 "Proof: the sylvester matrix is almost th e same as before, except that now m rows have been multiplied by a_n, \+ and the other n rows by b_m." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 260 12 "Corollary 2:" }}{PARA 0 "" 0 " " {TEXT -1 167 "Let f and g be polynomials of degree n and m, let beta .1..beta.m be the roots of g and let b_m be the leading coefficient of g. So g is like in the previous corollary." }}{PARA 0 "" 0 "" {TEXT -1 5 "Then:" }}{PARA 0 "" 0 "" {TEXT -1 72 "resultant(f,g,x) = (a_n)^m * g(alpha.1) * g(alpha.2) * ... * g(alpha.n)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 71 "Proof: this is the previo us corollary, but just formulated differently." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 262 7 "Remark:" } }{PARA 0 "" 0 "" {TEXT -1 61 "Notice that: resultant(f,g,x) = (-1)^(n* m) * resultant(g,f,x)" }}{PARA 0 "" 0 "" {TEXT -1 289 "because if you \+ interchange the alpha's and the beta's in corollary 1 then you're mult iplying all these alpha.i-beta.j by -1, so you get n*m factors -1. So \+ if you interchange f and g then the resultant changes a factor -1 if b oth n and m are odd, and otherwise the resultant stays the same." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 261 12 "Definitions:" }}{PARA 0 "" 0 " " {TEXT -1 331 "Let f in K[x] be a monic irreducible polynomial, where K is a field. Let f=(x-alpha.1)*..*(x-alpha.n) where alpha.1..alpha.n are the roots of f. To find these roots we need to keep on adding new RootOf's to K, and keep on factoring f, until it factors into linear \+ factors. This way we find a large algebraic extension of K, namely:" } }{PARA 0 "" 0 "" {TEXT -1 39 "K(alpha.1, alpha.2, ..., alpha.n) of K. " }}{PARA 0 "" 0 "" {TEXT -1 117 "This is called the splitting field o f f over K. It is the smallest field extension of K that contains all \+ roots of f." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 " If we extend K by just one root of f we get a field:" }}{PARA 0 "" 0 "" {TEXT -1 95 "L=K[x]/(f) which is isomorphic to K(alpha.1), w hich is also isomorphic to K(alpha.2), etcetera." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 260 "Now, if g in L=K[x]/(f), then write g as a polynomial in x. Now K[x]/(f) is isomorphic to K(al pha.1), and the image of g under this isomorphism is gamma.1 = subs(x= alpha.1,g) in K(alpha.1). We have elements: gamma.i = subs(x=alpha.i, \+ g) in K(alpha.i), i=1..n." }}{PARA 0 "" 0 "" {TEXT -1 332 "All of the se elements gamma.i are in different algebraic extensions K(alpha.i) o f K. But they are all in the splitting field K(alpha.1, alpha.2, ..., \+ alpha.n) of f over K. The gamma.1, gamma.2, .., gamma.n are called con jugates of each other. We can go from gamma.i to gamma.j by replacing \+ the root alpha.i of f by the root alpha.j." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 66 "Now we define the trace of g ov er the field extension L over K as:" }}{PARA 0 "" 0 "" {TEXT -1 26 "th e sum of all the gamma.i" }}{PARA 0 "" 0 "" {TEXT -1 65 "and we define the norm of g over the field extension L over K as:" }}{PARA 0 "" 0 " " {TEXT -1 30 "the product of all the gamma.i" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "We see now, that if f is \+ monic, then the norm equals:" }}{PARA 0 "" 0 "" {TEXT -1 16 "resultant (f,g,x)" }}{PARA 0 "" 0 "" {TEXT -1 54 "and this is in fact an element of the smaller field K." }}{PARA 0 "" 0 "" {TEXT -1 59 "Likewise, the trace is also an element of the base field K." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 397 "Let g again be in L=K[x] /(f). Another way to define the trace and the norm of g over the field extension L over K is the following. L is a K-vector space of dimensi on n. Multiplication by g is a K-linear map from L to L. By choosing a basis of L (e.g. x^0,x^1,...,x^(n-1)) we get a matrix for this map. N ow the norm of g is the determinant of this map, and the trace of g is the trace of this map." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 9 "Examples:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "resultant(f,x,x); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "resultant(f,1+x,x);" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "resultant(f,2,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "resultant(f,y-x,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "resultant(f,y^2-x,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "resultant(f,y-2*x,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "resultant(f,y^2+x+x^2,x);" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "resultant(f,x^2+5,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "resultant(f, x-beta,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "resultant(f, (x-beta1)*(x-be ta2) ,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "f:=x^3-2;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "solve(f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "alpha1, alpha2, alpha3 :=%;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "resultant(f,x^2-3,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "mul(alpha.i^2-3,i=1..3);" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "resultant(f,y-x,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "resultant(f,y^2-x,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "resultant(f,y-(x+x^2),x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "seq(expand(subs(y=alpha.i+(a lpha.i)^2,%)), i=1..3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 123 "So if alpha is a root of f, then we get a polynomial in y that has alpha+al pha^2 as a root by taking the norm of y-(x+x^2)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 66 "Maple also has the norm f unction. The syntax is evala(Norm( .. ))." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f:=x^3+x+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "alpha:=R ootOf(f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "alpha+alpha^ 2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "y-%;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "evala(Norm(%));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "subs(y=alpha+alpha^2,%);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 9 "evala(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "evala(Normal( f/(x-alpha) ));" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 17 "evala(Factor(%));" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 16 "beta:=RootOf(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "alpha-beta;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "x-%;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "evala(Norm(%)) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "g:=%;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "evala(Factor(g,\{alpha,beta\}));" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 157 "All algebraic extensions of Fp of degree n are is omorphic to each other. This means that when f and g are irreducible p olynomials of Fp[x] of degree n, then:" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 37 "Fp[x]/(f) is isomorphic to Fp[x]/(g). " }}{PARA 0 "" 0 "" {TEXT -1 46 "In particular: Fp[x]/(f) contains a r oot of g." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 12 "Furthermore:" }}{PARA 0 "" 0 "" {TEXT -1 69 "Fp[x]/(f) contains al l roots of f, so it is the splitting field of f." }}{PARA 0 "" 0 "" {TEXT -1 57 "One root is given by the equivalence class of x modulo f. " }}{PARA 0 "" 0 "" {TEXT -1 51 "The next root is x^p. The next one is x^(p^2), etc." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 74 "If f is monic and irreducible in Fp[x], and if alpha is a root of f, then:" }}{PARA 0 "" 0 "" {TEXT -1 66 "f = (x-alpha^(p^0)) \+ * (x-alpha^(p^1)) * ... * (x-alpha^(p^(n-1)))." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 "Lets check:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p:=17;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f:=x^3+x+3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(f) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "g :=x^3+x+5;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(g) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "alpha:=RootOf(f,x); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Factor(f,alpha) mod p; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Factor(g,alpha) mod p; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "mul( x-alpha^(p^i), i=0 ..2 );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Expand(%) mod p; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "beta:=RootOf(g);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "Factor(f,beta) mod p;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "Factor(g,beta) mod p;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "mul(x-beta^(p^i),i=0..2);" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Expand(%) mod p;" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "Now think of f and g in characteri stic 0, so f and g in Q[x]." }}{PARA 0 "" 0 "" {TEXT -1 115 "Take a ro ot alpha of f and a root beta of g. Compute a polynomial in x such tha t alpha+beta will be a root of that." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "alpha;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "be ta;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "alpha+beta;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "x-%;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "evala(Norm(%));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "h:=%;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "subs(x=alpha+be ta,h);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "evala(%);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "We see that h is irreducible in Q[ x]." }}{PARA 0 "" 0 "" {TEXT -1 478 "But when we compute modulo p, the n we see that we can take a root alpha of f in an extension of degree \+ 3 or degree 1 (when f is reducible in Fp[x]). And we can take a root b eta of f in an extension of Fp of degree 1 or 3. If both f and g are i rreducible in Fp[x], then these two extensions of degree 3 are the sam e, so alpha+beta is still in an extension of degree 3. Therefore, the \+ polynomial h will have a root in an extension of Fp of degree 3, no ma tter what the prime p is." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 168 "If h were irreducible in Fp[x] then you can only \+ find a root in an extension of degree at least 9. The conclusion is th at h will be reducible modulo any prime number p." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 57 "p:=2; while p<100 do Factor(h) mod p; p:=nex tprime(p) od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 263 17 " The discriminant." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 91 "We've seen that f is square-free if and only if f and dif f(f,x) have no common factors. So:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 299 "resultant(f, diff(f,x), x) must be non-z ero for f to be square-free. If a_n is the leading coefficient of f th en the Sylvester matrix contains one column that contains only two non -zero entries, both of which are a_n. So this resultant is always divi sible by a_n. Now the discriminant is defined as:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "(-1)^(n*(n-1)/2) * result ant(f, diff(f,x), x) / a_n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 207 "And we see that the discriminant vanishes if a nd only if the polynomial has a double root (which could be infinity, \+ that means that then the degree drops by at least 2, so one has a doub le root at infinity)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "di scrim(h,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ifactor(%); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 44 "The discriminant has the foll owing property:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "If f = a_n * (x-alpha.1)*(x-alpha.2)*...*(x-alpha.n) then " }}{PARA 0 "" 0 "" {TEXT -1 84 "discrim(f,x) = (a_n)^(2*(n-1)) * mul( mul( (alpha.i - alpha.j)^2, i=1..j-1), j=2..n)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 357 "So it is an even power o f the leading coefficient times the product of (alpha.i-alpha.j)^2 for all i " 0 "" {MPLTEXT 1 0 83 "for N from 0 to 5 do f:=a_n * mul(x -alpha.i,i=1..N); disc:=factor(discrim(f,x)) od;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f:=x^4+x-1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "readlib(splits):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "spl its(f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "sols:=[seq(x-i [1],i=%[2])];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "evala(Expa nd( mul(x-i,i=sols) ));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 " mul(mul( (sols[i]-sols[j])^2 ,i=1..j-1),j=2..4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "evala(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "discrim(f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ifactor(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Sqrf ree(f) mod 283;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 177 "Let F be a sq uare-free polynomial in x and y. If we substitute values for x, then f or most values the result will still be square-free. Except for the ro ots of the discriminant." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "f:=y^4+x*y+x^3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "sqrfree (f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "subs(x=123,f);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "sqrfree(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "factors(discrim(f,y));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "sols:=[seq(RootOf(i[1],x),i=%[2])]; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "subs(x=sols[1],f);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "sqrfree(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "subs(x=sols[2],f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "sqrfree(%);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 75 "Assume that f is in Z[x] and we want to factor f. So what Maple will do is:" }}{PARA 0 "" 0 "" {TEXT -1 16 "Factor(f) mod \+ p;" }}{PARA 0 "" 0 "" {TEXT -1 17 "Then: Hensellift." }}{PARA 0 "" 0 " " {TEXT -1 70 "Then: form all products and check which ones are factor s of f in Z[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "Which primes to avoid?" }}{PARA 0 "" 0 "" {TEXT -1 382 "I n the Hensel lifting algorithm, we can lift f = f1 * f2 if f1 and f2 h ave no common factors. When f is square-free, then this will be the ca se, i.e. when the discriminant is non-zero. So we should avoid primes \+ that divide the discriminant. In particular, we see this way that if f is square-free, then there are at most finitely many primes such that f is not square-free modulo p." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f:=x^5+x+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "ifac tor(discrim(f,x));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Facto r(f) mod 3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(f) mo d 7;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Factor(f) mod 23;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "If we take any other prime then f will be square-free." }}}}{MARK "103 6 0" 382 }{VIEWOPTS 1 1 0 1 1 1803 }