module Euklid

open System

let rec euklid a b =
    if b = 0 then a
    else euklid b (a % b)

let rec erwEuklid a b =
    if b = 0 then (a, 1, 0)
    else
        let (d, x, y) = erwEuklid b (a % b)
        (d, y, x - (a / b) * y)