gcd of polynomials over Z_7

Question

I want the gcd of the two polynomials:

$$f=x^5+3x^4+5x^3+x^2+x+3$$

$$g=2x^3+4x^2+x$$

in $Z_7[x]$.

My approach:

I use the euclidean algorithm and continue until I get no remainder.

$$(x^5+3x^4+5x^3+x^2+x+3):(2x^3+4x^2+x) = (4x^2+4x+3) + (6x^2+5x+3)$$

Step 2:

$$(2x^3+4x^2+x):(6x^2+5x+3) = (5x)+(0)$$

Is that correct? So the gcd of $f$ and $g$ is $5x$?! Or do I have to do more?

Answer 1

Calculating the/a GCD for polynomials over a field is virtually the same as calculating the GCD in the integers.

Define a sequence of successive remainders $r_k$ like so:

• Set $r_0 =f$.
• Set $r_1 = g$.
• As long as $r_k\neq 0$ set $r_{k+1}$ the remainder of the division of $r_{k-1}$ by $r_k$.

This will generate a finite sequence of remainders $r_0, r_1 , \dots r_n, r_{n+1} = 0$.

A GCD of $f$ and $g$ is given by $r_n$ the last non-zero remainder. That is in your case $6x^2 + 5x + 3$.

However, note this is a GCD, not really the GCD, as multiplication by any non-zero element of the base field would yield another GCD.

Furthermore, sometimes the convention is in place that the GCD is the normed polynomial that is a GCD. If you are working under this assumption you should multiply $6x^2 + 5x + 3$ by an appropriate constant to get the normed polynomial associated to that one. (This is analogous the convention that the GCD of two integers is positive.)