ユークリッドの互除法

ユークリッドの互除法は，２つの自然数または整数の最大公約数（Greatest Common Divisor）を求めるアルゴリズムです．

1. 入力を m, n (m ≧ n) とする。

2. n = 0 なら、 m を出力してアルゴリズムを終了する。

3. m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。

gcd                 :: Int -> Int -> Int
gcd m n | m < n     = gcd n m
        | n == 0    = n
        | otherwise = gcd n (mod m n)

最小公倍数と最大公約数の以下の関係から，
最小公倍数（Least Common Multiple）を用意に求められる．

gcd(a, b) * lcm(a, b) = a * b

lcm     :: Int -> Int -> Int
lcm m n = m * n / gcd m n