let rec extended_gcd a b = if a > b then extended_gcd b a else if b = 0 then (1, 0) else let qr = divide a b; let st = extended_gcd b (snd qr); (snd st, (fun s q t -> s - q * t) (fst st) (fst qr) (snd st));;
let divide x y = x / y, x mod y;;