Algorithmic Mathematics

Exercise 5.13. The Euler's o-function is defined on the positive integers, as follows: 6(1) = 1; for m > 1, o(m) is the number of invertible elements in Z/(m). Write the algorithm to the following specifications: Algorithm Phi INPUT: m, a positive integer. OUTPUT: 0(m). Exercise 5.14. Consider the recursive algorithm Algorithm A INPUT: r e Z, > 0 OUTPUT: ?? if r=1 then return 1; else return A(x - 1)/2; fi; end; (a) Compute A(5). (6) Explain in one sentence what this algorithm does. [X] Exercise 5.15. Consider the recursive algorithm Algorithm B INPUT: r EZ, 1 > 0 OUTPUT: ?? ifr=1 then return 1; else return 22 + Bx - 1); fi; end; (a) Trace B(5). (6) Explain in one sentence what this algorithm does. [%]