{VERSION 6 0 "SUN SPARC SOLARIS" "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 }
{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 "Maple Output" 0 11 1 
{CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }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 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "In the previous worksheet
 we looked at a prime number p, and then defined the p-adic integers a
s follows:" }}{PARA 0 "" 0 "" {TEXT -1 20 "A = (A_1, A_2, ...) " }}
{PARA 0 "" 0 "" {TEXT -1 41 "where each A_i is in the range 0..p^i -1,
" }}{PARA 0 "" 0 "" {TEXT -1 38 "and where (if j>i) A_i is A_j mod p^i
." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 204 "We \+
can write A_j = sum a.i * p^i where the sum is taken for i from 0 to j
-1 and where a.i are in the range 0..p-1. Then we can think of the p-a
dic integer A as an infinite sum: A = sum a.i p^i, i=0,1,2..." }}
{PARA 0 "" 0 "" {TEXT -1 58 "because this infinite sum converges in th
e p-adic numbers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 137 "So in this construction \+
we started with the ring of integers Z, and then we considered Z modul
o p^1, then modulo p^2, then p^3, etcetera." }}{PARA 0 "" 0 "" {TEXT 
-1 272 "Lets do the same construction for the ring Q[x] of polynomials
 in x with rational numbers as coefficients. Instead of a prime number
 p we will now take an irreducible polynomial p, in fact, we will just
 take p=x   (it would also work with other irreducible polynomials p).
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 214 "So c
onsider Q[x]. Elements modulo x^n can be represented as sum a.i x^i wh
ere i=0..n-1. If we now do the same construction as we did for the p-a
dic numbers, then we will obtain a ring that we will denote by Q[[x]].
" }}{PARA 0 "" 0 "" {TEXT -1 99 "An element A of Q[[x]] can be represe
nted by an infinite power series A = sum a.i x^i, i=0,1,2,...." }}
{PARA 0 "" 0 "" {TEXT -1 255 "Of course, like with p-adic numbers, in \+
practise we can only compute with approximations of elements of Q[[x]]
. An approximation with accuracy n of the element A will simply be: A \+
modulo x^n, which can be represented by the polynomial sum a.i x, i=0.
.n-1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 297 
"We call the elements of Q[[x]] formal power series with rational coef
ficients. The word \"formal\" refers to the fact that there are no con
ditions on convergence (so formal power series are in a way easier tha
n convergent power series). For example, the formal power series:  sum
 i!*x^i, i=0,1,2,..." }}{PARA 0 "" 0 "" {TEXT -1 191 "does not converg
e but it is still an element of Q[[x]]. Convergent power series are of
 course also elements of Q[[x]], the set of all convergent power serie
s at x=0 forms a subring of Q[[x]]." }}{PARA 0 "" 0 "" {TEXT -1 265 "N
ote that if we had taken another irreducible polynomial p, say p=x-15,
 then we would have obtained the ring Q[[x-15]], the ring of all forma
l power series at the point x=15. The ring Q[[x-15]] is not the same a
s the ring Q[[x]], but these two rings are isomorphic." }}{PARA 0 "" 
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 177 "Q[[x]] is a much la
rger ring than Q[x], for example sin(x) can be viewed as an element of
 Q[[x]]. We can compute approximations of sin(x) of accuracy n by the \+
following command:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n:=15;
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"#:" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 21 "taylor(sin(x),x=0,n);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#+3%\"xG\"\"\"F%#!\"\"\"\"'\"\"$#F%\"$?\"\"\"&#F'\"%S]\"
\"(#F%\"'!)GO\"\"*#F'\")+o\"*R\"#6#F%\"++3-Fi\"#8-%\"OG6#F%\"#:" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 152 "Maple uses the notation O(x^15) t
o tell us that it calculated up to accuracy 15, that is, modulo x^15. \+
So the coefficient of x^15 has not been computed." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 278 "Now consider again the r
ing Z. In the previous worksheet we took a monic polynomial f in Z[x] \+
and factored it (up to some finite accuracy) in the ring Z_p[x]. When \+
the accuracy of these monic factors is high enough, then we could use \+
them to find all monic factors of f in Z[x]." }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 212 "Now we will do the same, but i
nstead of Z we take Q[x]. So we take polynomials that have their coeff
icients in Q[x]. Lets use the variable y for these polynomials. So the
n we will look at polynomials f in Q[x,y]." }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 150 "We will assume that f is monic
 as a polynomial in y, i.e. lcoeff(f,y)=1. This makes the algorithms e
asier. The non-monic case will be discussed later." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 325 "Then we can compute all \+
monic factors of f in Q[[x]][y],  so we compute all monic irreducible \+
polynomials in y with coefficients in Q[[x]] that are factors of f. If
 we compute them sufficiently accurate then we can use them to reconst
ruct the monic (in y) factors of f in Q[x,y], in the same way as in th
e previous worksheet." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 
"" {TEXT -1 446 "What accuracy is needed?  If g in Q[x,y] and if we kn
ow that for example degree(g,x) < 10, then it is easy to see that once
 we know g up to accuracy 10 (that is, we know g modulo x^10) then we \+
know g up to infinite precision (we know g exactly). So all we need to
 figure out the required accuracy is a degree bound. Now if g is some \+
factor of f, then clearly degree(g,x) <= degree(f,x) and so it is easy
 to find a bound for the required accuracy." }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "Now lets consider an example:" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "f := y^4-4*x*y^3-5*y^2+6*
x^2*y^2+2*x*y^2+10*x*y-4*x^3*y-4*x^2*y+4+x^4+2*x^3-4*x^2-5*x;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,<*$)%\"yG\"\"%\"\"\"F**(F)F*%\"
xGF*)F(\"\"$F*!\"\"*&\"\"&F*)F(\"\"#F*F/*(\"\"'F*)F,F3F*F2F*F**(F3F*F,
F*F2F*F**(\"#5F*F,F*F(F*F**(F)F*)F,F.F*F(F*F/*(F)F*F6F*F(F*F/F)F**$)F,
F)F*F**&F3F*F;F*F**&F)F*F6F*F/*&F1F*F,F*F/" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 73 "f modulo x^1 is the same as rem(f,x,x), which is the same
 as subs(x=0,f)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "subs(x=
0,f);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$)%\"yG\"\"%\"\"\"F(F'F(*&
\"\"&F()F&\"\"#F(!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L
:=factors(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"LG7$\"\"\"7&7$,&%
\"yGF&\"\"#!\"\"F&7$,&F*F&F&F&F&7$,&F*F&F+F&F&7$,&F*F&F&F,F&" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "L:=[seq(i[1],i=L[2])];" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"LG7&,&%\"yG\"\"\"\"\"#!\"\",&F'F(F
(F(,&F'F(F)F(,&F'F(F(F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Now f \+
is in Q[x][y]." }}{PARA 0 "" 0 "" {TEXT -1 54 "And f is also an elemen
t in the larger ring Q[[x]][y]." }}{PARA 0 "" 0 "" {TEXT -1 94 "We wil
l first factor f as an element of Q[[x]][y], and then as an element of
 Q[x][y] = Q[x,y]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 224 "If we factor f in Q[[x]][y], then how accurate should th
e factors be in order to recover the factorization in Q[x,y]? Well, de
gree(f,x) = 4, so every factor has degree < 5, so accuracy 5 should de
finitely be accurate enough." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 
0 "" 0 "" {TEXT -1 143 "The list L above gives all monic irreducible f
actors of f in Q[[x]][y], but it only gives those factors up to accura
cy 1 (that is, modulo x^1)." }}{PARA 0 "" 0 "" {TEXT -1 39 "We will He
nsel lift L up to accuracy 5." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 1609 "Lift_L:=proc(f,L,x,y,n)\n   # Inpute f in Q[x,y] monic in y.\n
   # L a list of factors of f mod x^1\n   # (so the elements in L have
 accuracy 1).\n   # The elements in L must have gcd 1.\n   #\n   # n a
 positive integer.\n   #\n   # Note: to make it easy I only implemente
d the case\n   # where f is monic, and where the elements of L\n   # a
re also monic (as polynomials in y).\n   #\n   local i,j,k,c,Li,pol,cp
ol;\n\n   Li:=L; # accuracy right now is i=1.\n\n   for i from 1 to n-
1 do\n      \n      Li := [seq(\n              Li[k] + x^i * add(c[j,k
]*y^j,\n                      j=0..degree(L[k],y)-1)\n             ,k=
1..nops(L))];\n\n      # Now Li mod x^i did not change because we adde
d\n      # something that is 0 mod x^i.\n      #\n      # Li mod x^(i+
1) did change. We did not know any of\n      # the coefficients of x^i
*y^j in any of the\n      # factors. So we used an unknown c[j,k] for \+
the\n      # the coefficient of x^i*y^j in the k'th factor. \n      #
\n      # Now lets compute equations for the c[j,k].\n      # We know \+
that the product convert(Li,`*`) is the\n      # same as f up to accur
acy i, so the following is\n      # a polynomial:\n      pol:=normal((
convert(Li,`*`)-f)/x^i);\n      # We want to choose values for the unk
nowns c[j,k]\n      # in such a way that Li is OK with accuracy i+1,\n
      # which means that pol is 0 mod x^1.\n      pol:=expand(subs(x=0
,pol));\n      # This pol should be the zero polynomial,\n      # whic
h means that the following coeffs\n      # should be zero:\n      cpol
:=\{coeffs(pol,y)\};\n      # Solve and increase the accuracy of Li to
 i+1:\n      Li:=subs(solve(cpol),Li)\n   od;\n   Li\nend;" }}{PARA 
12 "" 1 "" {XPPMATH 20 "6#>%'Lift_LGj+6'%\"fG%\"LG%\"xG%\"yG%\"nG6)%\"
iG%\"jG%\"kG%\"cG%#LiG%$polG%%cpolG6\"F4C%>8(9%?(8$\"\"\"F;,&9(F;F;!\"
\"%%trueGC'>F77#-%$seqG6$,&&F76#8&F;*&)9&F:F;-%$addG6$*&&8'6$8%FIF;)9'
FTF;/FT;\"\"!,&-%'degreeG6$&F8FHFVF;F;F>F;F;/FI;F;-%%nopsG6#F8>8)-%'no
rmalG6#*&,&-%(convertG6$F7%\"*GF;9$F>F;FKF>>F_o-%'expandG6#-%%subsG6$/
FLFYF_o>8*<#-%'coeffsG6$F_oFV>F7-F_p6$-%&solveG6#FcpF7F7F4F4F46'FYFYFY
FY\"#\\" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "n:=degree(f,x)+1
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"\"&" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 21 "L:=Lift_L(f,L,x,y,n);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%\"LG7&,.%\"yG\"\"\"\"\"#!\"\"*&#\"\"$\"\"%F(%\"xGF(F*
*&#F(\"#kF(*$)F/F)F(F(F(*&#F(\"$7&F(*$)F/F-F(F(F(*&#\"\"&\"&%Q;F(*$)F/
F.F(F(F(,.F'F(F(F(*&#F-F)F(F/F(F**&#F(\"\")F(F3F(F**&#F(\"#;F(F8F(F**&
#F<\"$G\"F(F>F(F*,.F'F(F)F(*&#F<F.F(F/F(F**&#F(F2F(F3F(F**&#F(F7F(F8F(
F**&#F<F=F(F>F(F*,.F'F(F(F**&#F(F)F(F/F(F**&#F(FEF(F3F(F(*&#F(FHF(F8F(
F(*&#F<FKF(F>F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "Lets check i
f we did the Hensel lifting correctly:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 28 "expand( f - convert(L,`*`));" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#,J*&#\"%vr\"&oF$\"\"\"*$)%\"xG\"\"&F(F(!\"\"*&#\"$0\"\"
')GC&F(*$)F+\"\"'F(F(F(*&#\"'Zd?\"(/V>%F(*$)F+\"\"(F(F(F(*&#\"(:iM$\"*
caVo#F(*$)F+\"\")F(F(F(*&#\"(l1s\"F?F(*$)F+\"\"*F(F(F(*&#\"'*[1%F?F(*$
)F+\"#5F(F(F(*&#\"$X#\")k)3r'F(*$)F+\"#6F(F(F-*&#\"$$p\"*74(o`F(*$)F+
\"#7F(F(F-*&#\"&vT\"\",o$Q(fV$F(*$)F+\"#8F(F(F-*&#\"%vP\"-sM&*Qu8F(*$)
F+\"#9F(F(F-*&#\"$D'\"-Wp!z([FF(*$)F+\"#:F(F(F-*&#\"%*z\"\"&%Q;F(*&F3F
(%\"yGF(F(F-*&#F&\"'W@EF(*&F:F(FapF(F(F-*&#\"&&[?\"(_r4#F(*&FAF(FapF(F
(F-*&#\"'D'4%\"*Gx@M\"F(*&FGF(FapF(F(F-*&#F^pF'F(*&F*F()Fap\"\"#F(F(F(
*&#F&F1F(*&F3F(FcqF(F(F(*&#Fgo\"./6^Y!)R%F(*$)F+\"#;F(F(F-*&#FhpF8F(*&
F:F(FcqF(F(F(*&#F]qF?F(*&FAF(FcqF(F(F(" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 182 "Hmm, that doesn't look like 0. Of course we can't expect
 0 because we computed L only up to accuracy n. So we can only expect \+
this f  minus product(factors) to be 0 up to accuracy n:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "rem(%, x^n, x);" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 220 "Now we
 have determined all 4 monic irreducible factors of f in Q[[x]][y]. Le
ts now determine all the possible products of these factors, so that w
e get all (not just the irreducible ones) monic factors of f in Q[[x]]
[y]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 214 "subsets:=proc(L)\n
  # Input: list or set.\n  # Output: list of all subsets.\n  local e,R
,i;\n  if nops(L)=0 then\n     [ \{\} ]\n  else\n     e:=L[1]:\n     R
:=procname(L[2..-1]);\n     [op(R), seq(i union \{e\},i=R)]\n  fi\nend
;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(subsetsGj+6#%\"LG6%%\"eG%\"RG%
\"iG6\"F,@%/-%%nopsG6#9$\"\"!7#<\"C%>8$&F26#\"\"\">8%-9!6#&F26#;\"\"#!
\"\"7$-%#opG6#F=-%$seqG6$-%&unionG6$8&<#F8/FPF=F,F,F,6#F3" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "subsets(L);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#72<\"<#,.%\"yG\"\"\"F(!\"\"*&#F(\"\"#F(%\"xGF(F)*&#F(\"
\")F(*$)F-F,F(F(F(*&#F(\"#;F(*$)F-\"\"$F(F(F(*&#\"\"&\"$G\"F(*$)F-\"\"
%F(F(F(<#,.F'F(F,F(*&#F;F?F(F-F(F)*&#F(\"#kF(F1F(F)*&#F(\"$7&F(F6F(F)*
&#F;\"&%Q;F(F=F(F)<$FAF&<#,.F'F(F(F(*&#F8F,F(F-F(F)*&#F(F0F(F1F(F)*&#F
(F5F(F6F(F)*&#F;F<F(F=F(F)<$FOF&<$FOFA<%FOFAF&<#,.F'F(F,F)*&#F8F?F(F-F
(F)*&#F(FFF(F1F(F(*&#F(FIF(F6F(F(*&#F;FLF(F=F(F(<$FfnF&<$FfnFA<%FfnFAF
&<$FOFfn<%FOFfnF&<%FOFfnFA<&FOFfnFAF&" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 31 "map(expand,map(convert,%,`*`)):" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 17 "map(rem,%,x^n,x);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#72\"\"\",.%\"yGF$F$!\"\"*&#F$\"\"#F$%\"xGF$F'*&#F$\"\")
F$*$)F+F*F$F$F$*&#F$\"#;F$*$)F+\"\"$F$F$F$*&#\"\"&\"$G\"F$*$)F+\"\"%F$
F$F$,.F&F$F*F$*&#F9F=F$F+F$F'*&#F$\"#kF$F/F$F'*&#F$\"$7&F$F4F$F'*&#F9
\"&%Q;F$F;F$F',0*&,&#\"#6FIF'*(\"$N'F$FIF'F&F$F$F$F<F$F$*&,&#FNFFF'*(
\"#JF$FFF'F&F$F$F$F5F$F$*&,&*(\"\"(F$FCF'F&F$F$#\"#dFCF$F$F0F$F$*&,&#F
$F=F$*(FYF$F=F'F&F$F'F$F+F$F$F*F'F&F$*$)F&F*F$F$,.F&F$F$F$*&#F6F*F$F+F
$F'*&#F$F.F$F/F$F'*&#F$F3F$F4F$F'*&#F9F:F$F;F$F',*F/F$*&,&F$F$*&F*F$F&
F$F'F$F+F$F$F$F'FjnF$,0*&,&#\"#vFIF$*(\"$X'F$FIF'F&F$F'F$F<F$F$*&,&#\"
#FFFF$*(\"#LF$FFF'F&F$F'F$F5F$F$*&,&*(\"\"*F$FCF'F&F$F'#\"$.\"FCF$F$F0
F$F$*&,&#\"#<F=F'*(FNF$F=F'F&F$F'F$F+F$F$FjnF$*&F6F$F&F$F$F*F$,2*&,(#
\"$$GFIF'*&#F$\"$c#F$F&F$F$*&#F9FIF$FjnF$F'F$F<F$F$*&,(*&#F$\"#KF$F&F$
F$#\"$Z'FFF'*&#F$FFF$FjnF$F'F$F5F$F$*&,(#\"#\\FCF$*&#F$FCF$FjnF$F'*&#F
YF*F$F&F$F$F$F0F$F$*&,(#\"#8F=F$*&F6F$F&F$F'*&#F`sF=F$FjnF$F'F$F+F$F$F
*F'F&F'*$)F&F6F$F$*&F*F$F[oF$F$,.F&F$F*F'*&#F6F=F$F+F$F'*&#F$FCF$F/F$F
$*&#F$FFF$F4F$F$*&#F9FIF$F;F$F$,0*&,&#\"%P?FIF'*(F_pF$FIF'F&F$F$F$F<F$
F$*&,&#\"$<\"FFF'*(FepF$FFF'F&F$F$F$F5F$F$*&,&*(FipF$FCF'F&F$F$#FYFCF$
F$F0F$F$*&,&#FYF=F$*(F9F$F=F'F&F$F'F$F+F$F$F*F$*&F6F$F&F$F'FjnF$,*F/F$
FfoF$F=F'FjnF$,2*&,(F_rF$*&#F$F.F$F&F$F'*&F8F$FjnF$F$F$F<F$F$*&,(*&#F$
F=F$F&F$F'#F9F.F'*&F2F$FjnF$F$F$F5F$F$*&,(*&F-F$FjnF$F$F*F'*&F*F$F&F$F
$F$F0F$F$*&,(F$F$*&#F9F*F$FjnF$F'*&F6F$F&F$F$F$F+F$F$FdsF$*&F=F$F&F$F'
FjnF'F=F$,0*&,&#\"%t>FIF$*(FPF$FIF'F&F$F'F$F<F$F$*&,&#\"$,\"FFF$*(FUF$
FFF'F&F$F'F$F5F$F$*&,&*(FYF$FCF'F&F$F'#\"#*)FCF$F$F0F$F$*&,&#FipF=F$*(
FipF$F=F'F&F$F'F$F+F$F$F*F'F&F'FjnF$,2*&,(#FfqFIF$*&#F$FiqF$F&F$F'*&F_
tF$FjnF$F$F$F<F$F$*&,(*&#F$F`rF$F&F$F'#\"$x$FFF'*&F]tF$FjnF$F$F$F5F$F$
*&,(*&F[tF$FjnF$F$#\"$x\"FCF'*&#F9F*F$F&F$F$F$F0F$F$*&,(#F9F=F'*&#FNF=
F$FjnF$F'*&F9F$F&F$F$F$F+F$F$FdsF$F&F'*&F*F$F[oF$F'F*F$,2*&,(#F$F`rF'*
&F-F$F&F$F$*&#F9F:F$FjnF$F'F$F<F$F$*&,(*&FhnF$F&F$F$#FNF.F'*&#F$F3F$Fj
nF$F'F$F5F$F$*&,&*&#F$F.F$FjnF$F'*&F=F$F&F$F$F$F0F$F$*&,(FYF$*&#FYF*F$
FjnF$F'F&F'F$F+F$F$FdsF$FjnF$*&F=F$F&F$F'F=F',0F;F$*&,&*&F=F$F&F$F'F*F
$F$F5F$F$*&,(*&\"\"'F$F[oF$F$*&F=F$F&F$F'F=F'F$F0F$F$*&,**&F=F$FesF$F'
*&\"#5F$F&F$F$*&F*F$F[oF$F$F9F'F$F+F$F$*$)F&F=F$F$F=F$*&F9F$F[oF$F'" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "map(gcd,%,f);" }}{PARA 12 
"" 1 "" {XPPMATH 20 "6#72\"\"\"F$F$F$F$,,F$!\"\"%\"xGF$*$)F'\"\"#F$F$*
$)%\"yGF*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$F$F$,<*$)F-F0F$F$*(F0F$F'F$)F-\"\"$F$F&*&\"\"&F$F,F$F&*(\"\"'F
$F)F$F,F$F$*(F*F$F'F$F,F$F$*(\"#5F$F'F$F-F$F$*(F0F$)F'F7F$F-F$F&*(F0F$
F)F$F-F$F&F0F$*$)F'F0F$F$*&F*F$F@F$F$*&F0F$F)F$F&*&F9F$F'F$F&" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "\{ op(%) \} minus \{1,f\};" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$,,\"\"\"!\"\"%\"xGF%*$)F'\"\"#F%F%
*$)%\"yGF*F%F%*(F*F%F'F%F-F%F&,,\"\"%F&F'F%F(F%F+F%*(F*F%F'F%F-F%F&" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "convert(%,`*`);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#*&,,\"\"\"!\"\"%\"xGF%*$)F'\"\"#F%F%*$)%\"yG
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%" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "Now we have factored f in Q[x,y] i
nto irreducible factors, using:" }}{PARA 0 "" 0 "" {TEXT -1 42 "1) Map
le's factorization for the ring Q[y]" }}{PARA 0 "" 0 "" {TEXT -1 18 "2
) Hensel lifting." }}{PARA 0 "" 0 "" {TEXT -1 44 "3) Constructing all \+
combinations of factors." }}{PARA 0 "" 0 "" {TEXT -1 51 "4) reducing t
he factors modulo p^n  (p=x, n was 5)." }}{PARA 0 "" 0 "" {TEXT -1 54 
"5) Taking gcd's to find out which factors are correct." }}{PARA 0 "" 
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "Let's verify the cor
rectness of our computation:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 10 "factor(f);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&,,\"\"\"!\"\"%\"
xGF%*$)F'\"\"#F%F%*$)%\"yGF*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%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
}{MARK "0 1 0" 20 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 
2 33 1 1 }