A min-max theorem for the gcd

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

if d|d_i-1 and d|d_i, then d|a and d|b,
d_i-1=ax_i-1+by_i-1 and d_i=ax_i+by_i;

since each d_i other than d₀,d₁ that it constructs is nonnegative and less than d_i-1, the algorithm terminates. Hence it returns the desired d,x,y.

   d₀=a, d₁=b;
   x₀=1, x₁=0;
   y₀=0, y₁=1;
   i = 1;
   while d_i >0
   do    i = i+1;
         q = floor of d_i-2/d_i-1;
         d_i = d_i-2 -qd_i-1;
         x_i = x_i-2 -qx_i-1;
         y_i = y_i-2 -qy_i-1;
   end    
   return (d_i-1, x_i-1, y_i-1);

This algorithm is known as the extended Euclidean algorithm.

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