Prove that the Euclidean algorithm for gcd works with polynomials Given the algorithm $E$:
E(a(x), b(x))
    if b(x) = 0
        return a(x)

    return E(b(x), r(x)) // r(x) comes from the equation
                            a(x) = b(x)q(x) + r(x)

prove that $E(a(x), b(x))=gcd(a(x),b(x))$.
I think using the definition of polynomial gcd is the right approach:

$d(x)$ is called a gcd of $f(x)$ and $g(x)$ if (i) $d(x)$ divides both $f(x)$ and $g(x)$, and (ii) for any polynomial $c(x)$ such that $c(x)$ divides both $f(x)$ and $g(x)$, we have that $c(x)$ divides $d(x)$. (adapted from https://math.stackexchange.com/a/348672/97319)

but I don't know how to prove that the algorithm satisfies this.
 A: It has to be polynomials over a field since the leading coefficients of each polynomial in the sequence $b(x),r_1(x),r_2(x),...$ (where $r_i(x)$ are the remainders produced by the steps in the algorithm) have to be invertible in order to have the degrees of the polynomials in the sequence strictly decreasing so that the algorithm terminates in finitely many steps. In that case the algorithm will terminate in at most $\deg\left(b(x)\right)+1$ steps.
Now, to see that the algorithm produces $\gcd(a(x),b(x))$ we first have to see that
$$
r_n(x)=\mbox{'the last non-zero remainder'}
$$
is in fact a common divisor of $a(x)$ and $b(x)$. Working backwards in the algorithm we have $r_n(x)$ dividing $r_{n-1}(x)$ since the next remainder is zero. Then $r_{n-1}(x)$ divides $r_{n-2}(x)$ except having the remainder $r_n(x)$:
$$
r_{n-2}(x)=q_n(x)\cdot r_{n-1}(x)+r_n(x)
$$
and since $r_n(x)$ divides the right hand side above, it divides $r_{n-2}(x)$ as well. Continuing backwards in this manner we eventually see that $r_n(x)$ divides both $b(x)$ and $a(x)$.
What is left to show is that $r_n(x)$ is a greatest common divisor. So assume $c(x)$ divides both $a(x)$ and $b(x)$. But then $c(x)$ divides
$$
a(x)-q_1(x)\cdot b(x)=r_1(x)
$$
too, since it divides each term of the left hand side. Applying this reasoning in each step of the algorithm we eventually see that $c(x)$ has to divide $r_n(x)$. We are done.
