[Math] Euclidean algorithm in the ring of polynomials over a field

divisibilitypolynomials

I need some help with the following division proofs. I suppose my biggest problem is not being able to visualize the algebra for one GCD equaling another GCD. I'm not sure of how to arrange the variables.

Let $F$ be a field and $f,g,q,r \in F[X]$ with $f$ being nonzero and $g=fq+r$

A. Prove that $d$ is a greatest common divisor of $f$ and $g$ if and only if $d$ is a greatest common divisor of $f$ and $r$.

B. Prove that the last nonzero remainder of Euclid’s Algorithm on $f$ and $g$ is a greatest common divisor of $f$ and $g$.

C. Show that there are polynomials $r,t \in F[X]$ such that $d = rf +tg$

Best Answer

A greatest common divisor of $f$ and $g$ is a polynomial $d$ such that

  1. $d$ divides both $f$ and $g$;
  2. if $e$ is a polynomial that divides both $f$ and $g$, then $e$ divides $d$.

(A) Suppose $d$ is a greatest common divisor of $f$ and $g$; then by (1), we can write $f=df_1$ and $g=dg_1$; therefore $$ r=fq-g=d(f_1q-g_1) $$ and so $d$ satisfies property (1) with respect to $g$ and $q$. Next, suppose $e$ divides both $g$ and $r$: $g=eg_2$, $r=er_2$; then $f=gq+r=e(g_2q+r_2)$, which means that $e$ divides both $f$ and $g$, so by (2) we conclude that $e$ divides $d$. Hence $d$ satisfies also property (2) with respect to $g$ and $r$.

The converse direction is very similar.

(B) At each step of the Euclidean algorithm the greatest common divisor is preserved because of (A). The last step gives a zero remainder, so the divisor is obviously a greatest common divisor of itself and the dividend. But this divisor is exactly the last nonzero remainder.

(C) Traverse the steps in the algorithm.

Related Question