ユークリッドの互除法

1 概要
2 証明
3 計算例
4 再帰関数による実装

概要

ユークリッドの互除法(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$ は $b$ と $r$ の公約数でもあることがわかる。

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

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

(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

def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)

print( gcd(12, 8) )

def gcd(a, b):

if a % b == 0:

return b

else:

return gcd(b, a % b)

print( gcd(12, 8) )

CLisp

(defun mygcd (a b)
	(if (= (mod a b) 0) b (mygcd b (mod a b)))
)

(print (mygcd 18 12))

(defun mygcd (a b)

(if (= (mod a b) 0) b (mygcd b (mod a b)))

)

(print (mygcd 18 12))

TauStation

ユークリッドの互除法

概要

証明

計算例

再帰関数による実装

コメントを残すコメントをキャンセル

概要

証明

計算例

再帰関数による実装

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル