sig
  module type Rat =
    sig
      type q
      val eq : Euclid.Rat.q -> Euclid.Rat.q -> bool
      val ( + ) : Euclid.Rat.q -> Euclid.Rat.q -> Euclid.Rat.q
      val zero : Euclid.Rat.q
      val inv : Euclid.Rat.q -> Euclid.Rat.q
      val ( * ) : Euclid.Rat.q -> Euclid.Rat.q -> Euclid.Rat.q
      val one : Euclid.Rat.q
      val ( / ) : Euclid.Rat.q -> Euclid.Rat.q -> Euclid.Rat.q
      val floor : Euclid.Rat.q -> Euclid.Rat.q
      val is_int : Euclid.Rat.q -> bool
    end
  module type S =
    sig
      type t
      val euclid :
        Euclid.S.t -> Euclid.S.t -> Euclid.S.t * Euclid.S.t * Euclid.S.t
      val solve :
        Euclid.S.t list ->
        Euclid.S.t -> (Euclid.S.t * Euclid.S.t list) option
    end
  module Make :
    functor (R : Rat) ->
      sig
        type t = R.q
        val euclid :
          Euclid.S.t -> Euclid.S.t -> Euclid.S.t * Euclid.S.t * Euclid.S.t
        val solve :
          Euclid.S.t list ->
          Euclid.S.t -> (Euclid.S.t * Euclid.S.t list) option
      end
end