ユークリッドの互除法

概要

ユークリッドの互除法(Euclidean Algorithm)は、2つの自然数の最大公約数を求める手順。

2つの自然数a, b \; (a \ge b)の最大公約数(GCD: greatest common divisor)は、bと剰余r = a \mod bの最大公約数に等しいという性質を利用。数を順次割り込んでいき、剰余がゼロとなったときの除数が最大公約数となる。

(1)   }\begin{align*}a \mod b &= r_1 \quad (a \ge b) \\b \mod r &= r_2 \\&\vdots \\r_{n-1} \mod r_n &= 0 \\&\Downarrow \\\gcd(a, b) &= r_n\end{align*}

証明

以下の余りあり除算を考える。

(2)   \begin{gather*}a \mod b = r \Rightarrow a = bd + r\end{gather*}

a, bの公約数をmとすると、上式は以下のように変形され、mは余りrの公約数でもあることがわかる。

(3)   \begin{gather*}a = mp , \quad b = mq \\r = mp - mqd = m(p - qd)\end{gather*}

一方、b, rの公約数をnとすると、naの公約数であることがわかる。

(4)   \begin{gather*}b = ns , \quad r = nt \\a = nsd + nt = n(sd + t)\end{gather*}

これより、a, bの公約数の集合とb, rの公約数の集合は等しく、最大公約数も等しくなる。

(5)   \begin{equation*}a = bd+r \Rightarrow \gcd(a, b) = \gcd(b, r)\end{equation*}

計算例

143と91の最大公約数を求める。

(6)   \begin{align*}&143 \mod 91 = 52 \\&91 \mod 52 = 39 \\&52 \mod 39 = 13 \\&39 \mod 13 = 0 \\&\therefore \gcd(143, 91) = 13\end{align*}

再帰関数による実装

PythonとCLispの再帰関数による実装例は以下の通り。ただし、第1引数>第2引数を前提としており、エラー処理はしていない。

Python

CLisp

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です