package euler

  1. Overview
  2. Docs

Solving diophantine equations, i.e. equations on integers.

exception No_solution

Raised when a system has no solution.

val solve_congruences : (int * int * int) Seq.t -> int * int

solve_congruences @@ List.to_seq [ (a1, b1, m1) ; … ; (ak, bk, mk) ], provided that the mi are non-zero, solves the following linear congruence system of unknown x:

  • a1 · x ≡m1 b1
  • ak · x ≡mk bk

TODO: complexity?

  • returns

    a pair (x, m) where 0 ≤ x < m, which represents the set of solutions x + mℤ,

OCaml

Innovation. Community. Security.