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|di-1` and `d|di`, then `d|a` and `d|b`,
• `di-1=axi-1+byi-1` and `di=axi+byi`;
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;
end
return (di-1, xi-1, yi-1);

```
This algorithm is known as the extended Euclidean algorithm.