Euclidean algorithm in the ring of polynomials over a field

Question

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$

Answer 1

For part $(A)$, suppose that $d$ is a gcd of $f$ and $g$ and $d'$ is a gcd of $f$ and $r$. Then $d\mid (g-fq)=r$ because $d\mid g$ and $d\mid f$, so $d\mid d'$ (because $d'$ is a greatest common divisor of $r$ and $f$.) Similarly, $d'\mid (fq+r)=g$ and $d'\mid f$, so $d'\mid d$. Hence, $d'$ and $d$ differ by at most multiplication by a constant polynomial, and so each is a gcd of $g$ and $f$ and $f$ and $r$.

Parts $(B)$ and $(C)$ follow from $(A)$ simply by applying the Euclidean algorithm.

For $(B)$, you just apply $(A)$ at each step of the Euclidean algorithm to get that the last nonzero remainder is also a gcd of $f$ and $g$.

For $(C)$, starting at the last equation you get in the Euclidean algorithm (which will be of the form $g_k=q_kf_k+d$ for some $g_k$, $q_k$, and $f_k$,) take the equation $d=g_k-q_kf_k$ and back-substitute for $g_k$ and $f_k$ with the earlier equations in the Euclidean algorithm to get an equation of the desired form for $(C)$.

Here is an example using the Euclidean algorithm in $\mathbb{Z}$ to demonstrate this: \begin{align*} 5 &= 1\cdot 3+2 \\ 3 &= 1\cdot 2+1, \end{align*} so take $1=3-1\cdot 2$, substitute in $2=5-1\cdot 3$ from the previous equation, and you get $1=3-1\cdot(5-1\cdot 3)=2\cdot 3-1\cdot 5$.

Answer 2

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.

Answer 3

Let's $\mathbb{F}=F[X]$ and $Id(f,g)=\mathbb{F}f + \mathbb{F}g$ the ideal generated by $f$ and $g$. I don't know if you know the definition of the gcd with ideals, so I did proofs with and proof without.

A. "Ideals" : We suppose $f \neq 0$. Since $r=g-fq$, it is clear that $Id(f,r)=\mathbb{F}f + \mathbb{F}r = \mathbb{F}f + \mathbb{F}(g - fq) \subset Id(f,g)$ since its element are linear combination of $f$ and $g$. So $gcd(f,g) \mid gcd(f,r)$. Conversly, $sf + tg \in Id(f,g)$ can be written as $(s-tq+tq)f + tg=s'f - tqf + tg=s'f + t(g - qf)=s'f + tr \in Id(f,r)$ where $s'=s+tq$. So, finally $Id(f,g)=Id(f,r)$ and $gcd(f,g)=gcd(f,r)$.

"Usual" : It is known (and trivial to show) that if $d \mid f,g$ then $d$ divide any linear combination of $f$ and $g$ (I say linear but the coeffecient can be in $\mathbb{F}$), and especially $d \mid r = g -qf$ and so $d \mid f,r$. Conversely, if $d \mid r,f$ then $d \mid g=fq + r$ and finally $\{$ Common divisors of $f$ and $g \} = \{$ Common divisor of $f$ and $r \}$ and it follows that $gcd(f,g)=gcd(f,r)$

B. You can use the usual proof (http://en.wikipedia.org/wiki/Euclidean_algorithm#Proof_of_validity), using the A. lemma instead of the usual one on integers, and it works well.

C. With the definition on ideals, there is nothing to prove, since $gcd(f,g) \in Id(f,g)$.

"Usual" : this is also the same proof than for integers, using Bezout's theorem (which is still valid for polynomials) or Euclide algorithm (that provides with the actual coefficients).