# Euclids Algorithm for polynomials and a greatest common divisor

I have question about a problem I've encountered while attempting to solve an exercise (it's from an exercise in a homework series).

Suppose we have two polynomials $f$ and $g$ (presumably over the reals, although the field over which these polynomials are defined isn't mentioned explicitly). Assume that deg($g$) > 1. Then there exist polynomals $q_1,r_1$ such that $f = q_1 g + r_1$. We can now repeat the polynomial divison, which gives $g = q_2 r_1 + r_2$ for polynomials $q_3,r_3$ and $r_1 = q_4 r_2 + r_4$ for polynomials $q_4,r_4$, etcetera. At some point we get $r_{p-2} = q_{p}r_{p-1} + r_p$ and $r_{p-1} = q_{p+1} r_p$. I now want to show that $r_p$ is the greatest common divisor of $f$ and $g$.

I have already showed (I think) that $r_p$ divides both $f$ and $g$ by writing the equations in matrixform, giving $$\left(\begin{array}{c}f\\g\end{array}\right) = \Pi_{i=1}^{p+2}\left(\begin{array}{cc} q_{i} & 1 \\ 1 & 0 \end{array}\right) \left(\begin{array}{c}r_p\\0\end{array}\right)$$ But now I want to show that $r_p$ is the greatest divisor. I think the best way to do it is to assume that there is some $\tilde{r}_p$ which also divides $f$ and $g$ but which has a degree larger than $r_p$. At this moment I'm not sure how to proceed (I'm a bit rusty on my abstract algebra). I feel that the solution is obvious but I'm not seeing it. How is this sort of problem best handled?

Those matrices are all invertible, which means that $r_p$ is a combination of $f$ and $g$. Hence every divisor of $f$ and $g$ also divides $r_p$.

• Ugh... I suck. I almost want to delete my question but that wouldn't be fair to you. – Stijn May 18 '11 at 13:29
• @Stijn, +1 for the matrix formulation, which is my favorite. BTW, this argument works for any euclidean domain. – lhf May 18 '11 at 13:32
• @Stijn: don't worry about it. simple things aren't necessarily obvious. Just learn the idea for the future. – Mitch May 18 '11 at 16:00

That $\rm\:r_p\:$ is a greatest common divisor, i.e. that it is divisible by every common divisor $\rm\:d\:$ of $\rm\:f,g\:$, follows immediately from the fact that, by construction, it is an $\rm\:\mathbb R[x]$-linear combination of $\rm\:f,g\:,\$ i.e. for some $\rm\: h,k\in \mathbb R[x]\:,\:$ we have $\rm\ r_p =\: h\ f + k\ g\:,\$ so if $\rm\ d\:|\:f,g\$ then $\rm\ d\ |\ h\ f + k\ g = r_p\:,\$ i.e. more explicitly $\rm\ f/d,\:g/d\in\mathbb R[x]\ \Rightarrow\ (h\ f + k\ g)/d = h\: (f/d) + k\: (g/d)\in \mathbb R[x]\:.$

That $\rm\:r_p\:$ is in fact such a linear combination is easy to prove inductively. The base case is trivially true, i.e. both $\rm\:r_{-1} = f\:$ and $\rm\: r_0 = g\:$ are trivially linear combinations of $\rm\:f,\:g\:.\:$ Suppose, as inductive hypothesis, for all $\rm\:k\le i\:$ that $\rm\:r_k\:$ is a linear combination of $\rm\:f,\:g\:.\:$ Then so to is $\rm\ r_{i+i} = r_{i-1} - q_i\ r_i\:$ since $\rm\:\mathbb R[x]$-linear combinations of $\rm\ f,\:g\$ are preserved under multiplication by elements of $\rm\:\mathbb R[x]\$ (here $\rm\:q_i\:$), and they are also preserved under subtraction. Thus the inductive proof is complete.

If you know about ideals, then the above inductive proof may be interpreted as saying that each step of the Euclidean algorithm simply changes the basis of the ideal, so preserves the ideal, i.e.

$$\rm\:I_{\:i+1} =\: (r_{i+1},\:r_i)\ =\ (r_{i-1}-q_i\ r_i,\:r_i)\ =\ (r_{i-1},\:r_i)\: =\ I_{\:i}$$

So $\rm\ I_i = I_0 = (f,g)\ \Rightarrow\ r_i\in I_i = (f,g) = f\ \mathbb R[x]+g\ \mathbb R[x] = \mathbb R[x]$-linear combinations of $\rm\:f,g\:.$

Generally in any Bezout domain, i.e. any domain where finitely generated ideals are principal, the gcd is given by any generator of an equivalent principal ideal, i.e.

$$\rm (a,b)\ = (c)\ \ \iff\ \ gcd(a,b)\ =\ c$$

$\$ since $\rm\quad\quad\quad\ (a,b)\ =\ (c)$

$\rm\quad\quad\quad \iff\ [\ (d)\supset (a,b)\ \iff\ (d)\supset (c)\ ]$

$\rm\quad\quad\quad \iff\ [\ d\ |\ a,\:b\ \iff\ d\ |\ c \ ]$

$\rm\quad\quad\quad \iff\ gcd(a,b)\ =\ c$