Run Euclid’s algorithm on the inputs to obtain an output . Then for some . From step , is itself expressible as a linear combination of and ; substituting expresses as a linear combination of and . Continuing inductively,

for some and all . In particular

for some . Since the output satisfies , the highest common factor is a linear combination of and — and the computation also produces the coefficients.

Let be the least positive linear combination of and , that is, the smallest positive integer of the form for some . We verify the two conditions in the definition of the highest common factor and conclude .

To show (2), observe that given with and , we have for all ; in particular .

To show (1), suppose that . Then we can write for some with . Hence

is also a positive linear combination of and , contradicting the minimality of . Thus , and similarly .

This argument proves that exists and is a linear combination of and , but it gives no method to compute it.