If you look closely at the variables`a1` and`b1`, you can notice that they take exactly the same values as in the iterative version of the normal[Euclidean algorithm](euclid-algorithm.md). So the algorithm will at least compute the correct GCD.

If you look closely at the variables`a1` and`b1`, you can notice that they take exactly the same values as in the iterative version of the normal[Euclidean algorithm](euclid-algorithm.md#implementation). So the algorithm will at least compute the correct GCD.

To see why the algorithm computes the correct coefficients, consider that the following invariants hold at any given time (before the while loop begins and at the end of each iteration):