Knuth Art Of Computer Programming V1 p2 ----------------------------------------------------------------------- Algorithm E (Euclid's algorithm). Given two positive integers m and n, find their greatest common divisor, that is, the largest positive integer that evenly divides both m and n.

E1 [Find remained] Divide m by n and r be the remainder. (We will know that 0 <= r < n)

E2 [Is it zero?] If r = 0, the algorithm terminates, n is the answer

E3 [Reduce] Set m = n, then n = r, then go back to step E1

----------------------------------------------------------------------- Knuth Art Of Computer Programming V1 p9 Problem 1.1.4

[4] Using Algorithm E compute the greatest common divisor of 2166 and 6099. Label each step of the algorithm as it is used.

======================================================================== Claude Sonnet 4.6 ========================================================================

Starting with m = 2166, n = 6099: E1: 2166 ÷ 6099 = 0 remainder 2166 → r = 2166 E2: r ≠ 0, continue E3: m = 6099, n = 2166

E1: 6099 ÷ 2166 = 2 remainder 1767 → r = 1767 E2: r ≠ 0, continue E3: m = 2166, n = 1767

E1: 2166 ÷ 1767 = 1 remainder 399 → r = 399 E2: r ≠ 0, continue E3: m = 1767, n = 399

E1: 1767 ÷ 399 = 4 remainder 171 → r = 171 E2: r ≠ 0, continue E3: m = 399, n = 171

E1: 399 ÷ 171 = 2 remainder 57 → r = 57 E2: r ≠ 0, continue E3: m = 171, n = 57

E1: 171 ÷ 57 = 3 remainder 0 → r = 0 E2: r = 0, algorithm terminates GCD(2166, 6099) = 57