Art of Computer Programming, The: Volume 1: Fundamental Algorithms, 3rd Edition

Answers to Exercises

I am not bound to please thee with my answers.

— SHYLOCK, in The Merchant of Venice (Act IV, Scene 1, Line 65)

Notes on the Exercises

1. An average problem for a mathematically inclined reader.

2. They help you to lodge ideas in your brain.

4. See W. J. LeVeque, Topics in Number Theory 2 (Reading, Mass.: Addison–Wesley, 1956), Chapter 3; P. Ribenboim, 13 Lectures on Fermat’s Last Theorem (New York: Springer-Verlag, 1979); A. Wiles, Annals of Mathematics (2) 141 (1995), 443–551.

Section 1.1

1. t ← a, a ← b, b ← c, c ← d, d ← t.

2. After the first time, the values of the variables m and n are the previous values of n and r, respectively; and n > r.

3. Algorithm F (Euclid’s algorithm). Given two positive integers m and ...