832 Fundamental

Extended Euclidean Algorithm

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Extended Euclidean Algorithm" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. The basic Euclidean algorithm finds gcd(a, b) but not the coefficients. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

The basic Euclidean algorithm finds gcd(a, b) but not the coefficients. The extended version also finds Bezout coefficients x, y such that a*x + b*y = gcd(a, b). These coefficients are essential for computing modular inverses (when gcd(a, m) = 1, x is a's inverse mod m), solving linear Diophantine equations ax + by = c, and implementing CRT. Without the extended algorithm, modular inverse requires Fermat's little theorem (only works for prime moduli) or Euler's theorem (requires phi(m), harder to compute). Extended GCD works for any modulus, not just primes.

🎯 Learning Outcomes

• Understand the recursive structure: if extended_gcd(b, a%b) = (g, x1, y1), then for the original pair: x = y1, y = x1 - (a/b)*y1

• Derive Bezout coefficient update via the recurrence relationship

• Apply to modular inverse: mod_inv(a, m) = x mod m where (g, x, _) = extended_gcd(a, m) and g = 1

• Solve general linear Diophantine ax + by = c: has solution iff gcd(a,b) divides c

• Understand sign handling: Bezout coefficients can be negative

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Extended Euclidean Algorithm in OCaml *)

(* Returns (g, x, y) such that a*x + b*y = g = gcd(a, b) *)
(* The recursive version is the cleanest expression of the algorithm *)
let rec extended_gcd (a : int) (b : int) : int * int * int =
  if b = 0 then
    (a, 1, 0)   (* a*1 + 0*0 = a = gcd *)
  else
    let (g, x, y) = extended_gcd b (a mod b) in
    (* Recurrence: if b*x + (a mod b)*y = g
       then b*x + (a - (a/b)*b)*y = g
            a*y + b*(x - (a/b)*y) = g *)
    (g, y, x - (a / b) * y)

(* Iterative version (avoids deep recursion for very large inputs) *)
let extended_gcd_iter (a : int) (b : int) : int * int * int =
  let old_r = ref a and r = ref b in
  let old_s = ref 1 and s = ref 0 in
  let old_t = ref 0 and t = ref 1 in
  while !r <> 0 do
    let q = !old_r / !r in
    let tmp = !r in r := !old_r - q * !r; old_r := tmp;
    let tmp = !s in s := !old_s - q * !s; old_s := tmp;
    let tmp = !t in t := !old_t - q * !t; old_t := tmp;
  done;
  (!old_r, !old_s, !old_t)

(* Modular inverse of a mod m (exists iff gcd(a,m)=1) *)
let mod_inv (a : int) (m : int) : int option =
  let (g, x, _) = extended_gcd (((a mod m) + m) mod m) m in
  if g <> 1 then None
  else Some (((x mod m) + m) mod m)

(* Solve linear Diophantine equation ax + by = c *)
(* Returns Some (x0, y0, dx, dy) where general solution is (x0 + k*dx, y0 - k*dy) *)
let solve_diophantine (a : int) (b : int) (c : int) : (int * int * int * int) option =
  let (g, x0, y0) = extended_gcd a b in
  if c mod g <> 0 then None
  else
    let scale = c / g in
    Some (x0 * scale, y0 * scale, b / g, a / g)

let () =
  let show_gcd a b =
    let (g, x, y) = extended_gcd a b in
    Printf.printf "gcd(%d, %d) = %d: %d*%d + %d*%d = %d  (check: %b)\n"
      a b g a x b y g (a*x + b*y = g)
  in
  show_gcd 35 15;
  show_gcd 48 18;
  show_gcd 101 103;

  Printf.printf "\nModular inverses:\n";
  List.iter (fun (a, m) ->
    match mod_inv a m with
    | Some inv -> Printf.printf "  inv(%d, %d) = %d  (check: %d*%d mod %d = %d)\n"
                    a m inv a inv m (a * inv mod m)
    | None     -> Printf.printf "  inv(%d, %d): no inverse\n" a m
  ) [(3, 7); (10, 17); (2, 4)];

  Printf.printf "\nDiophantine 3x + 5y = 1:\n";
  (match solve_diophantine 3 5 1 with
   | Some (x, y, dx, dy) ->
     Printf.printf "  Particular: x=%d, y=%d  general: x=%d+%d*k, y=%d-%d*k\n" x y x dx y dy
   | None -> Printf.printf "  No solution\n")

Key Differences

Aspect	Rust	OCaml
Negative modulo	`rem_euclid` for mathematical mod	`((x mod m) + m) mod m`
Return type	Tuple `(i64, i64, i64)`	Tuple `(int * int * int)`
Stack safety	Tail-recursive iter preferred	TCO makes recursion safe
Modular inverse	Returns `Option<i64>`	Returns `int option`
Bezout signs	Can be negative (correct)	Same
Integer size	`i64` for 64-bit inputs	`int` (63-bit) or `Int64`

OCaml Approach

OCaml's recursive extended GCD returns (int * int * int) exactly as in Rust. The pattern let (g, x1, y1) = extended_gcd b (a mod b) in (g, y1, x1 - (a / b) * y1) is identical in structure. OCaml handles negative remainders from mod differently: (-7) mod 3 = -1 in OCaml (truncating division), requiring explicit adjustment. The ((x mod m) + m) mod m idiom ensures non-negative modular inverse. OCaml's Int.rem has the same truncating behavior.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Extended Euclidean Algorithm in OCaml *)

(* Returns (g, x, y) such that a*x + b*y = g = gcd(a, b) *)
(* The recursive version is the cleanest expression of the algorithm *)
let rec extended_gcd (a : int) (b : int) : int * int * int =
  if b = 0 then
    (a, 1, 0)   (* a*1 + 0*0 = a = gcd *)
  else
    let (g, x, y) = extended_gcd b (a mod b) in
    (* Recurrence: if b*x + (a mod b)*y = g
       then b*x + (a - (a/b)*b)*y = g
            a*y + b*(x - (a/b)*y) = g *)
    (g, y, x - (a / b) * y)

(* Iterative version (avoids deep recursion for very large inputs) *)
let extended_gcd_iter (a : int) (b : int) : int * int * int =
  let old_r = ref a and r = ref b in
  let old_s = ref 1 and s = ref 0 in
  let old_t = ref 0 and t = ref 1 in
  while !r <> 0 do
    let q = !old_r / !r in
    let tmp = !r in r := !old_r - q * !r; old_r := tmp;
    let tmp = !s in s := !old_s - q * !s; old_s := tmp;
    let tmp = !t in t := !old_t - q * !t; old_t := tmp;
  done;
  (!old_r, !old_s, !old_t)

(* Modular inverse of a mod m (exists iff gcd(a,m)=1) *)
let mod_inv (a : int) (m : int) : int option =
  let (g, x, _) = extended_gcd (((a mod m) + m) mod m) m in
  if g <> 1 then None
  else Some (((x mod m) + m) mod m)

(* Solve linear Diophantine equation ax + by = c *)
(* Returns Some (x0, y0, dx, dy) where general solution is (x0 + k*dx, y0 - k*dy) *)
let solve_diophantine (a : int) (b : int) (c : int) : (int * int * int * int) option =
  let (g, x0, y0) = extended_gcd a b in
  if c mod g <> 0 then None
  else
    let scale = c / g in
    Some (x0 * scale, y0 * scale, b / g, a / g)

let () =
  let show_gcd a b =
    let (g, x, y) = extended_gcd a b in
    Printf.printf "gcd(%d, %d) = %d: %d*%d + %d*%d = %d  (check: %b)\n"
      a b g a x b y g (a*x + b*y = g)
  in
  show_gcd 35 15;
  show_gcd 48 18;
  show_gcd 101 103;

  Printf.printf "\nModular inverses:\n";
  List.iter (fun (a, m) ->
    match mod_inv a m with
    | Some inv -> Printf.printf "  inv(%d, %d) = %d  (check: %d*%d mod %d = %d)\n"
                    a m inv a inv m (a * inv mod m)
    | None     -> Printf.printf "  inv(%d, %d): no inverse\n" a m
  ) [(3, 7); (10, 17); (2, 4)];

  Printf.printf "\nDiophantine 3x + 5y = 1:\n";
  (match solve_diophantine 3 5 1 with
   | Some (x, y, dx, dy) ->
     Printf.printf "  Particular: x=%d, y=%d  general: x=%d+%d*k, y=%d-%d*k\n" x y x dx y dy
   | None -> Printf.printf "  No solution\n")

Deep Comparison

OCaml vs Rust: Extended Euclidean

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

Verify the extended GCD output: for all tested pairs (a, b), check that a*x + b*y == gcd(a,b).

Implement iterative extended GCD to avoid stack depth issues for large inputs.

Solve the linear Diophantine equation ax + by = c or report no solution, using extended GCD.

Use the extended GCD to implement CRT for two congruences without explicitly computing phi.

Implement a batch modular inverse computation for a list of values mod p using the recurrence inv[i] = -(p/i) * inv[p%i] mod p.

Open Source Repos

functional-rust

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

Rust