fact: Definition div_eucl (a b:Z) : Z * Z := match a, b with | 0, _ => (0, 0) | _, 0 => (0, a) | pos a', pos _ => pos_div_eucl a' b | neg a', pos _ => let (q, r) := pos_div_eucl a' b in match r with | 0 => (- q, 0) | _ => (- (q + 1), b - r) end | neg a', neg b' => let (q, r) := pos_div_eucl a' (pos b') in (q, - r) | pos a', neg b' => let (q, r) := pos_div_eucl a' (pos b') in match r with | 0 => (- q, 0) | _ => (- (q + 1), b + r) end end.
imports: BinNums BinPos BinNat