Let
be nonzero polynomials for an Euclidean domain
.
Let
be a prime.
We denote by
the reduction
modulo
.
We know from the previous section that
![$\displaystyle {\gcd}(f,g) \in R \ \ \ \ \iff \ \ \ \ {\rm res}(f,g) \neq 0$](img177.png) |
(36) |
The formula of the resultant of
and
shows that
is a
multivariate polynomial expression in the coefficients of
and
.
Hence we might be tempted to say
-
.
-
and
are coprime in
iff
does not divide
.
Proof.
Let us write:
![$\displaystyle f \ = \ f_n x^n + \cdots + f_0 \ \ \ \ {\rm and} \ \ \ \ g \ = \ g_m x^m + \cdots + g_0$](img148.png) |
(44) |
with
![$ f_n \neq 0$](img200.png)
and
![$ g_m \neq 0$](img201.png)
.
If
![$ n = 0$](img202.png)
then
![$ {\rm Sylv}(f,g)$](img154.png)
and
![$ {\rm Sylv}(\overline{f},\overline{g})$](img203.png)
are both diagonal with
![$ f$](img64.png)
on the diagonal.
Then in that case
![$\displaystyle \overline{r} \ = \ \overline{f^m} \ = \ \overline{f}^m \ = \ {{\rm res}(\overline{f}, \overline{g})}^m$](img204.png) |
(45) |
If
![$ n > 0$](img205.png)
we distinguish two cases.
If
![$ \overline{g} = 0$](img206.png)
then
![$ {\rm res}(\overline{f},\overline{g}) = 0$](img207.png)
(by Definition
4).
Moreover each
![$ g$](img98.png)
-column of
![$ {\rm Sylv}(f,g)$](img154.png)
is zero modulo
![$ I$](img195.png)
such that
![$ \overline{r} = 0$](img208.png)
too.
From now on assume
![$ \overline{g} \neq 0$](img209.png)
and let
![$ i$](img210.png)
be the smallest index such that
![$ \overline{g_{m-i}} \neq 0$](img211.png)
holds.
![$\displaystyle {\rm Sylv}(f,g) \ = \ \left( \begin{array}{ccccccccc} f_0 & & & &...
...ddots & \vdots & & & & \vdots \\ & & & & f_n & & & & g_m \\ \end{array} \right)$](img212.png) |
(46) |
By exchanging the
![$ f$](img64.png)
-
zone with the
![$ g$](img98.png)
-
zone we have also
![$\displaystyle {\rm res}(f,g) \ = \ (-1)^{n m} \left\vert \begin{array}{cccccccc...
...s & & & & \ddots & \vdots \\ & & & g_m & & & & & f_n \\ \end{array} \right\vert$](img213.png) |
(47) |
Let
![$ M$](img214.png)
be the submatrix obtained from
![$ {\rm Sylv}(g,f)$](img215.png)
by deleting the
last
![$ i$](img210.png)
rows and the last
![$ i$](img210.png)
columns.
Observe that we have
![$\displaystyle \overline{{\rm res}(f,g)} \ = \ (-1)^{n m} \ \overline{{\det}(M)} \ \overline{{f_n}^i}$](img216.png) |
(48) |
Since
![$\displaystyle \overline{{\det}(M)} \ = \ {\det}(\overline{M}) \ = \ {\rm res}(\overline{f},\overline{g})$](img217.png) |
(49) |
we obtain
![$\displaystyle \overline{{\rm res}(f,g)} \ = \ (-1)^{n m} \ {\rm res}(\overline{f},\overline{g}) \ {\overline{{\rm lc}(f)}}^i$](img218.png) |
(50) |
This shows that we have
![$\displaystyle \overline{r} = 0 \ \ \ \ \iff \ \ \ \ {\rm res}(\overline{f}, \overline{g}) = 0$](img197.png) |
(51) |
and the first claim of the lemma is proved.
The second claim follows from
Proposition
6.
Proof.
Since in
![$\displaystyle h \ \mid \ f \ \ \ \ {\rm and} \ \ \ \ h \ \mid \ g$](img224.png) |
(55) |
we have in
![$\displaystyle {\rm lc}(h) \ \mid \ {\rm lc}(f) \ \ \ \ {\rm and} \ \ \ \ {\rm lc}(h) \ \mid \ {\rm lc}(g).$](img225.png) |
(56) |
Therefore
![$\displaystyle {\alpha} \ = \ {\rm lc}(h) \ \mid \ {\gcd}({\rm lc}(f), {\rm lc}(g)) \ = \ b$](img226.png) |
(57) |
and the first claim is proved.
Consider now the cofactors of
![$ f$](img64.png)
and
![$ g$](img98.png)
in
![$\displaystyle u \ = \ f/h \ \ \ \ {\rm and} \ \ \ \ v \ = \ g/h.$](img227.png) |
(58) |
Then we have
![$\displaystyle \overline{u} \, \overline{h} \ = \ \overline{f} \ \ \ \ {\rm and} \ \ \ \ \overline{v} \, \overline{h} \ = \ \overline{g}$](img228.png) |
(59) |
which shows that
![$\displaystyle \overline{h} \ \mid \ {\gcd}(\overline{f}, \overline{g})$](img229.png) |
(60) |
and implies that
![$\displaystyle {\deg}(\overline{h}) \ \leq \ {\deg}({\gcd}(\overline{f}, \overline{g}))$](img230.png) |
(61) |
Since
![$ p$](img61.png)
does not divide
![$ b$](img22.png)
, it cannot not divide
![$ {\alpha}$](img221.png)
neither.
Hence the leading coefficient of
![$ \overline{h}$](img112.png)
is
![$ \overline{{\alpha}}$](img231.png)
and we have
![$\displaystyle {\deg}(\overline{h}) \ = \ {\deg}(h)$](img232.png) |
(62) |
Therefore
![$\displaystyle e \ = \ {\deg}(h) \ \leq \ {\deg}({\gcd}(\overline{f}, \overline{g})) \ = \ e^{\ast}$](img233.png) |
(63) |
and the second claim is proved.
Now consider the case where
.
Since
divides
and since
is monic (as a gcd over
the field
) there exists a unit
such that
![$\displaystyle \overline{h} \ = \ {\beta} \ {\gcd}(\overline{f}, \overline{g})$](img238.png) |
(64) |
Since the leading coefficient of
![$ \overline{h}$](img112.png)
is
![$ \overline{{\alpha}}$](img231.png)
we have in fact
![$\displaystyle {\beta} \ = \ \overline{{\alpha}}$](img239.png) |
(65) |
Therefore we have the following equivalence
![$\displaystyle e \ = \ e^{\ast} \ \ \ \ \iff \ \ \ \ \overline{h} \ = \ \overline{{\alpha}} \ {\gcd}(\overline{f}, \overline{g})$](img240.png) |
(66) |
It remains to prove that
![$\displaystyle \ \ \overline{{\alpha}} \ {\gcd}(\overline{f}, \overline{g}) = \overline{h} \ \ \iff \ \ p \not\mid {\rm res}(f/h, g/h)$](img241.png) |
(67) |
Observe that
![$ p$](img61.png)
cannot divide both
![$ {\rm lc}(u)$](img242.png)
and
![$ {\rm lc}(v)$](img243.png)
.
If this was the case
then from Relation (
59) (and since
![$ p$](img61.png)
does not divide
![$ {\alpha} = {\rm lc}(h)$](img244.png)
)
![$ p$](img61.png)
would divide
![$ {\rm lc}(f)$](img104.png)
and
![$ {\rm lc}(g)$](img105.png)
, and thus
![$ b$](img22.png)
.
A contradiction. Therefore we can assume that
![$ p$](img61.png)
does not divide
![$ {\rm lc}(u)$](img242.png)
.
By applying Lemma
2 we obtain
![$\displaystyle \overline{{\rm res}(u,v)} = 0 \ \ \ \ \iff \ \ \ \ {\rm res}(\overline{u}, \overline{v}) = 0$](img245.png) |
(68) |
By applying Proposition
5
this leads to
![$\displaystyle p \ \mid \ {\rm res}(u,v) \ \ \ \ \iff \ \ \ \ {\gcd}(\overline{u},\overline{v}) \neq 1$](img246.png) |
(69) |
From Relation (
59) we have
![$\displaystyle {\gcd}(\overline{f},\overline{g}) \ = \ {\gcd}(\overline{u},\overline{v}) \ \overline{h} / \overline{{\alpha}}$](img247.png) |
(70) |
Therefore
![$\displaystyle p \ \ \not\mid \ {\rm res}(u,v) \ \ \ \ \iff \ \ \ \ {\gcd}(\overline{f},\overline{g}) \ = \ 1 \ \times \ \overline{h} / \overline{{\alpha}}$](img248.png) |
(71) |
This concludes the proof of the theorem.
Definition 5
Let
be nonzero polynomials for an Euclidean domain
.
Let
be
.
A prime element
is said lucky if
does not divide
otherwise it is said unlucky.
Example 2
Consider
,
and
.
We have the following computation in AXIOM (where we do not display types)
N := NonNegativeInteger
(1) NonNegativeInteger
Z := Integer
(2) Integer
U := UnivariatePolynomial(x,Z)
(3) UnivariatePolynomial(x,Integer)
f: U := 12*x^3 -28*x^2 +20*x - 4
3 2
(4) 12x - 28x + 20x - 4
g: U := -12*x^2 +10*x -2
2
(5) - 12x + 10x - 2
resultant(f,g)
(6) 0
h: U := gcd(f,g)
(7) 6x - 2
r: Z := resultant(exquo(f,h),exquo(g,h))
(8) 2
K17 := PrimeField(17)
(9) PrimeField 17
r :: K17
(10) 2
U17 := UnivariatePolynomial(x,K17)
(11) UnivariatePolynomial(x,PrimeField 17)
f17: U17 := f :: U17
3 2
(12) 12x + 6x + 3x + 13
g17: U17 := g :: U17
2
(13) 5x + 10x + 15
h17: U17 := h ::U17
(14) 6x + 15
c17 := gcd(f17,g17)
(15) x + 11
h17 - (leadingCoefficient(h17)) * c17
(16) 0
Example 3
Consider
,
and
.
We have the following computation in AXIOM (where we do not display types)
The variables N, Z, U are defined as above.
f: U := x^4 -3*x^3 + 2*x
4 3
(4) x - 3x + 2x
g: U := x^3 -1
3
(5) x - 1
resultant(f,g)
(6) 0
h: U := gcd(f,g)
(7) x - 1
r: Z := resultant(exquo(f,h),exquo(g,h))
(8) 9
K3 := PrimeField(3)
(9) PrimeField 3
r :: K3
(10) 0
U3 := UnivariatePolynomial(x,K3)
(11) UnivariatePolynomial(x,PrimeField 3)
f3: U3 := f :: U3
4
(12) x + 2x
g3: U3 := g :: U3
3
(13) x + 2
h3: U3 := h ::U3
(14) x + 2
c3 := gcd(f3,g3)
3
(15) x + 2
exquo(c3, h3)
2
(16) x + x + 1
Marc Moreno Maza
2008-01-07