拡張ユークリッドの互除法を実装するPythonプログラム

この記事では、以下の問題文に対する解決策について詳しく解説していきます。

問題文

2つの整数が与えられたとき、それらの最大公約数（GCD）を計算し、結果を表示するプログラムを作成してください。

拡張ユークリッドの互除法とは

GCD（最大公約数）とは、2つの数をどちらも割り切ることができる最大の整数のことです。ここではユークリッドの互除法を用いてGCDを計算します。この手法は、2つの数を繰り返し割り算を行い、余りが0になった時点で計算を停止するというものです。

さらに本記事では、通常のユークリッドの互除法を拡張したアルゴリズムを扱います。拡張ユークリッドの互除法では、再帰処理の過程で得られる以前の値を利用することで、GCDだけでなく、ax + by = gcd(a, b) を満たす係数 x と y も同時に求めることができます。

それでは、実際の実装例を見ていきましょう。

実装例

# 拡張ユークリッドの互除法
def gcdExtended(a, b, x, y):
    # ベースケース
    if a == 0 :
        x = 0
        y = 1
        return b
    x1 = 1
    y1 = 1 # 結果を格納
    gcd = gcdExtended(b%a, a, x1, y1)
    # 前回計算した値をもとにxとyを更新
    x = y1 - (b/a) * x1
    y = x1
    return gcd

x = 1
y = 1
a = 11
b = 15
g = gcdExtended(a, b, x, y)
print("gcd of ", a , "&" , b, " is = ", g)

実行結果

gcd of 11 & 15 is = 1

すべての変数はローカルスコープ内で宣言されており、それぞれの参照関係は上記のコードから確認できます。11と15は互いに素であるため、最大公約数が1となっていることが分かります。

まとめ

この記事では、拡張ユークリッドの互除法を用いて2つの整数の最大公約数を求めるPythonプログラムの作成方法について学びました。このアルゴリズムは、モジュラ逆元の計算や暗号理論（RSA暗号など）でも広く応用されている重要な手法なので、ぜひ理解を深めておきましょう。