8. Here we look at an alternative algorithm based on divide-and-conquer. if a, b are even if a is odd, b is even 2 gcd(a/2, b/2) gcd (a, b)gcd(a, b/2) gcd((a b)/2, b)if a, b are odd Show this rule is true. (b) Give an efficient divide-and-conquer algorithm for finding greatest common divisor. (c) How does the efficiency of your algorithm compare to Euclid's algorithm if a and b are n-bit integers? (In particular, since n might be large you cannot assume that basic arithmetic operations like addition take constant time.)