**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

`d|a`

and `d|b`

and if `x,y`

are integers,
then `d|(ax+by)`

.
`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`

and_{i-1}`d|d`

, then_{i}`d|a`

and`d|b`

, `d`

and_{i-1}=ax_{i-1}+by_{i-1}`d`

;_{i}=ax_{i}+by_{i}

`d`_{i}

other than
`d`_{0},d_{1}

that it
constructs is nonnegative and less than `d`_{i-1}

,
the algorithm terminates. Hence it returns the desired `d,x,y`

.
dThis algorithm is known as the_{0}=a, d_{1}=b; x_{0}=1, x_{1}=0; y_{0}=0, y_{1}=1; i = 1;whiled_{i}>0doi = 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};endreturn (d_{i-1}, x_{i-1}, y_{i-1});

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