We take our pair of integers, and generate a new pair, and from the new pair generate another, and so on until one member of the pair is zero. If the input numbers are m(1) and n(1) with m(1) > n(1), the algorithm is:
m(i+1) = n(i) n(i+1) = m(i) mod n(i)After a few iterations, one of the n becomes zero, and the common factor that we seek is the corresponding m. If this common factor is 1, then the original numbers were coprime.
For example, to discover the common factor of 102 and 54 we generate this sequence:
102 54 54 48 48 6 6 0so that the common factor is 6.