2

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 understand 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?

user26857
  • 52,094
bateman
  • 4,000

1 Answers1

3

First of all, assume neither $f$ nor $g$ are constant (they are nonzero by assumption, since we are talking about their degrees), otherwise the claim is either trivial, or even not true if both are constant.

The degree of $r f$ is less than $\deg(g)+\deg(f)$. If $\deg(b + q f) \ge \deg(f)$, there's no way for the leading term of $(b + q f) g$, which then has degree at least $\deg(f)+\deg(g)$, to cancel out with a term of $r f$ to give you $d$, which has degree at most $\max(\deg(f), \deg(g)) < \deg(f)+\deg(g)$ (recall that neither $f$ nor $g$ have degree $0$).

user26857
  • 52,094
Andreas Caranti
  • 68,873