Chapter 5.5, Problem 12ES

The following sentence could be added to the loop invariant for the Euclidean algorithm:
There exist integers u, v, s, and t such that $a=uA+vB$ and $b=sA+tB$ . 5.5.12
a. Show that this sentence is a loop invariant for
while $\left(b\ne 0\right)$
$r:=amodb$ $a:=b$ $b:=\text{r}$
end while
b. Show that if initially a = A and b = B, then sentence (5.5.12) is true before the first iteration of the loop.
c. Explain how the correctness proof for the Euclidean algorithm together with the results of (a)
and (b) above allow you to conclude that given any integers A and B with $A>B\ge 0$ , there exist integers u and v so that $\gcd \left(A,B\right)=uA+vB$ .
d. By actually calculating u, v, s, and t at each stage of execution of the Euclidean algorithm, find integers u and v so that $\gcd \left(330,156\right)=330u+156v$ .