Euclid's algorithm (idea)

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:

qi  ri    xi   yi
    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₀ and r₁ are b and c, in order of decreasing magnitude