Skip to main content

Euclid, Termination and Bezout Certificates

What this concept is​

For nonzero input pairs, the greatest common divisor is the greatest positive integer dividing both inputs. We use gcd(a,0)=abs(a) and the programming convention gcd(0,0)=0. Euclid repeatedly replaces (a,b) by (b,a mod b) after normalizing signs. Extended Euclid also returns coefficients x,y with ax+by=gcd(a,b); this identity is a certificate.

Why it matters here​

This is an early example of proving an algorithm: show the answer is preserved and that the process stops. The coefficients later let us compute modular inverses.

Concrete example​

Trace 252 and 198:

252 = 1*198 + 54
198 = 3*54 + 36
54  = 1*36 + 18
36  = 2*18 + 0

The gcd is 18. Back-substitute: 18 = 54 - 36 = 4*54 - 198 = 4*252 - 5*198. Thus x=4,y=-5 is a certificate.

Why is the answer preserved? A common divisor of a,b divides a-qb; conversely a common divisor of b and a-qb divides a. The common-divisor sets are equal. Why terminate? Each nonzero new remainder is smaller than the previous positive divisor; an infinite strictly decreasing sequence of nonnegative integers is impossible.

Common confusion / misconception​

Coefficients are not unique: test the identity, not a particular pair. Normalize signs for the gcd, but adjust coefficients to match the original signed inputs. Termination and correctness are different obligations; a loop can stop with the wrong answer.

How to use it​

Maintain each current remainder as an integer combination of the original inputs. Initialize coefficients for a as (1,0) and for b as (0,1); apply the same quotient update to the coefficients as to the remainders. For negative originals, work on absolute values and correct coefficient signs at the end.

Every two remainder steps reduce the relevant positive remainder by at least half, giving logarithmically many divisions in the input magnitude. This counts arithmetic operations, not constant-time machine work on arbitrarily long integers; bit cost needs a separate model.

Check yourself​

How can you verify a returned (g,x,y)? Check nonnegative g, divisibility of each input by g when g>0, and ax+by=g. Handle the all-zero pair separately. The identity alone would permit a non-gcd multiple.

Mini drill or application​

Trace 84 and 30, obtain a certificate, and repeat with -84 and 30. Explain which parts change and which do not.

Read this only if stuck​

Source backbone: Mathematics for Computer Science reference. For the freely available original, use MIT’s 2015 Chapter 8 readings. See the reading guide for topic selection; chapter numbering can differ across editions.