gcd :: Nat -> Nat -> Nat gcd x y = if y == 0 then x else if x > y then gcd (x - y) y else gcd (y - x) x