Consider the following version of the Euclidean algorithm to compute gcd(a, b). Start with computing the largest power of 2 dividing both a and b. If this is 2", then divide a and b by 2". After this "preprocessing", do the following: Step 1: Swap the numbers if necessary to have a s b;
Step 2: If a = 0, then check the parities of a and b; if a is even, and b is odd, then replace a by a/2; if both a and b are odd, then replace b by b - a; in each case, go to step (1);
Step 3: If a = 0, then return 2" b as the greatest common denominator.

Required:
a. Show that the modified Euclidean algorithm always terminates with the right answer.
b. Show that this algorithm, when applied to two 100-digit integers, does not take more than 1500 iterations.