Algorithmic Mathematics

Exercise 5.4. Consider the statements below, where the variables m and n are assumed to have integer values, with n > 0, and let W denote the while-loop in these statements. Q:=m; b:=n; CE=0; while b>0 do if 2b then a:=2a; :=b/2; else Cc+a; b:=b-1; fi; od; (a) Prove that ab+c=mn is a loop invariant for w. b odd separately.) (b) Why must w terminate? Why must b = 0 on this termination? (c) Show that on the termination of W, we have that c = mn. (d) Is this approach to computing mn faster or slower than the approach in the previous problem? Justify your answer. Exercise 5.5. Prove that the algorithm GCD is correct. Exercise 5.6. Apply the algorithm GCD, to determine the greatest common divisor of 11468 and 5551. Exercise 5.7. Let F=Z/(3), and let c= 23+2r2 +r+2 and d=2x2+1 be polynomials in F[z]. Apply the algorithm ExtendedGCD to determine g, s,t F[z], such that g is a god of c and d, and 9 = 8c +td