071 Intermediate

071 — GCD and LCM

Functional Programming

Tutorial

The Problem

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are among the most ancient and practical algorithms in mathematics. Euclid's algorithm for GCD (circa 300 BC) is one of the oldest known algorithms: gcd(a, 0) = a and gcd(a, b) = gcd(b, a mod b). Each recursive call replaces the larger argument with the remainder, which strictly decreases, guaranteeing termination in O(log min(a, b)) steps. LCM follows from GCD: lcm(a, b) = a * b / gcd(a, b).

GCD and LCM appear throughout computer science and mathematics: fraction simplification divides numerator and denominator by their GCD; synchronized clocks or processes that fire every p and q cycles next coincide at lcm(p, q) steps; hash table designers choose prime or coprime sizes to minimize clustering; RSA key generation verifies that the public exponent e is coprime to φ(n) using GCD; and musical tuning theory uses LCM to find the first beat where two rhythms re-align. Understanding Euclid's algorithm deeply is understanding the division algorithm — the foundation of modular arithmetic.

🎯 Learning Outcomes

• Implement Euclidean GCD recursively and iteratively, understanding the termination proof

• Derive LCM from GCD using the safe form a / gcd(a, b) * b (dividing first avoids overflow)

• Extend GCD to lists using reduce: gcd_list(v) = v.iter().copied().reduce(gcd)

• Understand the loop invariant: a % b < b strictly decreases, guaranteeing termination

• Recognize that GCD is associative, making it composable with fold and reduce

• Connect to Bezout's identity and the extended Euclidean algorithm used in cryptography

Code Example

#![allow(clippy::all)]
// 071: GCD and LCM

// Approach 1: Recursive GCD (Euclidean)
fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a.abs()
    } else {
        gcd(b, a % b)
    }
}

fn lcm(a: i64, b: i64) -> i64 {
    if a == 0 || b == 0 {
        0
    } else {
        (a * b).abs() / gcd(a, b)
    }
}

// Approach 2: Iterative GCD
fn gcd_iter(mut a: i64, mut b: i64) -> i64 {
    a = a.abs();
    b = b.abs();
    while b != 0 {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}

// GCD/LCM of a slice
fn gcd_list(v: &[i64]) -> i64 {
    v.iter().copied().reduce(gcd).unwrap_or(0)
}

fn lcm_list(v: &[i64]) -> i64 {
    v.iter().copied().reduce(lcm).unwrap_or(1)
}

// Approach 3: Extended GCD
fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    if b == 0 {
        (a, 1, 0)
    } else {
        let (g, x, y) = extended_gcd(b, a % b);
        (g, y, x - (a / b) * y)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_gcd() {
        assert_eq!(gcd(12, 8), 4);
        assert_eq!(gcd(17, 5), 1);
        assert_eq!(gcd(0, 5), 5);
        assert_eq!(gcd(100, 0), 100);
    }

    #[test]
    fn test_lcm() {
        assert_eq!(lcm(4, 6), 12);
        assert_eq!(lcm(3, 5), 15);
        assert_eq!(lcm(0, 5), 0);
    }

    #[test]
    fn test_gcd_iter() {
        assert_eq!(gcd_iter(12, 8), 4);
        assert_eq!(gcd_iter(-12, 8), 4);
    }

    #[test]
    fn test_list_ops() {
        assert_eq!(gcd_list(&[12, 18, 24]), 6);
        assert_eq!(lcm_list(&[4, 6, 8]), 24);
    }

    #[test]
    fn test_extended_gcd() {
        let (g, x, y) = extended_gcd(35, 15);
        assert_eq!(g, 5);
        assert_eq!(35 * x + 15 * y, 5);
    }
}

(* 071: GCD and LCM *)

(* Approach 1: Recursive GCD *)
let rec gcd a b =
  if b = 0 then abs a
  else gcd b (a mod b)

let lcm a b =
  if a = 0 || b = 0 then 0
  else abs (a * b) / gcd a b

(* Approach 2: GCD of a list *)
let gcd_list = function
  | [] -> 0
  | x :: xs -> List.fold_left gcd x xs

let lcm_list = function
  | [] -> 1
  | x :: xs -> List.fold_left lcm x xs

(* Approach 3: Extended GCD — returns (g, x, y) where ax + by = g *)
let rec extended_gcd a b =
  if b = 0 then (a, 1, 0)
  else
    let g, x, y = extended_gcd b (a mod b) in
    (g, y, x - (a / b) * y)

(* Tests *)
let () =
  assert (gcd 12 8 = 4);
  assert (gcd 17 5 = 1);
  assert (gcd 0 5 = 5);
  assert (gcd 100 0 = 100);
  assert (lcm 4 6 = 12);
  assert (lcm 3 5 = 15);
  assert (lcm 0 5 = 0);
  assert (gcd_list [12; 18; 24] = 6);
  assert (lcm_list [4; 6; 8] = 24);
  let (g, x, y) = extended_gcd 35 15 in
  assert (g = 5);
  assert (35 * x + 15 * y = 5);
  Printf.printf "✓ All tests passed\n"

Key Differences

Recursive vs iterative: OCaml guarantees TCO for the tail-recursive Euclidean GCD. Rust's recursive version may overflow the stack for very large inputs (though GCD terminates in O(log min(a,b)) steps, making stack overflow unlikely in practice).

Signed vs unsigned: This implementation uses u64. For signed integers, absolute values must be taken first: a.abs() and b.abs(). OCaml's default integers are signed.

**reduce vs fold_left**: Rust's reduce does not need an identity element — it uses the first element. OCaml's fold_left gcd 0 lst works because gcd(0, x) = x (0 is the identity for GCD). Both are equivalent.

Overflow in LCM: a * b overflows u64 for a, b > 2^32. The a / gcd(a,b) * b form avoids this if a is divisible by gcd(a,b) (which it always is by definition).

OCaml Approach

OCaml's Euclidean GCD is a direct tail-recursive definition:

let rec gcd a b = if b = 0 then a else gcd b (a mod b)
let lcm a b = if a = 0 || b = 0 then 0 else a / gcd a b * b

For a list: List.fold_left gcd 0 lst exploits the identity gcd(0, x) = x. OCaml's arbitrary-precision integers (Zarith library) avoid all overflow in LCM computation for very large inputs. The standard library includes Int.gcd since OCaml 4.14.

Full Source

#![allow(clippy::all)]
// 071: GCD and LCM

// Approach 1: Recursive GCD (Euclidean)
fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a.abs()
    } else {
        gcd(b, a % b)
    }
}

fn lcm(a: i64, b: i64) -> i64 {
    if a == 0 || b == 0 {
        0
    } else {
        (a * b).abs() / gcd(a, b)
    }
}

// Approach 2: Iterative GCD
fn gcd_iter(mut a: i64, mut b: i64) -> i64 {
    a = a.abs();
    b = b.abs();
    while b != 0 {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}

// GCD/LCM of a slice
fn gcd_list(v: &[i64]) -> i64 {
    v.iter().copied().reduce(gcd).unwrap_or(0)
}

fn lcm_list(v: &[i64]) -> i64 {
    v.iter().copied().reduce(lcm).unwrap_or(1)
}

// Approach 3: Extended GCD
fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    if b == 0 {
        (a, 1, 0)
    } else {
        let (g, x, y) = extended_gcd(b, a % b);
        (g, y, x - (a / b) * y)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_gcd() {
        assert_eq!(gcd(12, 8), 4);
        assert_eq!(gcd(17, 5), 1);
        assert_eq!(gcd(0, 5), 5);
        assert_eq!(gcd(100, 0), 100);
    }

    #[test]
    fn test_lcm() {
        assert_eq!(lcm(4, 6), 12);
        assert_eq!(lcm(3, 5), 15);
        assert_eq!(lcm(0, 5), 0);
    }

    #[test]
    fn test_gcd_iter() {
        assert_eq!(gcd_iter(12, 8), 4);
        assert_eq!(gcd_iter(-12, 8), 4);
    }

    #[test]
    fn test_list_ops() {
        assert_eq!(gcd_list(&[12, 18, 24]), 6);
        assert_eq!(lcm_list(&[4, 6, 8]), 24);
    }

    #[test]
    fn test_extended_gcd() {
        let (g, x, y) = extended_gcd(35, 15);
        assert_eq!(g, 5);
        assert_eq!(35 * x + 15 * y, 5);
    }
}

(* 071: GCD and LCM *)

(* Approach 1: Recursive GCD *)
let rec gcd a b =
  if b = 0 then abs a
  else gcd b (a mod b)

let lcm a b =
  if a = 0 || b = 0 then 0
  else abs (a * b) / gcd a b

(* Approach 2: GCD of a list *)
let gcd_list = function
  | [] -> 0
  | x :: xs -> List.fold_left gcd x xs

let lcm_list = function
  | [] -> 1
  | x :: xs -> List.fold_left lcm x xs

(* Approach 3: Extended GCD — returns (g, x, y) where ax + by = g *)
let rec extended_gcd a b =
  if b = 0 then (a, 1, 0)
  else
    let g, x, y = extended_gcd b (a mod b) in
    (g, y, x - (a / b) * y)

(* Tests *)
let () =
  assert (gcd 12 8 = 4);
  assert (gcd 17 5 = 1);
  assert (gcd 0 5 = 5);
  assert (gcd 100 0 = 100);
  assert (lcm 4 6 = 12);
  assert (lcm 3 5 = 15);
  assert (lcm 0 5 = 0);
  assert (gcd_list [12; 18; 24] = 6);
  assert (lcm_list [4; 6; 8] = 24);
  let (g, x, y) = extended_gcd 35 15 in
  assert (g = 5);
  assert (35 * x + 15 * y = 5);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_gcd() {
        assert_eq!(gcd(12, 8), 4);
        assert_eq!(gcd(17, 5), 1);
        assert_eq!(gcd(0, 5), 5);
        assert_eq!(gcd(100, 0), 100);
    }

    #[test]
    fn test_lcm() {
        assert_eq!(lcm(4, 6), 12);
        assert_eq!(lcm(3, 5), 15);
        assert_eq!(lcm(0, 5), 0);
    }

    #[test]
    fn test_gcd_iter() {
        assert_eq!(gcd_iter(12, 8), 4);
        assert_eq!(gcd_iter(-12, 8), 4);
    }

    #[test]
    fn test_list_ops() {
        assert_eq!(gcd_list(&[12, 18, 24]), 6);
        assert_eq!(lcm_list(&[4, 6, 8]), 24);
    }

    #[test]
    fn test_extended_gcd() {
        let (g, x, y) = extended_gcd(35, 15);
        assert_eq!(g, 5);
        assert_eq!(35 * x + 15 * y, 5);
    }
}

Deep Comparison

Core Insight

The Euclidean algorithm: gcd(a, b) = gcd(b, a mod b) with base case gcd(a, 0) = a. LCM derives from GCD. The recursive structure is identical in both languages.

OCaml Approach

• Recursive function with pattern matching

• Tail-recursive naturally (last call is recursive)

• abs for handling negative inputs

Rust Approach

• Recursive or iterative (loop with swap)

• No guaranteed TCO but small depth for GCD

• Can use .abs() method on integers

Comparison Table

Feature	OCaml	Rust
GCD	`let rec gcd a b = ...`	`fn gcd(a, b) -> ...`
Pattern	`match b with 0 -> a`	`if b == 0 { a }`
LCM	`a * b / gcd a b`	`a * b / gcd(a, b)`
Overflow	No (arbitrary precision with Zarith)	Possible with i32/i64

Exercises

Extended Euclidean: Implement the extended Euclidean algorithm extended_gcd(a, b) -> (i64, i64, i64) returning (gcd, x, y) where ax + by = gcd. Used in modular inverse computation for cryptography.

Modular inverse: Using extended GCD, write mod_inverse(a: i64, m: i64) -> Option<i64> that returns x such that ax ≡ 1 (mod m). Returns None if gcd(a, m) != 1.

Fraction simplification: Write simplify(num: i64, den: i64) -> (i64, i64) that reduces a fraction by dividing both by their GCD.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust