A min-max theorem for the greatest common divisor

THEOREM. For every choice of integers a,b that are not both zero, we have

max{d: d|a and d|b} = min{ax+by: x,y are integers and ax+by>0}.

Proof. The inequality max<=min follows from the fact that

if d|a and d|b and if x,y are integers, then d|(ax+by).
To prove the inequality max>=min, we shall find integers d,x,y such that d|a, d|b, d>0, and d=ax+by; for this purpose, we may assume (since we may switch a and b and since we may change their signs) that a>=b>=0. The following algorithm maintains the loop invariant since each di other than d0,d1 that it constructs is nonnegative and less than di-1, the algorithm terminates. Hence it returns the desired d,x,y.
   d0=a, d1=b;
   x0=1, x1=0;
   y0=0, y1=1;
   i = 1;
   while di >0
   do    i = i+1;
         q = floor of di-2/di-1;
         di = di-2 -qdi-1;
         xi = xi-2 -qxi-1;
         yi = yi-2 -qyi-1;
   return (di-1, xi-1, yi-1);

This algorithm is known as the extended Euclidean algorithm.

Back to the table of contents of Vašek Chvátal's course notes