Extended Euclidean Algorithm

Extended Euclidean Algorithm for for .

(a)
let

(b)
let

(c)
Repeat:
• let ,
• let ,
• let ,
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.23   Use the extended Euclidean algorithm to find the gcd of and in . Also, find such that

Exercise 2.2.24   Use the extended Euclidean algorithm to find the gcd of and in . Also, find such that

Exercise 2.2.25   Use the extended Euclidean algorithm to find the gcd of and in . Also, find such that

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.32   Let in , where .

(a) Let . Find satisfying Lemma 2.2.5.

(b) Find all roots of in .

Exercise 2.2.33   Let in , where .

(a) Let . Find satisfying Lemma 2.2.5.

(b) Find all roots of in .

Exercise 2.2.34   Let in , where .

(a) Let . Find satisfying Lemma 2.2.5.

(b) Find all roots of in .

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

Exercise 2.2.40   Use the reformulated'' Euclidean algorithm to compute the gcd of and in and such that

david joyner 2008-04-20