{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 }{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 28 "The ring of 10-adic number s." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{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 las t 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 followi ng infinite sequence:" }}{PARA 0 "" 0 "" {TEXT -1 56 "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 inte gers modulo 10^n. Then the n'th entry of S can be viewed as an element of Z/10^n." }}{PARA 0 "" 0 "" {TEXT -1 71 "We can view S as an elemen t 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." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 196 "Now define the set Z_10 as the set of all elements \+ S of Z/10^1 * Z/10^2 * Z/10^3 * Z/10^4 * .... that have that propert y, i.e. that if i " 0 "" {MPLTEXT 1 0 15 "-123 mod 10^50;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 128 "Negative \+ integers will at some point have just 9's on the left. Note that Z_10 \+ also contains some rational numbers, but not all:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 14 "1/2 mod 10^50;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "r:=1/3 mod 10^50;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "r*3 mod 10^50;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 187 "So we have an element in Z_10 consisting of .....6666667, i.e. o ne 7 and then infinitely many 6's on the left of that. Multiplying tha t element by 3 gives 1, so that element will be 1/3." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 284 "The set Z_10 is a ring , not a field, because we can not divide by all non-zero elements. We \+ can represent 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 65 "In the same way w e can also define Z_p as the set of formal sums:" }}{PARA 0 "" 0 "" {TEXT -1 65 " sum_\{n >= 0\} a.n * p^n where the a.i are in the ran ge 0..p-1." }}{PARA 0 "" 0 "" {TEXT -1 114 "This Z_p is called the rin g of p-adic integers. This ring has no zero divisors if and only if p \+ is a prime number." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "When p is a prime number then the fraction field Q_p of Z _p 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 51 "This set Q_p is called the field of p-adi c numbers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "with(padic); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "r:=evalp(1/3,7);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "evalp(3*r,7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "evalp( 1/20! , 7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "evalp( 1/20! , 7,20);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "evalp(20!*% , 7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "evalp( sqrt(2), 7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "evalp(%^2, 7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "evalp( sqrt(3), 7);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "Q_7 does not contain any element whose square equals 3. Note t hat Fp also contains no element whose square equals 3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 163 "Now lets look at Z_ 10 again, and consider the element r:=1/7, so r is the root of the po lynomial 7*x-1 in Z_10. To determine r in Z_10 is the same as determin ing:" }}{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;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^4;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^5;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/ 7 mod 10^6;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^7 ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^8;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^9;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "1/7 mod 10^10;" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 14 "1/7 mod 10^11;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 385 "If r is the exact element in Z_10 that is a root of the \+ polynomial 7*x-1, then what we have computed above are approximations \+ of r. First with 1 digit accurate, then with 2 digits accurate, then w ith 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- adic 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 107 "So, what we want is, given r modulo 10^n, compute r modulo 10^ (n+1). This process is called HENSEL LIFTING." }}{PARA 0 "" 0 "" {TEXT -1 135 "Then we only need to compute r modulo 10^1, and we can i ncrease 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 in 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 accuracy n. That mean s: 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 wa nt 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 integer r' such that :" }}{PARA 0 "" 0 "" {TEXT -1 48 "7*x-1 is equivalent to 7*(x-r') modu lo 10^(n+1)." }}{PARA 0 "" 0 "" {TEXT -1 171 "The last 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, whic h 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 divi de 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;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "r:=1/7 mod 10^11 ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "r:=r+d*10^n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "(r*7-1)/10^n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "solv e(%,d) mod 10;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "r:=subs(d =%,r);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "Now we've increased the accuracy from 11 to 12. Lets Hensel lift it further to accuracy 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)\no d;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^n;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 88 "Now lets Hensel lift some other factorizations, this time over Z_7, the 7-adic integers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=7;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "h:=x^2-2;" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(h) mod p;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f:=op(1,%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "g:=op(2,%%);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 22 "Expand(h-f*g) mod p^1;" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 22 "Expand(h-f*g) mod p^2;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 170 "We will view f,g,h now as polynomials in Z_7[x]. As we see, the product f*g is h up to accuracy 1, but not up to accuracy 2. We will try to Hensel lift the factorization:" }}{PARA 0 "" 0 "" {TEXT -1 8 " h = f*g" }}{PARA 0 "" 0 "" {TEXT -1 68 "That is, suppose \+ that the factorization has accuracy n, which means:" }}{PARA 0 "" 0 " " {TEXT -1 33 "h is equivalent to f*g modulo p^n" }}{PARA 0 "" 0 "" {TEXT -1 58 "Then we want 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 136 "An d this process converges in the ring Z_7[x]. So, after infinitely many steps we would get an exact factorization of h=x^2-2 in Z_7[x]." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 241 "How do w e Hensel lift the polynomials f and g (which have accuracy n) up to ac curacy n+1? Since f and g are already correct modulo p^n, we only need to add something that is a multiple of p^n, we don't need any lower p owers 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 equat e it to 0 modulo p, and then 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_modp) mod p, [f,g]))\nod;\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(h - f*g);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "% mod p^n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "g;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "r:=x-f;" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 12 "r^2 mod p^n;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "In general the Hensel lifting procedure works as follows:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 39 "Suppose f ,g,h in Z[x] and suppose that:" }}{PARA 0 "" 0 "" {TEXT -1 195 " h is equivalent to f*g modulo p^n where n>=1\nand suppose furthermore tha t 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 t hat:" }}{PARA 0 "" 0 "" {TEXT -1 15 " Gcd(f,g) mod p" }}{PARA 0 "" 0 " " {TEXT -1 117 "equals 1, so f and g have no common 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) < degree(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 169 "By repeating this infinitely m any times, one will find polynomials F, G in Z_p[x] such that h is exa ctly (not just modulo 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, modulo 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 equivalent 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 118 "Now compute h-f*g modulo p^(n+1), this must be of the form R*p^n \+ for some R in Z[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 beco mes:" }}{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 soluti on f0 and g0 modulo p (with the conditions on the degree above) that c an be computed by the Extended Euclidean Algorithm." }}{PARA 0 "" 0 " " {TEXT -1 3 "Do:" }}{PARA 0 "" 0 "" {TEXT -1 28 " Gcdex(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 f 0=R*t and g0=R*s then f0, g0 do not necessarily satisfy the degree con ditions (degree(f0) < degree(f) and degree(g0) < degree(g)). So we hav e 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 degre e(f0) " 0 "" {MPLTEXT 1 0 911 "Hensel_lift := proc(f,g,h ,x,N,p)\n # Input: a positive integer n, and\n # monic polynomials f,g,h in Z[x] such that:\n # h is f*g mod p.\n\n # Output: monic \+ 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) is\n \+ # h modulo p^(n+1).\n # Take f0, g0 = R*t, R*s as explai ned 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 condit ions,\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:=Ex pand(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 750 "HenselLift:=proc (L::list,h,x::name,N::posint,p::posint)\n # Input: a list L=[f1,f2,. ..fk] of polynomials such that\n # f1*f2*...*fk is h modulo p, and a ll f.i have Gcd 1.\n #\n # Output: 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(pro cname(L1,h1,x,N,p)), op(procname(L2,h2,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+3 24;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=5;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "L:=Factors(h) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "L:=[seq(i[1],i=L[2])];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "convert(L,`*`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "expand(% - h);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 8 "% mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "n:=10; L:=HenselLift(L,h,x,n,p);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "convert(L,`*`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "expand(% - h);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "% mod p^n;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "The Maple f unction mod always produces non-negative numbers, if a and m are integ ers 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 193 "If we want to obtain fac tors in Z[x] of h then we have to use mods instead of mod, because mod will only produce positive numbers, whereas factors of h in Z[x] coul d have negative coefficients." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(0,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(1, 5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(2,5);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(3,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(4,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(5,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "L;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "L:=map(mods,L,p^n) ; # same as [seq(mods(i,p^n),i=L)];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "for i in L do gcd(i,h) od;" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 165 "We have obtained factors in Z_5[x], i.e. factors with \+ 5-adic coefficients, but it turns out that when we mods these factors \+ the results are not factors in Z[x] of h." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "But maybe h does not have any fact ors of degree 2 in Z[x]?" }}{PARA 0 "" 0 "" {TEXT -1 139 "That is very well possible. Since Z_5 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 46 "Does h have any fa ctors of odd degree in Z[x]?" }}{PARA 0 "" 0 "" {TEXT -1 212 "That mus t be impossible, because if f in Z[x] is a factor of h, then we can f actor f in Z_5[x], and the result should be a sublist of the list L co mputed above. But we have only even degree factors in that list." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 297 "So the c onclusion is: either h is irreducible in Z[x], or it is a product of t wo irreducible polynomials f and g of degree 4. These f and g (modulo \+ p^n) must be products of two elements of L. So what we'll do is: take \+ all products of 2 elements of L, mods them, and check if they're a fac tor of h." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 74 "possible_facto rs:=\{seq(seq(mods(expand(L[i]*L[j]),p^n),i=1+j..4),j=1..4)\};" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "possible_factors:=\{seq(gcd( i,h),i=possible_factors)\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "convert(possible_factors,`*`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "expand(%-h);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(h);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {MARK "87" 0 }{VIEWOPTS 1 1 0 1 1 1803 }