拡張されたユークリッドの互除法 (導入)

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

概要

前回 のユークリッドの互除法により、2 つの整数の最大公約数を効率的に求めることができるようになりました。

しかし、ユークリッドの互除法によって、2 つの整数 $a, b$ の最大公約数を求めるだけでなく、一次不定方程式 $ax + by = {\rm gcd}(a, b)$ の解 $(x, y)$ を求めることができます。

どういうことかというと、例えば、前回の例でいうと $8767$ と $4664$ の最大公約数は $11$ でした。

このとき、一次不定方程式 $8767 x + 4664 y = 11$ の解 $(x, y)$ を求めることができるというわけです。ちなみに、$(x, y) = (133, -250)$ となります。

一応、Python での実装を最後のほうに載せますが、まだ愚直な実装しかしていません。本格的な実装は次回以降にしたいと思います。

具体例

前回の例をそのまま使用して、$8767$ と $4664$ のユークリッドの互除法を考えて、一次不定方程式 $8767 x + 4664 y = {\rm gcd}(8767, 4664)$ の解 $(x, y)$ を求めてみます。

一般に、$a, b$ の除算の商 $q$ と剰余 $r$ としたとき、$a = qb + r$ と表せることから、$r = a - qb$ と変形できるので、ユークリッドの互除法の除算をすべてこの形で表すことにします。

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

このうち、最後の式の左辺が ${\rm gcd}(8767, 4664)$ であることから、右辺を変形していって $8767 x + 4664 y$ の形を目指すと良さそうです。

最後の式の右辺の $33$ は、その一段上の式 $33 = 561 - 3 \times 176$ の左辺であるため、代入して整理することができます。

同様に、右辺の $176$ に、さらに一段上の $176 = 4103 - 7 \times 561$ が代入できるので、この代入操作を下から上へ逆順にたどっていくと、以下のようになります。

$$ \begin{align} 11 &= 176 - 5 \times 33 \\ &= 176 - 5 \times ( 561 - 3 \times 176 ) \\ &= - 5 \times 561 + 16 \times 176 \\ &= - 5 \times 561 + 16 \times ( 4103 - 7 \times 561 ) \\ &= 16 \times 4103 - 117 \times 561 \\ &= 16 \times 4103 - 117 \times ( 4664 - 1 \times 4103 ) \\ &= - 117 \times 4664 + 133 \times 4103 \\ &= - 117 \times 4664 + 133 \times ( 8767 - 1 \times 4664 ) \\ &= 133 \times 8767 - 250 \times 4664 \end{align} $$

よって、$8767 \times 133 + 4664 \times (- 250) = 11$ ということが分かったので、解を $(x, y) = (133, -250)$ と求めることができました。

一般化

具体的な計算方法が分かったので、Python での実装に向けて一般化していきたいと思います。

まずは、任意の正整数 $a, b$ に対して、以下のようにユークリッドの互除法の除算を行います。なお、$r_0 = a, \ r_1 = b, \ r_n = {\rm gcd}(a, b)$ とします。

$$ \begin{align} r_0 &= q_0 r_1 + r_2 \\ r_1 &= q_1 r_2 + r_3 \\ r_2 &= q_2 r_3 + r_4 \\ \vdots \\ r_{n-3} &= q_{n-3} r_{n-2} + r_{n-1} \\ r_{n-2} &= q_{n-2} r_{n-1} + r_n \\ r_{n-1} &= q_{n-1} r_n \end{align} $$

次に、具体例で挙げたような代入操作を、とりあえず 1 回だけ行ってみます。

$$ \begin{align} r_n &= r_{n-2} - q_{n-2} r_{n-1} \\ &= r_{n-2} - q_{n-2} ( r_{n-3} - q_{n-3} r_{n-2} ) \\ &= - q_{n-2} r_{n-3} + (1 + q_{n-2} q_{n-3}) r_{n-2} \end{align} $$

この次の代入操作を行うには、係数が煩雑であるため、$X_{n-2} = - q_{n-2}, \ Y_{n-2} = 1 + q_{n-2} q_{n-3}$ とおきます。この状態でもう 1 回操作を行います。

$$ \begin{align} r_n &= X_{n-2} r_{n-3} + Y_{n-2} r_{n-2} \\ &= X_{n-2} r_{n-3} + Y_{n-2} ( r_{n-4} - q_{n-4} r_{n-3} ) \\ &= Y_{n-2} r_{n-4} + (X_{n-2} - Y_{n-2} q_{n-4}) r_{n-3} \end{align} $$

これで、$r_{n-4}, \ r_{n-3}$ のそれぞれの係数を $X_{n-3} = Y_{n-2}, \ Y_{n-3} = X_{n-2} - Y_{n-2} q_{n-4}$ とおくことで、次からの代入操作も同じように行うことができます。

これをアルゴリズムとして考えると、以下の手順になります。

1. ユークリッドの互除法の手順における商を、順に配列で保持する
2. 最後の商は割り切ったときのものであるため、その次の商 $q_1$ から開始する
3. 初期値を $X = 1, \ Y = - q_1$ とする
4. 次の商 $q$ が存在しない場合、$X, Y$ が一次不定方程式の解であるため、アルゴリズムを終了する
5. 次の商 $q$ が存在する場合、$Y, \ X-Yq$ を新たな $X, \ Y$ として、手順 4 に戻る

まずは愚直に実装してみる

拡張されたユークリッドの互除法のアルゴリズムを考えることができたので、Python でそのまま実装してみます。

from typing import List, Tuple

def extended_euclidean_algorithm(a: int, b: int) -> Tuple[int, int, int]:

    # ユークリッドの互除法

    quotients: List[int] = []

    while b != 0:
        quotients.append(a // b)
        r: int = a % b
        a = b
        b = r

    # 一次不定方程式の解

    quotients.reverse()

    x: int = 1
    y: int = -quotients[1]

    for q in quotients[2:]:
        new_x: int = y
        new_y: int = x - y * q
        x = new_x
        y = new_y

    return a, x, y


print(extended_euclidean_algorithm(8767, 4664))
# (11, 133, -250)

これでも求める結果は得られるのですが、2 回も同じようなループするのはいささか不格好に見えます。

次回以降では、行列演算を用いて 1 回のループで計算することを目指したいと思います。

追記 (2021-09-29)

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