Manuel Kauers Hagenberg, January 7, 2003 RISC-Linz

Computer Algebra Exercises

Solution 5

Ex. (22) We are about to compute the bivariate gcd of f and g where

f(x, y) = y^{6} + xy^{5} + x^{3}y − xy + x^{4} − x^{2}
g(x, y) = xy^{5} − 2y^{5} + x^{2}y^{4} − 2xy^{4} + xy^{2} + x^{2}y.

Let’s take y as main variable, i.e. let’s write

f(x, y) = y^{6} + xy^{5} + (x^{3} − x)y + (x^{4} − x^{2})
g(x, y) = (x − 2)y^{5} + (x^{2} − 2x)y^{4} + xy^{2} + x^{2}y.

We find M := 1 + min(deg_{y}(f), deg_{y}(g)) = 5.

\begin{matrix}r & f(x, r) & g(x, r) & gcd & g \\ 1 & x^{4} + x^{3} − x^{2} + 1 & −2x^{2} − 2 & x + 1 & x + 1 \\ 2 & x^{4} + 2x^{3} − x^{2} + 30x + 64 & 18x^{2} + 4x − 64 & x + 2 & x + y \\ 3 & x^{4} + 3x^{3} − x^{2} + 240x + 729 & 84x^{2} + 90x − 486 & x + 3 & x + y \\ 4 & x^{4} + 4x^{3} − x^{2} + 1 020x + 4 096 & 260x^{2} + 528x − 2 048 & x + 4 & x + y \\ 5 & x^{4} + 5x^{3} − x^{2} + 3 120x + 15 625 & 630x^{2} + 1 900x − 6 250 & x + 5 & x + y \end{matrix}

We verify that x + y | f(x, y) and x + y | g(x, y) and thus find

gcd(f(x, y), g(x, y)) = x + y.

Ex. (26)

squarefree := proc(poly, p)
local a, Da, l, i, j, l1, l2, r, f, g, trash;
  a := poly; Da := diff(a, x) mod p;
  g := Gcd(a, Da) mod p; r := [];
  if a = 0 or degree(a) = 0 then
    r := [[a,1]];
  elif g = 1 or g = a then
     if Da = 0 then
       l := sf1(subs(x=x^(1/p), a), p);
       for f in l do
         r := [op(r), [f[1], f[2] * p]];
       od;
     else
       r := [[a,1]];
     fi;
  else

l1 := sf1(Quo(a, g, x, 'trash') mod p, p); l2 := sf1(g, p);
l := [[1,i] $ i=1..(max(l1[j][2] $j=1..nops(l1)) +
                    max(l2[j][2] $j=1..nops(l2)))];
for i from 1 to nops(l1) do
  for j from 1 to nops(l2) do
    g := Gcd(l1[i][1], l2[j][1]) mod p;
    if not g = 1 then
      l1[i][1] := Quo(l1[i][1], g, x, 'trash') mod p;
      l2[j][1] := Quo(l2[j][1], g, x, 'trash') mod p;
      l[l1[i][2] + l2[j][2]][1] := l[l1[i][2] + l2[j][2]][1] * g;
    fi;
  od;
  l[l1[i][2]][1] := l[l1[i][2]][1] * l1[i][1];
od;
for j from 1 to nops(l2) do
  l[l2[j][2]][1] := l[l2[j][2]][1] * l2[j][1];
od;
for f in l do
  if not f[1] = 1 then
    r := [op(r), f];
  fi;
od;
fi;
r;
end;

Using this procedure, we obtain

>> squareFree(x^7+x^5+x^4+x^3+x^2+1, 3);

(x + 2)^{2}(x + 1)^{5}

and indeed

>> expand(%) mod 3;

x^{7} + x^{5} + x^{4} + x^{3} + x^{2} + 1

Ex. (27) Let a(x) = x^{6} + 2x^{4} + x^{2} + 2.

a) Squarefree decomposition of a in ℚ[x]:

gcd(a, a′) = gcd(x^{6} + 2x^{4} + x^{2} + 2, 6x^{5} + 8x^{3} + 2x) = 1,

so a is already squarefree and we are done.

b) Squarefree decomposition of a in ℤ_{5}[x].

gcd(a, a′) = gcd(x^{6} + 2x^{4} + x^{2} + 2, x^{5} + 3x^{3} + 2x) = x^{2} + 2

We apply the decomposition algorithm recursively to a_{1} := x^{2} + 2 and a_{2} := a/(x^{2} + 2). By

gcd(a_{1}, a′_{1}) = gcd(x^{2} + 2, 2x) = 1,
gcd(a_{2}, a′_{2}) = gcd(x^{4} + 1, 4x^{3}) = 1.

we see that both a_{1} and a_{2} are squarefree. For the combination of the two results, we note that

gcd(a_{1}, a_{2}) = gcd(x^{2} + 2, x^{4} + 1) = x^{2} + 2,

such that by (x^{4} + 1)/(x^{2} + 2) = x^{2} + 3 we finally get

a = (x^{2} + 3) · (x^{2} + 2)^{2}

as square free decomposition of a in ℤ_{5}[x].

Ex. (28) In order to factor a(x) = a^{6} + 2x^{4} + x^{2} + 2 ∈ ℤ_{5}[x], we have to factor both square free parts separately (cf. Ex. 27).

First, we factor a_{1}(x) = x^{2} + 3: By

1 mod x^{2} + 3 = 1
x^{5} mod x^{2} + 3 = 4x

we obtain

Q − I = (\begin{matrix}1 & 0 \\ 0 & 4 \end{matrix}) − (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) = (\begin{matrix}0 & 0 \\ 0 & 3 \end{matrix}) ⇝ (\begin{matrix}0 & 1 \\ 0 & 0 \end{matrix})

and hence Rank(Q − I) = 2 − 1 = 1, such that x^{2} + 3 is irreducible in ℤ_{5}[x]. Analogously, we factor a_{2}(x) = x^{2} + 2: By

1 mod x^{2} + 2 = 1
x^{5} mod x^{2} + 2 = 4x

such that x^{2} + 3 must also be irreducible.

Putting things together, we obtain the factorization a(x) = (x^{2}+3)·(x^{2}+2)^{2}.

Ex. (29) Factor a(x) = x^{6} + 2x^{4} + x^{2} + 2 over ℚ by Berlekamp-Hensel assuming that the coefficients are bounded by 10. By Exercise 27, we know that a is squarefree over ℤ[x].

First, we have to choose a prime p such that a is squarefree in ℤ_{p}[x]. The exercise text suggests to take p = 5, but this is impossible since a mod 5 is not squarefree, see Exercise 27. We take p = 3 instead, which is possible because

gcd(a, a′) = gcd(x^{6} + 2x^{4} + x^{2} + 2, 2x^{3} + 2x) = 1

in ℤ_{3}[x] such that a must be squarefree there.

In the next step, we have to factor a in ℤ_{3}[x] by the Berlekamp algorithm:

1 mod a = 1
x^{3} mod a = x^{3}
x^{6} mod a = x^{4} + 2x^{2} + 1
x^{9} mod a = x
x^{12} mod a = x^{4}
x^{15} mod a = x^{5} + 2x^{3} + x

leads to

Q − I = (\begin{matrix}1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}) − I = (\begin{matrix}0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 2 & 0 & 2 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix})

⇝ (\begin{matrix}0 & 1 & 0 & 2 & 0 & 2 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}) ,

such that the ker(Q − I) has the basis

{1, x^{3} + x, x^{4}, x^{5} + x}.

The first polynomial in the basis is trivial, the second one yields two factors:

gcd(a, x^{3} + x − 1) = x^{3} + x + 2,
gcd(a, x^{3} + x − 2) = x^{3} + x + 1.

But we expect four factors, so we proceed and obtain

gcd(x^{3} + x + 2, x^{4} − 1) = x + 1,
gcd(x^{3} + x + 2, x^{4} − 2) = x^{2} + 2x + 2,
gcd(x^{3} + x + 1, x^{4} − 1) = x + 2,
gcd(x^{3} + x + 1, x^{4} − 2) = x^{2} + x + 2.

These are the four irreducible factors of a in ℤ_{3}[x], i.e.

a(x) = (x + 1)(x + 2)(x^{2} + 2x + 2)(x^{2} + x + 2)

in ℤ_{3}[x].

We are interested in a factorization of a in ℤ[x], so it remains to “lift” the above result to a factorisation in ℤ_{3^{3}}[x] (we make use of the knowledge that all coefficients are bounded by 10, cf. Exercise sheet). Let a_{1} = x + 1, a_{2} = x + 2, a_{3} = x^{2} + 2x + 2 and a_{4} = x^{2} + x + 2 and

a_{2}^{∗} = ∏_{k=2}^{4} a_{k} = (x + 2)(x^{2} + 2x + 2)(x^{2} + x + 2) = x^{5} + 2x^{4} + x + 2,

a_{3}^{∗} = ∏_{k=3}^{4} a_{k} =  (x^{2} + 2x + 2)(x^{2} + x + 2) = x^{5} + 2x^{4} + x + 2,

a_{4}^{∗} = ∏_{k=4}^{4} a_{k} =  (x^{2} + x + 2) = x^{5} + 2x^{4} + x + 2.

We compute the v_{i} to

1 = (x^{4} + x^{3} + 2x^{2} + x) · \underbrace{(x + 1)}_{=a_{1}} +2 · \underbrace{(x^{5} + 2x^{4} + x + 2)}_{=a_{2}^{∗}}

x^{4} + x^{3} + 2x^{2} + x = (x^{7} + 2x^{6} + x^{5} + 2x^{4} + x^{3} + x)(x + 2)
+ (2x^{4} + 2x^{3} + x^{2} + 2x)(x^{4} + 1)
= (x^{2} + 1) · (x + 2) + 1 · (x^{4} + 1)
x^{4} + 1 = (x^{3} + x^{2} + x + 1) · (x^{2} + 2x + 2)
+ (2x^{3} + x^{2} + 2x + 1) · (x^{2} + x + 2)
= (2x + 1)(x^{2} + 2x + 2) + (x + 1)(x^{2} + x + 2),

i.e. we obtain

(v_{1}, v_{2}, v_{3}, v_{4}) = (2, 1, x + 1, 2x + 1).

Set k := 1 and (ā_{1}, ā_{2}, ā_{3}, ā_{4}) := (a_{1}, a_{2}, a_{3}, a_{4}). We now lift from 3 = 3^{k} to 3^{k+1} = 9.

d̃= a − ∏_{i=1}^{r} ā_{i} mod p^{2} = 3x^{5} + 3x^{4} + 6x^{3} + 3x^{2} + 3x
d = d̃/p^{1} = x^{5} + x^{4} + 2x^{3} + x^{2} + x + 1.
ā_{1} = ā_{1} + 3 · (d · b_{1} mod a_{1}) = x + 4
ā_{2} = ā_{2} + 3 · (d · b_{2} mod a_{2}) = x + 5
ā_{3} = ā_{3} + 3 · (d · b_{3} mod a_{3}) = x^{2} + 5x + 8
ā_{4} = ā_{4} + 3 · (d · b_{4} mod a_{4}) = x^{2} + 4x + 8.

Now, for k := 2 we lift from 9 = 3^{k} to 3^{k+1} = 27.

d̃= a − ∏_{i=1}^{r} ā_{i} mod p^{3} = 9x^{5} + 18x^{3} + 9x + 18
d = d̃/9 = x^{5} + 2x^{3} + x + 2.
ā_{1} = ā_{1} + 9 · (d · b_{1} mod a_{1}) = x + 22
ā_{2} = ā_{2} + 9 · (d · b_{2} mod a_{2}) = x + 5
ā_{3} = ā_{3} + 9 · (d · b_{3} mod a_{3}) = x^{2} + 5x + 26
ā_{4} = ā_{4} + 9 · (d · b_{4} mod a_{4}) = x^{2} + 22x + 26.

Centering the representation around 0, we obtain

(ā_{1}, ā_{2}, ā_{3}, ā_{4}) = (x − 5, x + 5, x^{2} + 5x − 1, x^{2} − 5x − 1)

as result of the lifting process.

It remains to combine these factors to factors of a. None of the v̄_{i} is a factor of a by itself, but

ā_{1} · ā_{2} = x^{2} + 2 mod 27

is a factor:

a = (x^{2} + 2)(x^{4} + 1).

This removes ā_{1} and ā_{2} from the candidate list. It remains to combine factors of x^{4} + 1 out of ā_{3} and ā_{4}. In fact, we already get

ā_{3} · ā_{4} = x^{4} + 1 mod 27.

Putting things together, we finally have the factorization

a = (x^{2} + 2) · (x^{4} + 1).

Ex. (30) to be