Manuel Kauers Hagenberg, December 2, 2002 RISC-Linz

Computer Algebra Exercises

Solution 5

Ex. (21) We compute the gcd of

a = x^{4} − x^{3} − 2x^{2} + 3x − 1 and
b = x^{4} − x^{3} + x^{2} + x − 2

using the modular algorithm. In our case, d = gcd(lc(a), lc(b)) = 1 and

M = 2 · 2^{min(4,4)} gcd(a_{4}, b_{4}) · min (\frac{1}{|a_{4}|}\sqrt{∑_{i=0}^{4} a_{i}^{2}}, \frac{1}{|b_{4}|}\sqrt{∑_{i=0}^{4} b_{i}^{2}})
= 2 · 2^{4} · 1 · min(\sqrt{16}, \sqrt{8})
= 64\sqrt{2}.

By x_{(p)} we denote x mod p, and we write

g_{(p)} = c_{(p)} = gcd(a_{(p)}, b_{(p)})

(Note that d_{(p)} = d = 1 in our special case.) The steps of the computation can be read from the following table.

P p  f_{(p)}, g_{(p)}  g_{(p)}  g
1 2  {x^{4} + x^{3} + x + 1 \atop x^{4} + x^{3} + x^{2} + x}  x^{2} + 1  x^{2} + 1
2 3  {x^{4} + 2x^{3} + x^{2} + 2 \atop x^{4} + 2x^{3} + x^{2} + x + 1}  2x + 1  ⚡
1 5  {x^{4} + 4x^{3} + 3x^{2} + 3x + 4 \atop x^{4} + 4x^{3} + x^{2} + x + 3}  2x + 3  2x − 2
5 7  {x^{4} + 6x^{3} + 5x^{2} + 3x + 6 \atop x^{4} + 6x^{3} + x^{2} + x + 5}  5x + 2  12x − 12
35 11 {x^{4} + 10x^{3} + 9x^{2} + 3x + 10 \atop x^{4} + 10x^{3} + x^{2} + x + 9} 8x^{2} + 2x + 1 12x − 12

385

Finally, since P = 385 > 64\sqrt{2} we are done with the loop, so we redefine g to its primitive part:

g = pp(12x − 12) = x − 1.

We check by

a/g = x^{3} − 2x + 1, b/g = x^{3} + x + 2

that g is actually a divisor.

The polynomial remainder sequence approach is actually also not too bad on this particular example:

x^{4} − x^{3} − 2x^{2} + 3x − 1
x^{4} − x^{3} + x^{2} + x − 2
− 3x^{2} + 2x + 1
132x − 132
0.

Ex. (22)

Ex. (23) Given a prime p and m ∈ ℕ, let K = GF(p), L = GF(p^{m}) = K(α), q = p^{m} and

f = ∑_{i=0}^{q−1} a_{i}x^{i} ∈ L[x].

We are about to show the equivalence of

1. ∀a ∈ L : f(a) ∈ K and

2. x^{q} − x | f(x)^{p} − f(x).

We first prove the equivalence of x^{p} = x and x ∈ K as a lemma. The direction from right to left is asserted by Fermat. As for the other direction, take an arbitrary x = α^{k} ∈ L. Then

α^{k} = (α^{k})^{p} = α^{kp}
⟹ k = kp mod q
⟹ k(p − 1) = 0 mod q
⟹ k = 0 mod q  (since p − 1 ≠ 0 mod q)
⟹ k | q
⟹ α^{k} ∈ K.

This proves the lemma.

Now, using the fact that

x^{q} − x = ∏_{a∈L}(x − a)

we can write

x^{q} − x | f(x)^{p} − f(x)
⟺ ∀a ∈ L : x − a | f(x)^{p} − f(x)
⟺ ∀a ∈ L : f(x)^{p} − f(x) = 0 mod x − a
⟺ ∀a ∈ L : f(x)^{p} = f(x) mod x − a
⟺ ∀a ∈ L : f(a)^{p} = f(a)
⟺^{Lemma} ∀a ∈ L : f(a) ∈ K

quod erat demonstrandum.

Ex. (24) to be

Ex. (25) Let p_{1} · · · · · p_{r} = u be a prime decomposition of u (note that ℤ[x] is factorial). In order to have u be not squarefree modulo some prime p we have to have p_{i} = p_{j} mod p (i ≠ j). However, if |p| is greater than two times the maximum coefficient of p_{i} and p_{j}, then it is ensured that “p_{i} mod p = p_{i} mod ℤ,” because the p_{i} are primitive since u is primitive by assumption. This means that p_{i} ≠ p_{j} in ℤ_{p}[x] because p_{i} ≠ p_{j} in ℤ[x]. Now there are only finitely many p which satisfy the necessary condition which completes the proof.