Euclid's algorithm finds the greatest common divisor with nothing but repeated remainders - a two-line loop that our Mod makes exact at any size. Today you add Gcd.
Compute the greatest common divisor of two BigInts by the Euclidean algorithm.
Euclid’s insight, twenty-three centuries old, is that the greatest common divisor of
a and b equals the GCD of b and a mod b - so you keep replacing the pair with
(b, a mod b) until the second number hits zero, and the first is your answer. Our
non-negative Mod drives it directly; work with the absolute values so the result
is a clean non-negative divisor regardless of the inputs’ signs.
The terminating case, Gcd(x, 0) == |x|, is the loop’s natural base: when b is
already zero the loop never runs and returns |a|. This is a small function, but it
leans on the entire division chapter, and it runs just as happily on
Gcd(10^18, 12) == 4 as on the small textbook pair. With comparison, the four
arithmetic operations, exponentiation, and GCD all in place, the library is ready for
its capstone.
func Gcd(x, y BigInt) BigInt {a, b := x.Abs(), y.Abs()for b.sign != 0 {_, r, _ := DivMod(a, b)a, b = b, r // replace the pair with (b, a mod b)}return a}