4.16 The purpose of this problem is to set an upper bound on the number of iterations of the Euclidean algorithm. a. Suppose that m = qn + r with q > 0 and 0 <= r < n. Show that m/2 > r. b. Let At be the value of A in the Euclidean algorithm after the ith iteration. Show that Show that if m, n, and N are integers with with 1 <=m, n, <=2N, then the Euclidean algorithm takes at most 2N steps to find gcd(m, n). | |
| View Solution | |
| << Back | Next >> |