ユークリッドの互除法

• #1 : ユークリッドの互除法
• #2 : 拡張されたユークリッドの互除法 (導入)
• #3 : 拡張されたユークリッドの互除法 (実装)

概要

ユークリッドの互除法 (Euclidean algorithm) とは、2 つの整数の最大公約数を効率的に求めるアルゴリズムのことです。

最古のアルゴリズムと呼ばれているらしいです。

Python で実装するならば、以下の通りです。

# 再帰的に簡潔に記述するパターン
def gcd(a: int, b: int) -> int:
    return a if b == 0 else gcd(b, a % b)

print(gcd(8767, 4664))
# 11


# アルゴリズムの手順をそのまま記述するパターン
def euclidean_algorithm(a: int, b: int) -> int:

    while b != 0:
        r: int = a % b
        a = b
        b = r

    return a

print(euclidean_algorithm(8767, 4664))
# 11

ユークリッドの互除法の手順

2 つの整数に対して、以下の手順を繰り返すことで最大公約数を求めることができます。

1. 2 つの整数を $a, b$ とする
2. $b = 0$ ならば、$a$ が最大公約数であるため、アルゴリズムを終了する
3. $b \neq 0$ ならば、$a$ を $b$ で除算した剰余を $r$ とするとき、$b, r$ を新たな 2 数として最初に戻る

例

$8767$ と $4664$ の最大公約数を、ユークリッドの互除法によって求めます。

$$ \begin{align} 8767 \div 4664 &= 1 \ \ldots \ 4103 \\ 4664 \div 4103 &= 1 \ \ldots \ 561 \\ 4103 \div 561 &= 7 \ \ldots \ 176 \\ 561 \div 176 &= 3 \ \ldots \ 33 \\ 176 \div 33 &= 5 \ \ldots \ 11 \\ 33 \div 11 &= 3 \end{align} $$

以上より、最大公約数は $11$ と求められました。

なぜ、最大公約数が得られるのか

ユークリッドの互除法の手順では、最初の 2 数 $a, b$ ではなく、その剰余 $r$ を用いて $b, r$ 、あるいはその次と、最初の 2 数ではないものを次々と計算しています。

そうであるにもかかわらず、最初の 2 数の最大公約数が求められるということは、次の命題が成立するということです。

以下、$a, b$ の最大公約数のことを記号を用いて ${\rm gcd}(a, b)$ と表します。G.C.D. とは最大公約数 (greatest common divisor) のことです。

命題

任意の正整数 $a, b$ について、$a$ を $b$ で除算した剰余を $r$ とするとき、

$$ {\rm gcd}(a, b) = {\rm gcd}(b, r) $$

が成立する。

証明

任意の正整数 $a, b$ について、$a$ を $b$ で除算した商を $q$ 、剰余を $r$ とすると、

$$ a = qb + r $$

また、${\rm gcd}(a, b) = d, \ {\rm gcd}(b, r) = d'$ と置くとき、

$$ \begin{align} ({\rm i}) \ d &\leq d' \\ ({\rm ii}) \ d &\geq d' \end{align} $$

を示すことで、$d = d'$ を示す。

$({\rm i})$ $d \leq d'$ を示す。

${\rm gcd}(a, b) = d$ より、正整数 $a', b'$ を用いて $a=a'd, \ b=b'd$ と表せる。

$a=qb+r$ より、

$$ \begin{align} r &= a - qb \\ &= a'd - q \cdot b'd \\ &= (a' - qb')d \end{align} $$

となるため、$d$ は $r$ の約数である。

一方、$d$ は ${\rm gcd}(a, b) = d$ より $b$ の約数でもあることから、$b, r$ の公約数である。

したがって、${\rm gcd}(b, r) = d'$ より、$d \leq d'$ が示された。

$({\rm ii})$ $d \geq d'$ を示す。

${\rm gcd}(b, r) = d'$ より、正整数 $b'', r''$ を用いて $b=b''d', \ r=r''d'$ と表せる。

$a=qb+r$ より、

$$ \begin{align} a &= qb + r \\ &= q \cdot b''d' + r''d' \\ &= (qb'' + r'')d' \end{align} $$

となるため、$d'$ は $a$ の約数である。

一方、$d'$ は ${\rm gcd}(b, r) = d'$ より $b$ の約数でもあることから、$a, b$ の公約数である。

したがって、${\rm gcd}(a, b) = d$ より、$d \geq d'$ が示された。

以上より、$({\rm i}) ({\rm ii})$ が示されたので、$d = d'$ が示された。

実際の値で処理を追ってみる

既に例に挙げた $8767$ と $4664$ のユークリッドの互除法による以下の処理について、その過程を命題とともに観察してみます。

$$ \begin{align} 8767 \div 4664 &= 1 \ \ldots \ 4103 \\ 4664 \div 4103 &= 1 \ \ldots \ 561 \\ 4103 \div 561 &= 7 \ \ldots \ 176 \\ 561 \div 176 &= 3 \ \ldots \ 33 \\ 176 \div 33 &= 5 \ \ldots \ 11 \\ 33 \div 11 &= 3 \end{align} $$

まず、$8767 \div 4664 = 1 \ \ldots \ 4103$ より、剰余が $4103$ なので、命題より ${\rm gcd}(8767, 4664) = {\rm gcd}(4664, 4103)$ が分かります。

次に、$4664 \div 4103 = 1 \ \ldots \ 561$ より、剰余が $561$ なので、命題より ${\rm gcd}(4664, 4103) = {\rm gcd}(4103, 561)$ が分かります。

同様の除算を繰り返して、命題より以下の通りになることが分かりました。

$$ \begin{align} {\rm gcd}(8767, 4664) &= {\rm gcd}(4664, 4103) \\ &= {\rm gcd}(4103, 561) \\ &= {\rm gcd}(561, 176) \\ &= {\rm gcd}(176, 33) \\ &= {\rm gcd}(33, 11) \\ \end{align} $$

最後の 2 数において $33 \div 11 = 3$ となり割り切れるということは、$11$ が $33$ の約数であり、かつ、$11$ が 2 数の最大公約数であるということです。

したがって、${\rm gcd}(33, 11) = 11$ となり、命題より ${\rm gcd}(8767, 4664) = 11$ と求められるわけです。

メモ

元々は、RSA 暗号を数学的に理解することを目的として、書き始めたものです。

そのため、この後に拡張されたユークリッドの互除法、RSA 暗号と続きます。

ただ、途中からは拡張されたユークリッドの互除法の Python での実装の方に熱が入り、RSA 暗号はおまけになりました。

気が向いたら、続きを書いていく予定です。

追記 (2021-09-28)

次回の 拡張されたユークリッドの互除法 (導入) を投稿しました。