Euclidean algorithm for polynomials

Let f $($x$)$ and g$($x$)$ be polynomials over F for which

deg$($f $($x$))>=$ deg$($g$($x$))>=1.$

Use the division algorithm for polynomials to compute polynomials

qi$($x$)$ and ri$($x$)$ as follows.

f $($x$)=$ q$1($x$)$g$($x$)+$ r$1($x$),$ degr$1($x$)<$ deg$($g$($x$)).$ If r$1($x$)6=0,$ then

g$($x$)=$ q$2$r$1($x$)+$ r$2($x$),$ degr$2($x$)<$ deg$($g$($x$)).$ If r$2($x$)6=0,$ then

r$1($x$)=$ q$3($x$)$r$2($x$)+$ r$3($x$),$ degr$3($x$)<$ deg$($r$2($x$)).$ If r$3($x$)6=0,$ then

r$2($x$)=$ q$4($x$)$r$3($x$)+$ r$4($x$),$ degr$4($x$)<$ deg$($r$3($x$)).$ If r$4($x$)6=0,$ then

$...$

rj $($x$)=$ qj$+2($x$)$rj$+1($x$)+$ rj$+2($x$),$ degrj$+2($x$)<$ deg$($rj$+1($x$)).$ If rj$+2($x$)=0,$

rj $($x$)=$ qj$+2($x$)$rj$+1($x$)+0.$

Show that rj$+1($x$)=$ gcd$($f $($x$),$ g$($x$)).$ Then use these equations to ob$-$

tain polynomials a$($x$)$ and b$($x$)$ for which rj$+1($x$)=$ a$($x$)$f $($x$)+$b$($x$)$g$($x$).$

The case where $1$ is the gcd of f $($x$)$ and g$($x$)$ is especially useful.