The Euclidean algorithm on the natural numbers N = {0,1,…} can be specified succinctly by the recursive program ε: gcd (a,b) = {b, if rem(a,b) = 0, gcd (b, rem(a,b)), otherwise (a ≥ b ≥ 1), where rem (a,b) is the remainder in the division of a by b, the unique natural number r such that for some natural number q, (1) a = bq + r (0 ≤ r < b).
展开▼
