a. Consider the ordinary "paper and pencil" algorithm for long division: dividing a by b, which yields a quotient q and remainder r. Show that this method requires O((1 + lg q) lg b) bit operations.

b. Define µ(a, b) = (1 + lg a)(1 + lg b). Show that the number of bit operations performed by EUCLID in reducing the problem of computing gcd(a, b) to that of computing gcd (b, a mod b) is at most c(µ (a, b) − µ (b, a mod b)) for some sufficiently large constant c > 0.

c. Show that EUCLID.a, b) requires O(µ (a, b)) bit operations in general and O(β²) bit operations when applied to two β-bit inputs.