The extended Euclidean algorithm

Extended Euclidean Algorithm for $d=\gcd (a,b)=xa+yb$ for $0< b<a.$

(a)

let $\overline{u}= \langle a,1,0\rangle$

(b)

let $\overline{v}= \langle b,0,1\rangle$

(c)

Repeat:

• let $\overline{w}= \overline{u}-\lfloor u_{1}/v_{1}\rfloor \overline{v}$ ,
• let $\overline{u}\leftarrow \overline{v}$ ,
• let $\overline{v}= \overline{w}$ ,

while $v_{1}\neq 0$

(d)

let $d= u_{1}$ , $x= u_{2}$ , $y= u_{3}$

(e)

return $d,x,y$ .

Example 1.4.7   Let $a=331$ , $b=81$ . We have

$$u = [331, 1, 0], v = [81, 0, 1], w = [7, 1, -4],$$

since $[331/81]=4$ . We have

$$u = [81, 0, 1], v = [7, 1, -4], w = [4, -11, 45],$$

since $[81/7]=11$ . We have

$$u = [7, 1, -4], v = [4, -11, 45], w = [3, 12, -49].$$

We have

$$u = [4, -11, 45], v = [3, 12, -49], w = [1, -23, 94].$$

We have

$$u = [3, 12, -49], v = [1, -23, 94], w = [0, 81, -331].$$

We have

$$u = [1, -23, 94], v = [0, 81, -331],$$

and we must now stop since $v_1=0$ . We have $gcd(331,81)=1$ and $331\cdot (-23)+81\cdot 94=1$ .

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: $29x+18y=289$ , where $x$ is the number of CD's in the A-group and $y$ is the number of CD's in the B-group. Since $(29,18)=1$ , Theorem 1.4.4 guarantees us a solution.

Let $u=[29,1,0]$ , $v=[18,0,1]$ , $w=u-[\frac{29}{18}]v=[11,1,-1]$ . We proceed as above to obtain:

$$u=[18,0,1],\quad v=[11,1,-1],\quad,w=[7,-1,2],$$

$$u=[11,-1,1],\quad v=[7,-1,2], \quad w=[4,2,-3],$$

$$u=[7,-1,2],\quad v=[4,2,-3],\quad w=[3,-3,5],$$

$$u=[4,2,-3],\quad v=[3,-3,5],\quad w=[1,5,-8],$$

$$u=[3,-3,5],\quad v=[1,5,-8],\quad w=[0,-18,-13],$$

$$u=[1,5,-8],\quad v=[0,-18,29]$$

We stop here since $v_1=0$ , and note that this calculation has given us $gcd(29,18)=1$ , $x=5$ , $y=-8$ . Therefore, $29(5)+18(-8)=1$ and $29(5 \cdot 289)+18(-8 \cdot 289)=289$ . That is, a particular solution to the linear equation $29x+18y=289$ is $x_0=5 \cdot 289 =1445$ and $y_0=-8 \cdot 289=-2312$ . By Theorem 1.4.4, all solutions are given by:

$$x=1445+18t,\quad y=-2312-29t,$$

where $t$ is any integer. To solve the above problem, we must find an integer $t$ which gives nonnegative values for $x$ and $y$ . In other words, we wish to find $t$ such that $x=1445+18t \geq 0$ , $y=-2312-29t \geq 0$ . It turns out that the only value of $t$ which satisfies these inequalities is $t=-80$ , which makes $x=5$ and $y=8$ .