(* Division modulo m *)

(* Pour diviser x par y modulo m, on commence par se servir
   de l'algorithme d'Euclide ├ętendu pour calculer l'inverse de y modulo m.
   Ensuite, il suffit de le multiplier par x. *)

let rec extended_gcd x y = (* Programme 79 page 327 *)
  if y = 0 then
    (1, 0, x)
  else
    let q = x / y in
    let (u, v, g) = extended_gcd y (x - q * y) in
    (v, u - q * v, g)

let div_mod x y m =
  assert (x > 0 && y > 0 && m > 0);
  let iy, _, g = extended_gcd y m in
  assert (g = 1);
  let iy = (iy + m) mod m in (* on assure iy >= 0 *)
  (x * iy) mod m

(* preuve : par l'algorithme d'Euclide ├ętendu, on a

     iy * y + im * m = gcd(y,m) = 1

   donc

     iy * y = 1 (mod m)

   et donc

     (x * iy) * y = x (mod m)
*)

This document was generated using caml2html