## The extended Euclidean algorithm

Extended Euclidean Algorithm for for

(a)
let

(b)
let

(c)
Repeat:
• let ,
• let ,
• let ,
while

(d)
let , ,

(e)
return .

Example 1.4.7   Let , . We have

since . We have

since . We have

We have

We have

We have

and we must now stop since . We have and .

Example 1.4.8   Lissa needed extra cash to pay for her college books and decided to sell some of her CD's. She divided them into two groups: she would charge $29.00 for those in the A-group and only$18.00 for those in the B-group. She collected a total of \$289.00. How many CD's in each group did she sell?

Solution: The linear equation to be solved is: , where is the number of CD's in the A-group and is the number of CD's in the B-group. Since , Theorem 1.4.4 guarantees us a solution.

Let , , . We proceed as above to obtain:

We stop here since , and note that this calculation has given us , , . Therefore, and . That is, a particular solution to the linear equation is and . By Theorem 1.4.4, all solutions are given by:

where is any integer. To solve the above problem, we must find an integer which gives nonnegative values for and . In other words, we wish to find such that , . It turns out that the only value of which satisfies these inequalities is , which makes and .

david joyner 2008-04-20