The greatest common divisor of two positive integers can be found by an algorithm that use...

The greatest common divisor of two positive integers can be found by an algorithm that uses only subtractions, parity checks, and shifts of binary expansions, without using any divisions. The algorithm proceeds recursively using the following reduction:

(Note: Reverse the roles of a and b when necessary.) Exercises refer to this algorithm.

Show that to find (a, b) this algorithm uses the subtraction step in the reduction no more than 1 + [log2 max (a, b)] times.