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 $\langle a,b\rangle =\{ax+by~|~x,y\in \mathbb {Z} \}$ (set of all linear combinations of $a$ and $b$ over all integers.

If $\langle a,b\rangle$ contains $c,d$, then $\langle c,d\rangle \subseteq \langle a,b\rangle$

Lemma 1: If $b\neq 0$, then $\langle a,b\rangle =\langle b,a\!\!\!\mod {b}\rangle$

Proof: The set $\langle a,b\rangle$ contains the remainer $r=a\!\!\!\mod {b}$, since $r=a-qb$, where the quotient $q=\lfloor {\tfrac {a}{b}}\rfloor$. Thus if $b\neq 0$, then $\langle b,a\!\!\!\mod {b}\rangle \subseteq \langle a,b\rangle$.

On the other hand, $a\in \langle b,a\mod {b}\rangle$ since $a=qb+r=qb+1\cdot (a\!\!\!\mod {b})$. Therefore by antisymmetry, $\langle a,b\rangle =\langle b,a\!\!\!\mod {b}\rangle$.

Q.E.D.

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

Since $g\in \langle a,b\rangle$, 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.