CSCE 222 Lecture 33

« previous | Wednesday, April 27, 2011 | next »

Extended Euclidean Algorithm

Find the greatest common devisor for two nonnegative, different integers $a$ and $b$:

def euclidean a, b
  while (b != 0) do
    a, b = b, a%b
  end
  return a
end

Proving Algorithm Correctness

Find an invariant of the loop (a property that holds through each iteration). This invariant and $b=0$ should imply that the result is the GCD of $a$ and $b$.

Let $⟨a,b⟩=\{ax+by|x,y\in \mathbb{\mathbb{Z}}\}$ (set of all linear combinations of $a$ and $b$ over all integers.

If $⟨a,b⟩$ contains $c,d$, then $⟨c,d⟩\subseteq ⟨a,b⟩$

Lemma 1: If $b\ne 0$, then $⟨a,b⟩=⟨b,amodb⟩$

Proof: The set $⟨a,b⟩$ contains the remainer $r=amodb$, since $r=a-qb$, where the quotient $q=\lfloor \frac{a}{b}\rfloor$. Thus if $b\ne 0$, then $⟨b,amodb⟩\subseteq ⟨a,b⟩$.

On the other hand,

$a\in ⟨b,amodb⟩$

since

$a=qb+r=qb+1\cdot (amodb)$

. Therefore by antisymmetry,

$⟨a,b⟩=⟨b,amodb⟩$

.

Q.E.D.

Suppose that the algorithm returns the value $g$. By Lemma 1, $⟨a,b⟩=⟨g,0⟩$ (where $⟨g,0⟩$ contains all multiples of $g$). Therefore $g$ is a divisor of $a$ and $b$.

Since $g\in ⟨a,b⟩$, we can find the integers $x$ and $y$ such that $g=ax+by$.

Therefore, each common divisor of

$a$

and

$b$

divides

$g$

, hence

$g$

is the greatest common divisor of

$a$

and

$b$

.

Q.E.D.