I need help with all questions from a to d.

Consider the following version of the Euclidean algorithm to compute ged(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. (a) Carry out this algorithm to compute gcd(19,2) (b) It seems that in step (2), we ignored the case when both a and b are even. Show that this never occurs (c) Show that the modified Euclidean algorithm always terminates with the right answer (d) Show that this algorithm, when applied to two 100-digit integers, does not take more than 1500 iterations