Unbeknownst to some, a couple extra steps let you use to

Euclid's

Algorithm to find not only the

greatest common denominator *g* of two integers

*b* and

*c*, but also the values of

*x* and

*y* for which

*bx* +

*cy* =

*g*. We here utilize the fact that the

gcd of two (or more) numbers is also their smallest positive

linear combination.

A simple demonstration, which you can probably convert into C faster than I can:

`
q`_{i} r_{i} x_{i} y_{i}
71 1 0
1 50 0 1
2 21 1 -1
2 8 -2 3
1 5 5 -7
1 3 -7 10
1 2 12 -17
1 -19 27
gcd(71,50) = 1 = (71)(-19) + (50)(27)

Each row requires four swift calculations:

- q
_{i+1} = Floor(r_{i}/r_{i+1})
- r
_{i+1} = r_{i-1} - q_{i}*r_{i}
- x
_{i+1} = x_{i-1} - q_{i}*x_{i}
- y
_{i+1} = y_{i-1} - q_{i}*y_{i}

Of course, r

_{0} and r

_{1} are b and c, in order of decreasing magnitude