**Extended Euclidean Algorithm**
for
for
.

- (a)
- let

- (b)
- let

- (c)
- Repeat:
while

- (d)
- let
,
,

- (e)
- return
.

The repeat loop in step (c) means to continue
every step until you see
.
This algorithm does not always yield a monic
polynomial for
(the gcd is always
monic), so it doesn't always yield the correct
answer. However, the polynomial
it
produces is a constant times the correct
gcd.

**Example 2.2.19**
*Let
,
, so
.
We have
*

*
since
. We have
*

*
since
.
We have
*

*
since
. We have
*

*
We can stop now since
. We read off
,
,
(which must be multiplied by
to make it monic).
*

**Exercise 2.2.20**
*Let
denote the field having
elements
and let
.
Show that for all
,
.
(Hint: Use Fermat's Little Theorem.)*

**Exercise 2.2.21**
*Let
be a field and let
denote the set of all
rational functions (i.e., expressions of the
form
where
and
).
Show that
is a field.*

**Exercise 2.2.22**
*Let
and let
, so
.
Use the interpolation formula to find a polynomial
representation of
.*

**Exercise 2.2.26**
*Show that
has no roots in
. *

**Exercise 2.2.27**
*Show that
has no roots in
. *

**Exercise 2.2.28**
*Show that
has two roots in
(namely,
and
). *

**Exercise 2.2.29**
*Show that
has
roots in
.*

**Exercise 2.2.30**
*Show that
has
roots in
.*

**Exercise 2.2.31**
*Show that
has
roots in
.
(This is a restatement of Fermat's little theorem.)*

**Exercise 2.2.35**
*Use the Euclidean algorithm to compute the gcd of
and
in
.*

**Exercise 2.2.36**
*Use the Euclidean algorithm to compute the gcd of
and
in
.*

**Exercise 2.2.37**
*Use the Euclidean algorithm to compute the gcd of
and
in
.*

**Exercise 2.2.38**
*Prove Theorem 2.2.15.
(Hint: Modify the proof of 1.4.3.)*

**Exercise 2.2.39**
*Carry out each step of the ``reformulated'' Euclidean
algorithm for
and
in
.
Verify
*

david joyner
2008-04-20