{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 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 278 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 291 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 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 "" 0 256 1 {CSTYLE "" -1 -1 "" 1 24 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 }} {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT -1 28 "The ring of 10-adic numb ers." }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 42 " Let a be a positive integer. We know that:" }}{PARA 0 "" 0 "" {TEXT -1 10 "a mod 10^n" }}{PARA 0 "" 0 "" {TEXT -1 39 "is the same as: the \+ last n digits of a." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 78 "Now, let a be any integer and we will look at the follo wing infinite sequence:" }}{PARA 0 "" 0 "" {TEXT -1 58 "S = ( a mod 10 ^1, a mod 10^2, a mod 10^3, a mod 10^4,....)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 114 "Let Z/10^n denote the set of i ntegers modulo 10^n. Then the n'th entry of S can be viewed as an elem ent of Z/10^n." }}{PARA 0 "" 0 "" {TEXT -1 71 "We can view S as an ele ment of the following infinite product of rings:" }}{PARA 0 "" 0 "" {TEXT -1 41 " Z/10^1 * Z/10^2 * Z/10^3 * Z/10^4 * ...." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 133 "Note, however, that when i,j are positive integers and ii) of S modulo 10^i. So we do not consider every element of Z/10 * \+ Z/10^2 * ... but only those that satisfy this relation." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "Now define the set \+ " }{TEXT 256 6 "Z_10 " }{TEXT -1 172 "as the set of all elements S of Z/10^1 * Z/10^2 * Z/10^3 * Z/10^4 * .... that have that property, i .e. that if i " 0 "" {MPLTEXT 1 0 15 "-123 mod 10^50;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"Sx)****************************************** *****" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "Negative integers will a t some point have just 9's on the left. Note that " }{TEXT 267 5 "Z_10 " }{TEXT -1 49 "also contains some rational numbers, but not all:" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "1/2 mod 10^50;" }}{PARA 8 " " 1 "" {TEXT -1 42 "Error, the modular inverse does not exist\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "r:=1/3 mod 10^50;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"Snmmmmmmmmmmmmmmmmmmmmmmmm" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "r*3 mod 10^50;" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "S o we have an element in " }{TEXT 268 5 "Z_10 " }{TEXT -1 157 "consisti ng of .....6666667, i.e. one 7 and then infinitely many 6's on the le ft of that. Multiplying that element by 3 gives 1, so that element wil l be 1/3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 8 "The set " }{TEXT 269 6 "Z_10 i" }{TEXT -1 270 "s a ring, not a fiel d, because we can not divide by all non-zero elements. We can represen t elements by \"integers with infinitely many digits\", or we can also write it as a number with base beta as follows:\nsum_\{n >= 0\} a.n * beta^n where a.n is in the range 0..beta-1" }}{PARA 0 "" 0 "" {TEXT -1 38 "and where beta=10 in the case of Z_10." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "In the same way we can \+ also define " }{TEXT 270 3 "Z_p" }{TEXT -1 27 " as the set of formal s ums:" }}{PARA 0 "" 0 "" {TEXT -1 65 " sum_\{n >= 0\} a.n * p^n wher e the a.i are in the range 0..p-1." }}{PARA 0 "" 0 "" {TEXT -1 5 "This " }{TEXT 271 3 "Z_p" }{TEXT -1 123 " is called the ring of p-adic int egers. This ring has no zero divisors if and only if p is a prime numb er or a prime power." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 49 "When p is a prime number then the fraction field " } {TEXT 272 3 "Q_p" }{TEXT -1 4 " of " }{TEXT 273 3 "Z_p" }{TEXT -1 31 " is the set of all formal sums:" }}{PARA 0 "" 0 "" {TEXT -1 64 "sum_\{ n >= -N\} a.n * p^n where the a.i are in the range 0..p-1." }}{PARA 0 "" 0 "" {TEXT -1 9 "This set " }{TEXT 274 4 "Q_p " }{TEXT -1 38 "is \+ called the field of p-adic numbers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "with(padic);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7E%)a rccoshpG%(arccospG%)arccothpG%(arccotpG%)arccschpG%(arccscpG%)arcsechp G%(arcsecpG%)arcsinhpG%(arcsinpG%)arctanhpG%(arctanpG%&coshpG%%cospG%& cothpG%%cotpG%&cschpG%%cscpG%&evalpG%*expansionG%%exppG%(lcoeffpG%%log pG%'orderpG%%ordpG%*ratvaluepG%&rootpG%&sechpG%%secpG%&sinhpG%%sinpG%& sqrtpG%&tanhpG%%tanpG%'valuepG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "r:=evalp(1/3,7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,8\" \"&\"\"\"*&\"\"%F'-%!G6#\"\"(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*F-F'F'*&F)F')F *\"\")F'F'*&F)F')F*\"\"*F'F'-%\"OG6#*$)F*\"#5F'F'" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 13 "evalp(3*r,7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&\"\"\"F$-%\"OG6#*$)-%!G6#\"\"(\"#5F$F$" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 18 "evalp( 1/20! , 7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0*&\"\"$\"\"\"-%!G6#\"\"(!\"#F&*&\"\"'F&F'!\"\"F&F'F&* &F-F&)F'\"\"#F&F&*&\"\"%F&)F'F3F&F&*&F1F&)F'F*F&F&-%\"OG6#*$)F'\"\")F& F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "evalp( 1/20! , 7,20); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,:*&\"\"$\"\"\"-%!G6#\"\"(!\"#F&*& \"\"'F&F'!\"\"F&F'F&*&F-F&)F'\"\"#F&F&*&\"\"%F&)F'F3F&F&*&F1F&)F'F*F&F &*&F%F&)F'\"#5F&F&*&F3F&)F'\"#9F&F&*&\"\"&F&)F'\"#:F&F&*&F3F&)F'\"#;F& F&*&F>F&)F'\"# " 0 "" {MPLTEXT 1 0 17 "evalp(20!*% , 7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# ,&\"\"\"F$-%\"OG6#*$)-%!G6#\"\"(\"\"*F$F$" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 19 "evalp( sqrt(2), 7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,8\"\"$\"\"\"-%!G6#\"\"(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%*&F2F%)F&\"\") F%F%*&F.F%)F&\"\"*F%F%-%\"OG6#*$)F&\"#5F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "evalp(%^2, 7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# ,&\"\"#\"\"\"-%\"OG6#*$)-%!G6#\"\"(\"\"*F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "evalp( sqrt(3), 7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%FAILG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "Q_7 do es not contain any element whose square equals 3. Note that Fp also co ntains no element whose square equals 3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Now lets look at " }{TEXT 275 5 "Z _10 " }{TEXT -1 85 "again, and consider the element r:=1/7, so r is t he root of the polynomial 7*x-1 in " }{TEXT 276 5 "Z_10." }{TEXT -1 51 " To determine r in Z_10 is the same as determining:" }}{PARA 0 "" 0 "" {TEXT -1 41 "r mod 10^1, r mod 10^2, r mod 10^3, ....." }}{PARA 0 "" 0 "" {TEXT -1 21 "Lets do that for now:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #\"\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^2;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"#V" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$V \"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^4;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"%Vr" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^5;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"&V r&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^6;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"'Vr&)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^7;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"(V r&G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^8;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\")Vr&G%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^9;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"*V r&G9" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "1/7 mod 10^10;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"+Vr&G9(" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 14 "1/7 mod 10^11;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \",Vr&G9d" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "If r is the exact el ement in " }{TEXT 277 5 "Z_10 " }{TEXT -1 351 "that is a root of the p olynomial 7*x-1, then what we have computed above are approximations o f r. First with 1 digit accurate, then with 2 digits accurate, then wi th 3, up to 11 digits. We have computed r modulo 10^1, then modulo 10^ 2, then modulo 10^3, etc. Every time we got one more digit of the 10-a dic number r (which has infinitely many digits)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 386 "But it seems that what w e are doing here is not efficient. When we computed 1/7 mod 10^11 (for which Maple will use igcdex) we only got 1 new digit, all the other o nes were already known at that point. So the question arises: instead \+ of computing all 11 digits, could we not just compute the one new digi t, making use of the 10 digits that we already knew from the previous \+ computation?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 94 "So, what we want is, given r modulo 10^n, compute r modulo 10^( n+1). This process is called " }{TEXT 278 15 "HENSEL LIFTING." }} {PARA 0 "" 0 "" {TEXT -1 135 "Then we only need to compute r modulo 10 ^1, and we can increase the accuracy (compute r modulo a higher power \+ of 10) by Hensel lifting." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 125 "What we are doing is solving the equation 7*x-1 i n Z_10. Solving is the same as factoring the polynomial 7*x-1 into: 7* (x-r)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 118 "Assume that we have factored 7*x-1 into the form 7*(x-r) up to ac curacy n. That means: we have an integer r such that:" }}{PARA 0 "" 0 "" {TEXT -1 43 "7*x-1 is equivalent to 7*(x-r) modulo 10^n." }}{PARA 0 "" 0 "" {TEXT -1 206 "Now we want to Hensel lift this factorization, which means: we want to increase its accuracy n. Lets say we want to \+ lift this equation up to accuracy n+1. That means we have to find an i nteger r' such that:" }}{PARA 0 "" 0 "" {TEXT -1 48 "7*x-1 is equivale nt to 7*(x-r') modulo 10^(n+1)." }}{PARA 0 "" 0 "" {TEXT -1 171 "The l ast n digits of r' and r will be the same, we only have to determine 1 new digit. We may assume that r is reduced modulo 10^n (i.e. 0 <= r < 10^n). Now we can write:" }}{PARA 0 "" 0 "" {TEXT -1 15 "r' = r + d* 10^n" }}{PARA 0 "" 0 "" {TEXT -1 92 "and what we need to do is compute the number d, which we can take in the range 0..9. We get:" }}{PARA 0 "" 0 "" {TEXT -1 47 "7*x-1 should be 7*(x-r-d*10^n) modulo 10^(n+1). " }}{PARA 0 "" 0 "" {TEXT -1 181 "So: 7*x-1 - 7*(x-r-d*10^n) should be divisible by 10^(n+1), and we already know that it is divisible by 10 ^n. So we can divide it by 10^n, and then the equation becomes of the \+ form:" }}{PARA 0 "" 0 "" {TEXT -1 29 "a + b*d should be 0 modulo 10" } }{PARA 0 "" 0 "" {TEXT -1 82 "where a and b are integers that we find \+ by computing (7*x-1 -7*(x-r-d*10^n))/10^n." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 6 "n:=11;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"#6 " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "r:=1/7 mod 10^11;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\",Vr&G9d" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 12 "r:=r+d*10^n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,&\",Vr&G9d\"\"\"*&\"-+ ++++5F'%\"dGF'F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "(r*7-1) /10^n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&\"\"%\"\"\"*&\"\"(F%%\"dGF %F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "solve(%,d) mod 10;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "r:=subs(d=%,r);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"rG\"-Vr&G9d)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "Now we've incre ased the accuracy from 11 to 12. Lets Hensel lift it further to accura cy 20." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 94 "for n from 12 to \+ 19 do\n r:=r+d*10^n;\n r:=subs(d = solve( (r*7-1)/10^n , d) mod 10 , r)\nod;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,&\"-Vr&G9d)\"\"\" *&\".++++++\"F'%\"dGF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\".V r&G9dG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,&\".Vr&G9dG\"\"\"*&\" /++++++5F'%\"dGF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"/Vr&G9d G%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,&\"/Vr&G9dG%\"\"\"*&\"0++ +++++\"F'%\"dGF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"0Vr&G9dG 9" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,&\"0Vr&G9dG9\"\"\"*&\"1+++ ++++5F'%\"dGF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"1Vr&G9dG9( " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,&\"1Vr&G9dG9(\"\"\"*&\"2+++ +++++\"F'%\"dGF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"2Vr&G9dG 9d" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,&\"2Vr&G9dG9d\"\"\"*&\"3+ +++++++5F'%\"dGF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"3Vr&G9d G9d)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,&\"3Vr&G9dG9d)\"\"\"*& \"4+++++++++\"F'%\"dGF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"4 Vr&G9dG9dG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG,&\"4Vr&G9dG9dG\" \"\"*&\"5+++++++++5F'%\"dGF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" rG\"5Vr&G9dG9dG%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "n;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"#?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"5V r&G9dG9dG%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 63 "Now lets Hensel lif t some other factorizations, this time over " }{TEXT 279 4 "Z_7," } {TEXT -1 21 " the 7-adic integers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=7;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "h:=x^2-2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"hG,&*$)%\"xG\"\"#\"\"\"F*F)!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(h) mod p;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#*&,&%\"xG\"\"\"\"\"$F&F&,&F%F&\"\"%F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f:=op(1,%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,&%\"xG\"\"\"\"\"$F'" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 12 "g:=op(2,%%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"gG,&%\"xG\"\"\"\"\"%F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Expand(h-f*g) mod p^1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Expand(h-f*g) mod p^2;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#,&\"#N\"\"\"*&\"#UF%%\"xGF%F%" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "We will view f,g,h now as polynomi als in " }{TEXT 280 3 "Z_7" }{TEXT -1 126 "[x]. As we see, the product f*g is h up to accuracy 1, but not up to accuracy 2. We will try to H ensel lift the factorization:" }}{PARA 0 "" 0 "" {TEXT -1 8 " h = f*g " }}{PARA 0 "" 0 "" {TEXT -1 68 "That is, suppose that the factorizati on has accuracy n, which means:" }}{PARA 0 "" 0 "" {TEXT -1 33 "h is e quivalent to f*g modulo p^n" }}{PARA 0 "" 0 "" {TEXT -1 58 "Then we wa nt to compute new f and g such that we will get:" }}{PARA 0 "" 0 "" {TEXT -1 38 "h is equivalent to f*g modulo p^(n+1)." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 39 "And this process conver ges in the ring " }{TEXT 281 3 "Z_7" }{TEXT -1 87 "[x]. So, after infi nitely many steps we would get an exact factorization of h=x^2-2 in " }{TEXT 282 3 "Z_7" }{TEXT -1 4 "[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 241 "How do we Hensel lift the polynomials \+ f and g (which have accuracy n) up to accuracy n+1? Since f and g are \+ already correct modulo p^n, we only need to add something that is a mu ltiple of p^n, we don't need any lower powers of p. So we take:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "New f := \+ f + f0 * p^n;" }}{PARA 0 "" 0 "" {TEXT -1 19 "New g:=g + g0 *p^n;" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 105 "Then we \+ compute h-f*g, divide it by p^n, then equate it to 0 modulo p, and the n solve f0 and g0 modulo p." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 291 "for n from 1 to 5 do\n f:=f+f0*p^n;\n g:=g+g0*p^n;\n should _be_zero_modp := expand( (h-f*g)/p^n ) mod p;\n should_be_zero_modp \+ := \{coeffs(should_be_zero_modp,x)\};\n # Solve this, reduce mod p, \+ and substitute into f and g:\n f,g := op(subs(solve(should_be_zero_m odp) mod p, [f,g]))\nod;\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,( %\"xG\"\"\"\"\"$F'*&\"\"(F'%#f0GF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%\"gG,(%\"xG\"\"\"\"\"%F'*&\"\"(F'%#g0GF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%4should_be_zero_modpG,.\"\"&\"\"\"*&\"\"'F'%\"xGF'F'* (F)F'F*F'%#g0GF'F'*&\"\"%F'F,F'F'*(F)F'%#f0GF'F*F'F'*&\"\"$F'F0F'F'" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%4should_be_zero_modpG<$,(\"\"&\"\" \"*&\"\"$F(%#f0GF(F(*&\"\"%F(%#g0GF(F(,(*&\"\"'F(F.F(F(*&F1F(F+F(F(F1F (" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%\"fG%\"gG6$,&%\"xG\"\"\"\"#5F *,&F)F*\"#RF*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,(%\"xG\"\"\"\" #5F'*&\"#\\F'%#f0GF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,(%\"x G\"\"\"\"#RF'*&\"#\\F'%#g0GF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%4 should_be_zero_modpG,.\"\"'\"\"\"*&F&F'%\"xGF'F'*(F&F'F)F'%#g0GF'F'*& \"\"%F'F+F'F'*(F&F'%#f0GF'F)F'F'*&\"\"$F'F/F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%4should_be_zero_modpG<$,(\"\"'\"\"\"*&\"\"$F(%#f0GF(F (*&\"\"%F(%#g0GF(F(,(*&F'F(F.F(F(*&F'F(F+F(F(F'F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%\"fG%\"gG6$,&%\"xG\"\"\"\"$3\"F*,&F)F*\"$N#F*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,(%\"xG\"\"\"\"$3\"F'*&\"$V$F'%# f0GF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,(%\"xG\"\"\"\"$N#F'* &\"$V$F'%#g0GF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%4should_be_zero _modpG,.\"\"$\"\"\"*&\"\"'F'%\"xGF'F'*(F)F'F*F'%#g0GF'F'*&\"\"%F'F,F'F '*(F)F'%#f0GF'F*F'F'*&F&F'F0F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% 4should_be_zero_modpG<$,(\"\"$\"\"\"*&F'F(%#f0GF(F(*&\"\"%F(%#g0GF(F(, (*&\"\"'F(F-F(F(*&F0F(F*F(F(F0F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6 $%\"fG%\"gG6$,&%\"xG\"\"\"\"%m@F*,&F)F*\"$N#F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,(%\"xG\"\"\"\"%m@F'*&\"%,CF'%#f0GF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,(%\"xG\"\"\"\"$N#F'*&\"%,CF'%#g0GF'F' " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%4should_be_zero_modpG,.\"\"&\"\" \"*&\"\"'F'%\"xGF'F'*(F)F'F*F'%#g0GF'F'*&\"\"%F'F,F'F'*(F)F'%#f0GF'F*F 'F'*&\"\"$F'F0F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%4should_be_zer o_modpG<$,(\"\"&\"\"\"*&\"\"$F(%#f0GF(F(*&\"\"%F(%#g0GF(F(,(*&\"\"'F(F .F(F(*&F1F(F+F(F(F1F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%\"fG%\"gG 6$,&%\"xG\"\"\"\"%nXF*,&F)F*\"&SA\"F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,(%\"xG\"\"\"\"%nXF'*&\"&2o\"F'%#f0GF'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,(%\"xG\"\"\"\"&SA\"F'*&\"&2o\"F'%#g0GF'F'" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%4should_be_zero_modpG,.\"\"'\"\"\"*& F&F'%\"xGF'F'*(F&F'F)F'%#g0GF'F'*&\"\"%F'F+F'F'*(F&F'%#f0GF'F)F'F'*&\" \"$F'F/F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%4should_be_zero_modpG <$,(\"\"'\"\"\"*&\"\"$F(%#f0GF(F(*&\"\"%F(%#g0GF(F(,(*&F'F(F.F(F(*&F'F (F+F(F(F'F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%\"fG%\"gG6$,&%\"xG \"\"\"\"&\"=QF*,&F)F*\"&o%zF*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(h - f*g);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&\"+5x;MI!\"\"*&\"'\\w6\"\"\"%\"xGF(F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "% mod p^n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%\"xG\"\"\"\"&\"=QF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "g;" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#,&%\"xG\"\"\"\"&o%zF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "r :=x-f;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG!&\"=Q" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "r^2 mod p^n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "In genera l the Hensel lifting procedure works as follows:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Suppose f,g,h in " } {TEXT 283 1 "Z" }{TEXT -1 21 "[x] and suppose that:" }}{PARA 0 "" 0 " " {TEXT -1 195 " h is equivalent to f*g modulo p^n where n>=1\nand s uppose furthermore that f,g,h are monic (i.e. the highest coefficient \+ of f (which is lcoeff(f,x) in Maple) should be 1, and same for g and h )." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "Now suppose furthermore that:" }}{PARA 0 "" 0 "" {TEXT -1 15 " Gcd(f,g) m od p" }}{PARA 0 "" 0 "" {TEXT -1 117 "equals 1, so f and g have no com mon factors in Fp[x] (recall that Fp is the field with p elements, it \+ is Z modulo p)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "Then, one can find polynomials f0 and g0, such that:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "degree(f0 ,x) < degree(f,x)" }}{PARA 0 "" 0 "" {TEXT -1 26 "degree(g0,x) < degre e(g,x)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "(f+f0 * p^n) * (g+g0 * p^n) is equivalent to h modulo p^(n+1)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "By repeat ing this infinitely many times, one will find polynomials F, G in " } {TEXT 284 3 "Z_p" }{TEXT -1 91 "[x] such that h is exactly (not just m odulo some power of p) equal to F*G, and furthermore:" }}{PARA 0 "" 0 "" {TEXT -1 34 "F is equivalent to f modulo p, and" }}{PARA 0 "" 0 "" {TEXT -1 30 "G is equivalent to g modulo p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "How to find f0 and g0? Well, mo dulo p^(n+1) we get" }}{PARA 0 "" 0 "" {TEXT -1 111 "(f+f0*p^n)*(g+g0* p^n) - h is f*g-h + p^n*(f0*g + g0*f) + p^(2n)*f0*g0, which is equ ivalent to (assume n>=1)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 41 "f*g-h + p^n*(f0*g + g0*f) modulo p^(n+1)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "Now compu te h-f*g modulo p^(n+1), this must be of the form R*p^n for some R in \+ " }{TEXT 285 1 "Z" }{TEXT -1 38 "[x] because h is f*g up to accuracy n ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "Then the equation becomes:" }}{PARA 0 "" 0 "" {TEXT -1 56 "p^n*R = p^n*(f0 *g + g0*f) modulo p^(n+1) in other words:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "R = f0*g + g0*f modulo p." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 145 "This has a unique solution f0 and g0 modulo p (with the conditions on the degr ee above) that can be computed by the Extended Euclidean Algorithm." } }{PARA 0 "" 0 "" {TEXT -1 3 "Do:" }}{PARA 0 "" 0 "" {TEXT -1 28 " Gcde x(f,g,x,'s','t') mod p;" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "then s*f + t*g is 1 mod p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "So: R*t*g + R*s*f is R mod p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 213 "Now if we take f0=R*t and g0=R*s then f0, g0 do not necessarily satisfy the \+ degree conditions (degree(f0) < degree(f) and degree(g0) < degree(g)). So we have to reduce R*t to get degree < degree(f,x). So we take:" } }{PARA 0 "" 0 "" {TEXT -1 66 "f0:=Rem(R*t,f,x,'q') mod p; and we'll \+ have degree(f0) " 0 "" {MPLTEXT 1 0 909 "Hensel_lift := proc( f,g,h,x,N,p)\n # Input: a positive integer n, and\n # monic polyno mials f,g,h in Z[x] such that:\n # h is f*g mod p.\n\n # Output: m onic polynomials F, G such that:\n # h is F * G mod p^N.\n local s ,t,f0,g0,R,q,F,G,n;\n \n # Compute s and t:\n if Gcdex(f,g,x,'s' ,'t') mod p<>1 then\n error \"f and g should have Gcd 1 modulo p \"\n fi;\n F, G := f, g; # Now the accuracy is 1.\n for n from 1 to N-1 do\n # Compute f0, g0 such that (F+f0*p^n)*(G+g0*p^n) i s\n # h modulo p^(n+1).\n # Take f0, g0 = R*t, R*s as ex plained above.\n R:=( Expand(h-F*G) mod p^(n+1))/p^n;\n \+ f0, g0 := R*t, R*s;\n # Now reduce f0, g0 to meet the degree co nditions,\n # while at the same time keeping f0*g+g0*f the\n \+ # same, namely R.\n f0:=Rem(f0,f,x,'q') mod p;\n g0 :=Expand(g0+q*g) mod p;\n F, G := F+f0*p^n, G+g0*p^n\n od;\n \+ F, G\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 916 "HenselLift:= proc(L::list,h,x::name,N::posint,p::posint)\n # Recursive algorithm \+ for Hensel lifting when there are\n # more than 2 factors. Note: Thi s is not the most efficient\n # way to do it but it's fine for us.\n #\n # Input: a list L=[f1,f2,...fk] of polynomials such that\n \+ # f1*f2*...*fk is h modulo p, and all f.i have Gcd 1.\n #\n # Outp ut: a list [F1,F2,..Fk] such that\n # F1*F2*..*Fk is h modulo p^n.\n local l,L1,L2,h1,h2;\n l:=nops(L);\n if l=0 then\n error \+ \"wrong input\"\n elif l=1 then\n [h]\n elif l=2 then\n \+ [Hensel_lift(op(L),h,x,N,p)]\n else\n L1, L2 := L[1..iquo(l, 2)], L[iquo(l,2)+1..-1];\n # Take the products.\n h1, h2 : = convert(L1,`*`), convert(L2,`*`);\n # Lift the products:\n \+ h1, h2 := Hensel_lift(h1,h2,h,x,N,p);\n # Lift L1 and L2 and \+ return the answer\n [op(procname(L1,h1,x,N,p)), op(procname(L2,h 2,x,N,p))]\n fi\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 " h:=x^8+2*x^6+37*x^4-36*x^2+324;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"hG,,*$)%\"xG\"\")\"\"\"F**&\"\"#F*)F(\"\"'F*F**&\"#PF*)F(\"\"%F*F**& \"#OF*)F(F,F*!\"\"\"$C$F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=5;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "L:=Factors(h) mod p;" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"LG7$\"\"\"7&7$,(*$)%\"xG\"\"#F&F&F,F&F-F&F&7 $,(F*F&*&F-F&F,F&F&\"\"%F&F&7$,(F*F&*&\"\"$F&F,F&F&F1F&F&7$,(F*F&*&F1F &F,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&,(*$)%\"xG\"\" #\"\"\"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+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "conv ert(L,`*`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#**,(*$)%\"xG\"\"#\"\"\" 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(F)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "exp and(% - h);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,2*&\"#5\"\"\")%\"xG\" \"(F&F&*&\"#XF&)F(\"\"'F&F&*&\"$S\"F&)F(\"\"&F&F&*&\"$X#F&)F(\"\"%F&F& *&\"$+%F&)F(\"\"$F&F&*&\"$?%F&)F(\"\"#F&F&*&\"$S#F&F(F&F&\"$g#!\"\"" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "% mod p;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "n :=10; L:=HenselLift(L,h,x,n,p);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"nG\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"LG7&,(*$)%\"xG\"\"#\" \"\"F+*&\"(O@D(F+F)F+F+\"(Acw*F+,(F'F+*&\"(Z'QZF+F)F+F+\"(>cw*F+,(F'F+ *&\"(yp-&F+F)F+F+F2F+,(F'F+*&\"(*[8DF+F)F+F+F.F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "convert(L,`*`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#**,(*$)%\"xG\"\"#\"\"\"F)*&\"(O@D(F)F'F)F)\"(Acw*F)F),(F%F)*&\"( Z'QZF)F'F)F)\"(>cw*F)F),(F%F)*&\"(yp-&F)F'F)F)F0F)F),(F%F)*&\"(*[8DF)F 'F)F)F,F)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "expand(% - h );" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,2*&\")]7`>\"\"\")%\"xG\"\"(F&F& *&\"0vV)*3nTP\"F&)F(\"\"'F&F&*&\"6Dc^`[zkwj5%F&)F(\"\"&F&F&*&\"]i!*y3prTc 'om]58F&)F(\"\"#F&F&*&\">]7y+$G\"3-w*))o)*==F&F(F&F&\"=+++voG(4MRDI\\4 *F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "% mod p^n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "The Maple function mod always produces non-negative numbers, if a \+ and m are integers and m>0 then:" }}{PARA 0 "" 0 "" {TEXT -1 9 " a mod m;" }}{PARA 0 "" 0 "" {TEXT -1 28 "will be in the range 0..m-1." }} {PARA 0 "" 0 "" {TEXT -1 32 "A very similar function is mods." }} {PARA 0 "" 0 "" {TEXT -1 10 " a mods m;" }}{PARA 0 "" 0 "" {TEXT -1 59 "will produce a number in the range -iquo(m-1,2)..iquo(m,2)" }} {PARA 0 "" 0 "" {TEXT -1 35 "that is equivalent wiht a modulo m." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "If we wan t to obtain factors in " }{TEXT 286 1 "Z" }{TEXT -1 122 "[x] of h then we have to use mods instead of mod, because mod will only produce pos itive numbers, whereas factors of h in " }{TEXT 287 2 "Z[" }{TEXT -1 36 "x] could have negative coefficients." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(0,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(1,5);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(2,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(3,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#!\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods (4,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#!\"\"" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 10 "mods(5,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "L;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7&,(*$)%\"xG\"\"#\"\"\"F)*&\"(O@D(F)F'F)F)\"(Acw*F ),(F%F)*&\"(Z'QZF)F'F)F)\"(>cw*F),(F%F)*&\"(yp-&F)F'F)F)F0F),(F%F)*&\" (*[8DF)F'F)F)F,F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "L:=map (mods,L,p^n); # same as [seq(mods(i,p^n),i=L)];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"LG7&,(*$)%\"xG\"\"#\"\"\"F+*&\"(*[8DF+F)F+!\"\"\"\" $F.,(F'F+*&\"(Z'QZF+F)F+F+\"\"'F.,(F'F+*&F2F+F)F+F.F3F.,(F'F+*&F-F+F)F +F+F/F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "for i in L do gc d(i,h) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 28 "We have obtained factors in " }{TEXT 288 3 "Z_5" }{TEXT -1 124 "[x], i.e. factors with 5-adic coefficients, but it turns out t hat when we mods these factors the results are not factors in " } {TEXT 289 1 "Z" }{TEXT -1 9 "[x] of h." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 53 "But maybe h does not have any factors of degree 2 in " }{TEXT 290 1 "Z" }{TEXT -1 4 "[x]?" }}{PARA 0 "" 0 " " {TEXT -1 34 "That is very well possible. Since " }{TEXT 291 3 "Z_5" }{TEXT -1 102 " is a larger ring than Z, it is possible that there are factors of degree 2 in Z_5[x] but not in Z[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 "Does h have any factors o f odd degree in " }{TEXT 292 1 "Z" }{TEXT -1 4 "[x]?" }}{PARA 0 "" 0 " " {TEXT -1 42 "That must be impossible, because if f in " }{TEXT 293 1 "Z" }{TEXT -1 46 "[x] is a factor of h, then we can factor f in " } {TEXT 294 3 "Z_5" }{TEXT -1 120 "[x], and the result should be a subli st of the list L computed above. But we have only even degree factors \+ in that list." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "So the conclusion is: either h is irreducible in " } {TEXT 295 1 "Z" }{TEXT -1 247 "[x], or it is a product of two irreduci ble polynomials f and g of degree 4. These f and g (modulo p^n) must b e products of two elements of L. So what we'll do is: take all product s of 2 elements of L, mods them, and check if they're a factor of h." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 74 "possible_factors:=\{seq(s eq(mods(expand(L[i]*L[j]),p^n),i=1+j..4),j=1..4)\};" }}{PARA 12 "" 1 " " {XPPMATH 20 "6#>%1possible_factorsG<(,(*$)%\"xG\"\"%\"\"\"F+*&\"\"#F +)F)F-F+!\"\"\"\"*F+,,F'F+*&\"(e^A#F+)F)\"\"$F+F+*&\"# " 0 "" {MPLTEXT 1 0 53 "possible_facto rs:=\{seq(gcd(i,h),i=possible_factors)\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%1possible_factorsG<%\"\"\",(*$)%\"xG\"\"%F&F&*&\"\"#F &)F*F-F&!\"\"\"\"*F&,(F(F&*&F+F&F.F&F&\"#OF&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "convert(possible_factors,`*`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&,(*$)%\"xG\"\"%\"\"\"F)*&\"\"#F))F'F+F)!\"\"\"\"*F )F),(F%F)*&F(F)F,F)F)\"#OF)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "expand(%-h);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(h);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&,(*$)%\"xG\"\"%\"\"\"F)*&\"\"#F))F'F+F)!\"\"\"\"*F )F),(F%F)*&F(F)F,F)F)\"#OF)F)" }}}}{MARK "0 1 0" 1 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }