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?
Answer
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$.
No comments:
Post a Comment