The Euclidean algorithm

Just as in the case of the integers, there is a Euclidean algorithm for polynomials over any ring.

Definition 2.2.11   The greatest common divisor of any two polynomials $f(x),g(x)\in F[x]$ is the monic polynomial $p(x)$ of highest degree such that $p(x)\vert f(x)$ and $p(x)\vert g(x)$ .

Proposition 2.2.12 (Division algorithm)   Let $F$ be a field. If $p(x)$ , $d(x)$ are polynomials in $F[x]$ with $0<$ deg$(d(x))<$ deg$(p(x))$ then there are polynomials $q(x)$ , $r(x)$ in $F[x]$ such that deg$(q(x))<$ deg$(p(x))$ , deg$(r(x))<$ deg$(d(x))$ in $F[x]$ and

$$p(x)=d(x)q(x)+r(x).$$

For $p,d,q,r$ as in the above theorem, we call $q(x)$ the quotient, written $quo(p(x),d(x))$ , and we call $r(x)$ the remainder. written $rem(p(x),d(x))$ .

Example 2.2.13   This does not hold for rings in the form stated. (See Knuth [Kn], §4.6.1, for a more general form of the division algorithm.) For example, If $F=\mathbb{Z}$ , $d(x)=2x$ and $p(x)=x^2$ then there is no quotient $q(x)$ in $\mathbb{Z}[x]$ such that $p(x)=d(x)q(x)+r(x)$ holds.

Example 2.2.14   Let $p(x)=3x^6+5x^4-4x^2-9x+21$ , $d(x)=x^2+1$ . We have

		$3x^4$		$2x^2$		$-6$
$x^2+1$		$3x^6$	$+0\cdot x^5$	$5x^4$	$0\cdot x^3$	$-4x^2$	$-9x$	$+21$
		$3x^6$	$+0\cdot x^5$	$3x^4$
				$2x^4$	$0\cdot x^3$	$-4x^2$	$-9x$	$+21$
				$2x^4$	$0\cdot x^3$	$2x^2$
						$-6x^2$	$-9x$	$+21$
						$-6x^2$	$0\cdot x$	$-6$
							$-9$ x	$+27$

So $q(x)=3x^4+2x^2-6$ and $r(x)=27-9x$ .

Theorem 2.2.15 (Euclidean algorithm for polynomials)   Let $F$ be a field. If $a(x)$ , $b(x)$ are polynomials in $F[x]$ then there are polynomials $p(x)$ , $q(x)$ in $F[x]$ such that

$$gcd(a(x),b(x))=a(x)p(x)+b(x)q(x).$$

The proof of this, which is very similar to the proof for the case of the integers given in chapter 1, is omitted. However, here is a sketch of the Euclidean algorithm for polynomials.

Let $r_{-1}=a$ and $r_0=b$ . Let $i=0$ .

(1)

Use the division algorithm to compute polynomials $q_{i+1}$ and $r_{i+1}$ , $0\leq \deg(r_{i+1})<deg(r_i)$ such that

$$r_{i-1}=r_iq_{i+1}+r_{i+1}.$$

(2)

If $r_{i+1}\not= 0$ then increment $i$ and go to step 1. If $r_{i+1}=0$ then stop.

Since $0\leq ...<deg(r_1)<deg(r_0)=deg(b)<deg(r_{-1})=deg(a)$ , at some point the above algorithm must terminate. Suppose that $r_k=0$ and $k$ is the smallest such integer. Fact: $gcd(a,b)=r_{k-1}$ .

Corollary 2.2.16   Let $a(x)$ and $b(x)$ be polynomials in $F[x]$ , where $F$ is a field. $a(x)$ is relatively prime to $b(x)$ if and only if there are $p(x),q(x)\in F[x]$ such that $a(x)p(x)+b(x)q(x)=1$ .

proof: (only if) This is a special case of the Euclidean algorithm above.

(if) If $d(x)\in F[x]$ is a non-zero polynomial satisfying both $d(x)\vert a(x)$ and $d(x)\vert b(x)$ then $d(x)\vert(a(x)p(x)+b(x)q(x)=1$ , so $d\vert 1$ . This forces $d(x)\in F^\times$ , so $gcd(a(x),b(x))=1$ . $\Box$

Here is a reformulation of the Euclidean Algorithm.

Theorem 2.2.17   Let $f(x),g(x)\in F[x]$ be given, where $F$ is a field. Assume $deg(g(x))\leq deg(f(x))$ , and let $r_{-1}(x)=f(x)$ , $r_0(x)=g(x)$ . Repeated Euclidean Algorithm can be regarded as a sequence of polynomials $\{r_k(x)\}$ , $\{a_k(x)\}$ , and $\{b_k(x)\}$ satisfying the following properties.

• For $k>0$ ,
  $$r_{k-2}(x)=q_k(x)r_{k-1}(x)+r_k(x), \ deg(r_k(x))<deg(r_{k-1}(x)),$$
  $$r_k(x)=a_k(x)f(x)+b_k(x)g(x).$$

• For some $\ell$ ,
  $$gcd(f(x),g(x))=a(x)f(x)+b(x)g(x),$$
  where $a(x)=a_\ell(x)$ , $b(x)=b_\ell(x)$ .

• $$deg(a_k(x))=\sum_{j=2}^k deg(q_j(x)), \ deg(b_k(x))=\sum_{j=1}^k deg(q_j(x)).$$

• $$\det \left( \begin{array}{cc} a_k(x) & b_k(x)\\ a_{k+1}(x) & b_{k+1}(x) \end{array}\right) =(-1)^{k+1}.$$

• $$\det \left( \begin{array}{cc} r_k(x) & b_k(x)\\ r_{k+1}(x) & b_{k+1}(x) \end{array}\right) =(-1)^{k+1}f(x).$$

• $$\det \left( \begin{array}{cc} u_k(x) & r_k(x)\\ u_{k+1}(x) & r_{k+1}(x) \end{array}\right) =(-1)^{k+1}g(x).$$

Remark 2.2.18   This version is useful for decoding alternant codes using Sugiyama's algorithm. However, this goes beyond the scope of this book. For more details, see Roman [Rom], page 399.