826 Intermediate

GCD and LCM — Euclidean Algorithm

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "GCD and LCM — Euclidean Algorithm" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. The greatest common divisor (GCD) and least common multiple (LCM) are foundational operations in arithmetic: reducing fractions, synchronizing periodic events, solving linear Diophantine equations, and implementing modular arithmetic all depend on them. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

The greatest common divisor (GCD) and least common multiple (LCM) are foundational operations in arithmetic: reducing fractions, synchronizing periodic events, solving linear Diophantine equations, and implementing modular arithmetic all depend on them. The Euclidean algorithm computes GCD in O(log min(a,b)) — exponentially faster than trial factorization. Extended Euclidean finds Bezout coefficients (x, y such that ax + by = gcd(a,b)), enabling modular inverse computation essential for RSA and other cryptographic operations. These functions appear in virtually every number theory library.

🎯 Learning Outcomes

• Implement the recursive Euclidean algorithm: gcd(a, b) = gcd(b, a % b), base case gcd(a, 0) = a

• Derive LCM from GCD: lcm(a, b) = (a / gcd(a, b)) * b (divide before multiply to avoid overflow)

• Implement the extended Euclidean algorithm returning Bezout coefficients

• Understand the connection: gcd(a,b) = 1 implies a has a modular inverse mod b

• Apply to: fraction reduction, Stern-Brocot tree, continued fractions, CRT

Code Example

#![allow(clippy::all)]
//! # GCD and LCM (Euclidean Algorithm)
pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}
pub fn lcm(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b
}
pub 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(48, 18), 6);
    }
    #[test]
    fn test_lcm() {
        assert_eq!(lcm(4, 6), 12);
    }
}

(* GCD, LCM, and Euclidean Algorithm in OCaml *)

(* The classic one-liner — functional elegance at its finest *)
let rec gcd (a : int) (b : int) : int =
  if b = 0 then a else gcd b (a mod b)

(* LCM via GCD — divide first to avoid overflow *)
let lcm (a : int) (b : int) : int =
  if a = 0 || b = 0 then 0
  else (a / gcd a b) * b

(* GCD of a list — neutral element is 0 since gcd(a,0)=a *)
let list_gcd (xs : int list) : int =
  List.fold_left gcd 0 xs

let list_lcm (xs : int list) : int =
  List.fold_left lcm 1 xs

(* Trace the steps of Euclidean algorithm *)
let gcd_trace (a : int) (b : int) : unit =
  Printf.printf "gcd(%d, %d):\n" a b;
  let a = ref a and b = ref b in
  while !b <> 0 do
    Printf.printf "  gcd(%d, %d) → rem = %d\n" !a !b (!a mod !b);
    let r = !a mod !b in
    a := !b;
    b := r
  done;
  Printf.printf "  = %d\n" !a

(* Binary GCD (Stein's algorithm) — avoids modulo *)
let rec binary_gcd (a : int) (b : int) : int =
  match (a, b) with
  | (0, b) -> b
  | (a, 0) -> a
  | (a, b) when a mod 2 = 0 && b mod 2 = 0 -> 2 * binary_gcd (a / 2) (b / 2)
  | (a, b) when a mod 2 = 0 -> binary_gcd (a / 2) b
  | (a, b) when b mod 2 = 0 -> binary_gcd a (b / 2)
  | (a, b) -> binary_gcd (abs (a - b)) (min a b)

let () =
  gcd_trace 48 18;
  Printf.printf "\ngcd(48, 18) = %d  (expected 6)\n" (gcd 48 18);
  Printf.printf "lcm(4, 6)   = %d  (expected 12)\n" (lcm 4 6);
  Printf.printf "lcm(12, 18) = %d  (expected 36)\n" (lcm 12 18);
  Printf.printf "gcd [12;18;24] = %d  (expected 6)\n" (list_gcd [12;18;24]);
  Printf.printf "lcm [2;3;4]    = %d  (expected 12)\n" (list_lcm [2;3;4]);
  Printf.printf "binary_gcd(48, 18) = %d\n" (binary_gcd 48 18)

Key Differences

Aspect	Rust	OCaml
Recursion	Tail-recursive, TCO not guaranteed	TCO guaranteed
Signed integers	Use `i64` with `abs()`	`Int.abs` or `abs`
Standard library	`num::integer::gcd` (crate)	`Int.gcd` (recent OCaml)
Return type	Single `u64`	Single `int`
Extended GCD	Returns `(i64, i64, i64)`	`(int * int * int)`
Overflow prevention	Divide before multiply	Same idiom

OCaml Approach

OCaml's recursive GCD is identical in structure: let rec gcd a b = if b = 0 then a else gcd b (a mod b). OCaml's optimizer performs tail call elimination, so deep recursion is stack-safe. The Int.abs handles negative inputs for signed int. OCaml's standard library includes Int.gcd in recent versions. The Zarith library provides GCD for arbitrary-precision integers. OCaml's let lcm a b = (a / gcd a b) * b mirrors Rust exactly. The extended Euclidean algorithm uses a pair return type (int * int * int) for (gcd, x, y).

Full Source

#![allow(clippy::all)]
//! # GCD and LCM (Euclidean Algorithm)
pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}
pub fn lcm(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b
}
pub 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(48, 18), 6);
    }
    #[test]
    fn test_lcm() {
        assert_eq!(lcm(4, 6), 12);
    }
}

(* GCD, LCM, and Euclidean Algorithm in OCaml *)

(* The classic one-liner — functional elegance at its finest *)
let rec gcd (a : int) (b : int) : int =
  if b = 0 then a else gcd b (a mod b)

(* LCM via GCD — divide first to avoid overflow *)
let lcm (a : int) (b : int) : int =
  if a = 0 || b = 0 then 0
  else (a / gcd a b) * b

(* GCD of a list — neutral element is 0 since gcd(a,0)=a *)
let list_gcd (xs : int list) : int =
  List.fold_left gcd 0 xs

let list_lcm (xs : int list) : int =
  List.fold_left lcm 1 xs

(* Trace the steps of Euclidean algorithm *)
let gcd_trace (a : int) (b : int) : unit =
  Printf.printf "gcd(%d, %d):\n" a b;
  let a = ref a and b = ref b in
  while !b <> 0 do
    Printf.printf "  gcd(%d, %d) → rem = %d\n" !a !b (!a mod !b);
    let r = !a mod !b in
    a := !b;
    b := r
  done;
  Printf.printf "  = %d\n" !a

(* Binary GCD (Stein's algorithm) — avoids modulo *)
let rec binary_gcd (a : int) (b : int) : int =
  match (a, b) with
  | (0, b) -> b
  | (a, 0) -> a
  | (a, b) when a mod 2 = 0 && b mod 2 = 0 -> 2 * binary_gcd (a / 2) (b / 2)
  | (a, b) when a mod 2 = 0 -> binary_gcd (a / 2) b
  | (a, b) when b mod 2 = 0 -> binary_gcd a (b / 2)
  | (a, b) -> binary_gcd (abs (a - b)) (min a b)

let () =
  gcd_trace 48 18;
  Printf.printf "\ngcd(48, 18) = %d  (expected 6)\n" (gcd 48 18);
  Printf.printf "lcm(4, 6)   = %d  (expected 12)\n" (lcm 4 6);
  Printf.printf "lcm(12, 18) = %d  (expected 36)\n" (lcm 12 18);
  Printf.printf "gcd [12;18;24] = %d  (expected 6)\n" (list_gcd [12;18;24]);
  Printf.printf "lcm [2;3;4]    = %d  (expected 12)\n" (list_lcm [2;3;4]);
  Printf.printf "binary_gcd(48, 18) = %d\n" (binary_gcd 48 18)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_gcd() {
        assert_eq!(gcd(48, 18), 6);
    }
    #[test]
    fn test_lcm() {
        assert_eq!(lcm(4, 6), 12);
    }
}

Deep Comparison

OCaml vs Rust: Gcd Lcm Euclid

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement the extended Euclidean algorithm returning (gcd, x, y) such that a*x + b*y = gcd(a,b).

Use extended GCD to compute the modular inverse of a mod m when gcd(a, m) = 1.

Compute GCD of a list of numbers: verify gcd(a, b, c) = gcd(gcd(a, b), c).

Implement a Fraction type with automatic reduction using GCD on construction.

Benchmark recursive vs. iterative GCD and the binary GCD algorithm (using bit operations) on 64-bit integers.

Open Source Repos

functional-rust

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

Rust