{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 }