{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 }{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 19 "More on re
sultants." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
37 "Let alpha be a root of f1 := x^3+x+1." }}{PARA 0 "" 0 "" {TEXT -1 
36 "Let beta be a root of f2 := y^3-y+1." }}{PARA 0 "" 0 "" {TEXT -1 
0 "" }}{PARA 0 "" 0 "" {TEXT -1 129 "Find a polynomial F in Q[z] such \+
that alpha+beta is a root of F. This is basically an elimination probl
em, we have the equations:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 
"" 0 "" {TEXT -1 19 "(1)  z - (x+y)  = 0" }}{PARA 0 "" 0 "" {TEXT -1 
14 "(2)  x^3+x+1=0" }}{PARA 0 "" 0 "" {TEXT -1 14 "(3)  y^3-y+1=0" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 93 "So we hav
e three equations with variables x,y,z, and we want to have an equatio
n with just z." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }{TEXT 257 102 "General Principle: When you have two equ
ations and you want to eliminate one variable use a resultant." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 218 "Take the
 equation (1). We want to eliminate both x and y, so that we end up wi
th an equation in just z. The way to do this is first eliminate x usin
g (2) or eliminate y using (3), and then eliminate the other variable.
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "f1:=x^3+x+1;" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "f2:=y^3-y+1;" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "eqn:=z-(x+y);" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 39 "eqn:=resultant(eqn,f1,x); # eliminate x" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "eqn:=resultant(eqn,f2,y); # \+
eliminate y" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "factor(eqn);
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 213 "Since eqn is irreducible we \+
see that it must be the unique monic polynomial F of minimal degree su
ch that alpha+beta is a root of F, and apparantly it didn't matter whi
ch roots alpha and beta we took of f1 and f2." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "Sometimes of course that \+
does matter. Suppose" }}{PARA 0 "" 0 "" {TEXT -1 11 "f1=x^3+x+1." }}
{PARA 0 "" 0 "" {TEXT -1 70 "f2=y^3+y+1  (which is the same as f1, jus
t a different variable name)." }}{PARA 0 "" 0 "" {TEXT -1 109 "Take a \+
root alpha from f1 and beta from f2. Then there are two essentially di
fferent ways to do this, namely:" }}{PARA 0 "" 0 "" {TEXT -1 15 "alpha
=beta. Or:" }}{PARA 0 "" 0 "" {TEXT -1 12 "alpha<>beta." }}{PARA 0 "" 
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 263 "If alpha=beta, then
 it is easy to see that alpha+beta will be a root of subs(x=z/2, f1) w
hich has degree 3, and is irreducible because f1 is irreducible. So th
e resultant, which will have again degree 9, must have an irreducible \+
factor subs(x=z/2,f1) of degree 3." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 12 "f1:=x^3+x+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 17 "f2:=subs(x=y,f1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "
eqn:=z-(x+y);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "eqn:=resul
tant(eqn,f1,x); # eliminate x" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 39 "eqn:=resultant(eqn,f2,y); # eliminate y" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 12 "factor(eqn);" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 17 "%/subs(x=z/2,f1);" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 10 "normal(%);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 113 "S
o we see that if alpha=beta, then alpha+beta is a root of subs(x=z/2,f
1), and otherwise it is a root of z^3+z-1." }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 12 "f1:=x^3+x+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 17 "f2:=subs(x=y,f1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
13 "eqn:=z-(x-y);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "factor
(resultant(resultant(eqn,f1,x),f2,y));" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 218 "Now we've computed a polynomial for which alpha-beta wil
l be a root. That is either z=0 when alpha=beta, or it is a polynomial
 of degree 6 when alpha<>beta. Let's check that that factor indeed has
 alpha-beta as a root." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "F:
=%/z^3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "alpha:=RootOf(f1
,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "evala(f1/(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 30 "evala(Factor(F,\{alpha,beta\}));" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "subs(beta=B,alpha=A,%);" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "a_b:=RootOf(F);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "evala(Factor(f1,a_b));" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "subs(a_b=alpha-beta,%);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "evala(Expand(%));" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 39 "What is going on here is the following:" }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 73 "We have the polynomial \+
f1, and we have two distinct roots alpha and beta." }}{PARA 0 "" 0 "" 
{TEXT -1 61 "Now the field K=Q(alpha,beta) contains all three roots of
 f1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "a
lpha-beta is a root of an irreducible polynomial F of degree 6." }}
{PARA 0 "" 0 "" {TEXT -1 71 "a_b is RootOf(F), so a_b is the differenc
e of two distinct roots of f1." }}{PARA 0 "" 0 "" {TEXT -1 26 "Let L b
e the field Q(a_b)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 233 "Now K contains all roots of f1, hence it contains all \+
differences of roots of f1, and these are the roots of F, hence K cont
ains all roots of F.  And we verified that above, we saw that F factor
s into linear factors over the field K." }}{PARA 0 "" 0 "" {TEXT -1 0 
"" }}{PARA 0 "" 0 "" {TEXT -1 174 "Since a_b in K, L is a subfield of \+
K. We've seen that f1 factors into linear factors over L. This means t
hat all roots of f1, so alpha,beta in L, and so K is a subfield of L.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 16 "Concl
usion:  K=L" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 296 "More generally, when you have K=Q(alpha1,alpha2,...,alpha_n), \+
then you can always find an element gamma in K such that K=Q(gamma). T
he way to find such gamma is to pick gamma at random, and then check t
hat Q(gamma) has the same dimension as Q-vector space as K. If not, ta
ke another random gamma." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "
" 0 "" {TEXT -1 147 "If K is a field, and K is a subfield of L, then L
 is a K-vector space. The degree of L over K is defined as the dimensi
on of L as a K-vector space." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 
0 "" 0 "" {TEXT -1 129 "If K is a field, and f in K[x] is an irreducib
le polynomial, then the degree of the field K[x]/(f) over K equals the
 degree of f." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 158 "Theorem: If K is a subfield of L, and L a subfield of M,
 then the degree of M over K equals the product of the degree of M ove
r L with the degree of L over K." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 64 "The degree of Q(alpha) over Q in our exam
ple was degree(f1,x)=3." }}{PARA 0 "" 0 "" {TEXT -1 129 "The degree of
 Q(alpha,beta) over Q(alpha) was 2, because beta was a root of an irre
ducible polynomial in Q(alpha)[x] of degree 2." }}{PARA 0 "" 0 "" 
{TEXT -1 77 "Applying the theorem we see that the degree of Q(alpha,be
ta) over Q is 3*2=6." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 98 "Now this field was the same as Q(a_b), and the degree o
f that over Q was degree(F,z), which was 6." }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "Lets look at another example:" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 22 "f1 := factor(x^4+x+1);" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 22 "f2 := factor(y^4+y+2);" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 18 "alpha:=RootOf(f1);" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 24 "evala(Factor(f2,alpha));" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 17 "beta:=RootOf(f2);" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 79 "So the theorem says that Q(alpha,beta) is a Q-vector spac
e of dimension 4*4=16." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 
0 "" {TEXT -1 66 "A basis of this vector space is:  alpha^i*beta^j,  i
=0..3, j=0..3." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "F:=factor
(resultant(resultant( z-(x+y) , f1,x),f2,y));" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 77 "We see that alpha+beta is a root of this irreducible p
olynomial of degree 16." }}{PARA 0 "" 0 "" {TEXT -1 110 "So K:=Q(alpha
,beta) contains a root alpha+beta of F. That means that we have an emb
edding (a 1-1 homomorphism)" }}{PARA 0 "" 0 "" {TEXT -1 26 "Q[z]/(F)  \+
-> Q(alpha,beta)" }}{PARA 0 "" 0 "" {TEXT -1 27 "by sending z to alpha
+beta." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
219 "So we can view L:=Q[z]/(F) as a subfield of K. But L has degree d
egree(F,z)=16 over Q. And K has degree 4*4=16 over Q. So L is a subvec
tor space of K, but has the same dimension as K. Therefore, K must be \+
the same as L." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 53 "Therefore, L must have a root of f1 and a root of f2." }}
{PARA 0 "" 0 "" {TEXT -1 83 "And K must have a root of F (but we alrea
dy know that, it has the root alpha+beta)." }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 333 "So we know a priori that f1 an
d f2 are reducible over L = Q[z]/(F) = Q(Gamma), where Gamma=RootOf(F)
, they both must have at least one factor of degree 1. But even though
 we know this a priori without any computation, actually finding those
 factors is far from trivial; without a computer you'd have a hard tim
e finding such factors." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 160 
"alias(Gamma=RootOf(F)); # We could also do: Gamma:=RootOf(F), but thi
s way Maple prints Gamma instead of RootOf(large polynomial) which wou
ld clog up the screen" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "ev
ala(Factor(f1,Gamma));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "e
vala(Factor(f2,Gamma));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "
A:=roots(f1,Gamma)[1,1];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 
"B:=roots(f2,Gamma)[1,1];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 
"A+B;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 261 "We see that instead of \+
working with Q(alpha,beta)  (where we have to deal with 2 RootOf's) we
 could also work with Q(Gamma) (which seems easier because then we're \+
dealing with only 1 RootOf) because that is an isomorphic field. We ca
n also give the isomorphism:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 
0 "" 0 "" {TEXT -1 71 "Q(Gamma)      -> Q(alpha,beta) is given by: sub
s(Gamma=alpha+beta, ...)" }}{PARA 0 "" 0 "" {TEXT -1 66 "Q(alpha,beta)
 -> Q(Gamma) is given by: subs(alpha=A, beta=B, ....)" }}{PARA 0 "" 0 
"" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 93 "and with those subs co
mmands we can translate elements of Q(Gamma) to Q(alpha,beta) and back
." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 198 "But
 we also see that there are disadvantages of using Q(Gamma) instead of
 Q(alpha,beta) because some expressions (even expressions like alpha a
nd beta) become very large when translated to Q(Gamma)." }}{PARA 0 "" 
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }{TEXT 258 19 "Other applications:" }}{PARA 0 "" 0 "" 
{TEXT -1 100 "Suppose we have the field K=Q(alpha,beta) and suppose we
 have some large matrix M with entries in K." }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 163 "Suppose we want to verify with
 a computer that det(M) is not zero. If p is a prime number, and if de
t(M) mod p is non-zero, then det(M) is non-zero and we're done." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 151 "By multi
plying the rows of M with integers we may assume that the entries are \+
in Z[alpha,beta]. Now we want to reduce this modulo p. We can do that \+
by:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 37 "Z[
alpha,beta]   ->  Fp[x,y]/(f1, f2)." }}{PARA 0 "" 0 "" {TEXT -1 141 "T
he integers are just reduced modulo p, and we send alpha to x, and bet
a to y, and this is a homomorphism because f1(alpha)=0 and f2(beta)=0.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 321 "Now \+
R := Fp[x,y]/(f1, f2) is not necessarily a field, for it to be a field
 we would need that f1 is irreducible in Fp[x], and that f2 is irreduc
ible over Fp[x]/(f1). In our example that will not be the case for any
 prime number p because degree(f1,x)=degree(f2,x) (we'll see later why
 this implies that R is not a field)." }}{PARA 0 "" 0 "" {TEXT -1 566 
"In any case, we can compute det(M) in the ring R, and if it's non-zer
o then det(M) is non-zero. During this deteterminant computation we ca
n reduce all coefficients modulo p and that will speed up the computat
ion. But we still have to work with x and y modulo the polynomials f1 \+
and f2. This can be speeded up when we have a prime number p, such tha
t Fp contains a root R1 of f1 and a root R2 of f2. So we're looking fo
r a prime number p, such that there exist integers R1,R2, for which f1
(R1) and f2(R2) are 0 modulo p. This can be done very easily when you \+
have F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "F;" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "for i from -5 to 5 do ifactor(subs(
z=i,F)) od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 385 "For every prime p
 we've found here, it is so that F has a root mod p (namely the value \+
i that we substituted for z). But alpha and beta can be expressed in t
erms of that root, by those big expressions A,B we had above. And when
ever those expressions doesn't have p in the denominator, then those e
xpressions will give us roots of f1 and f2 modulo p in terms of the ro
ot \"i mod p\" of F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "ifa
ctor(denom(A));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "ifactor(
denom(B));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "So we can take for
 example p=17, which we found by substituting z=-3 in F. So -3 is a ro
ot of F modulo p." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p:=17;
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(F) mod p;" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "subs(Gamma=-3,A) mod p;" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "subs(Gamma=-3,B) mod p;" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 96 "So we see that f1 has a root 3 in \+
Fp, and f2 has a root 11 in Fp. Let's check that using Factor:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Factor(f1) mod p;" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Factor(f2) mod p;" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "So we find the following homomorph
ism:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "Z
[alpha,beta]  ->  F17" }}{PARA 0 "" 0 "" {TEXT -1 31 "by reducing inte
gers modulo 17," }}{PARA 0 "" 0 "" {TEXT -1 43 "sending alpha to 3, an
d sending beta to 11." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 
"" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 442 "Now lets say that com
puting modulo 17 doesn't give enough information. Well, then we can al
so compute modulo 17^2. Or modulo 17^n, that is, we compute with 17-ad
ic numbers up to accuracy n. Since f1 and f2 are square-free even modu
lo p=17, we can apply the Hensel lemma to the factorization of f1 and \+
f2 modulo p, and we conclude that f1 and f2 both have a degree 1 facto
r over the 17-adic numbers, so they have a root in the 17-adic numbers
." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "with(padic):" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "rootp(f1,17);" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "rootp(f2,17);" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 162 "So if we had this large matrix M with entries in \+
Q(alpha, beta), and we wanted to check if the determinant is zero or n
ot, then what we could do is the following:" }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "1) if there appear factors 17 i
n the denominator, then multiply that row by 17." }}{PARA 0 "" 0 "" 
{TEXT -1 94 "2) replace alpha by rootp(f1,17) and beta by rootp(f2,17)
, and reduce all entries modulo 17^9." }}{PARA 0 "" 0 "" {TEXT -1 178 
"3) Compute the determinant in Z/(17^9), which should be very fast bec
ause you never get to see any large integers, and you don't see the al
gebraic numbers alpha and beta anymore." }}{PARA 0 "" 0 "" {TEXT -1 0 
"" }}{PARA 0 "" 0 "" {TEXT -1 87 "4) If det(M) mod 17^9 is non-zero, o
k, then you've established that det(M) is non-zero." }}{PARA 0 "" 0 "
" {TEXT -1 167 "5) If det(M) mod 17^9 equals 0, then det(M) is zero wi
th high probability. If you make the accuracy (which was 9 here) highe
r than the probability will also be higher." }}}}{MARK "69" 0 }
{VIEWOPTS 1 1 0 1 1 1803 }