Sunday, 18 August 2013

Euclidean algorithm for polynomials over a field

Euclidean algorithm for polynomials over a field

Let $f$ and $g$ be polynomials in $F[X]$, with $F$ a field and let $d(X)$
be their $gcd$. Euclid's algorithm constructs polynomials $a(X),b(X)$ such
that: $$a(X)f(X)+b(X)g(X)=d(X);\quad\deg(a)<\deg(g);\quad\deg(b)<\deg(f)$$
I can undestand how the algorithm works. My problem concerns with the
second part of the statement, the one related to degrees. For example i
can't prove $\deg(a)<\deg(g)$.
My book says: let $af+bg=d$. If $\deg(a)\geq\deg(g)$, write $a=gq+r$ with
$\deg(r)<\deg(g)$, then $$rf+(b+qf)g=d$$ and $b+qf$ automatically has
degree less than $f$. I can't understand this last statement:
...automatically has degree less than $f$, why?

No comments:

Post a Comment