ユークリッドの互除法と再帰関数

2021年12月26日 13:29

ユークリッドの互除法

$${a}$$, $${b}$$ を自然数とする。
$${a}$$, $${b}$$ の最大公約数は、次のようにして求めることができる。
$${a}$$ を $${b}$$ で割った余り $${r}$$ を求める
$${b}$$ を $${r}$$ で割った余り $${r_1}$$ を求める
$${r}$$ を $${r_1}$$ で割った余り $${r_2}$$ を求める
以下同様に繰り返し、
$${r_{n−1}}$$ を $${r_n}$$ で割った余りが $${0}$$ となるとき、
$${r_n}$$ が $${a}$$, $${b}$$ の最大公約数である。

ユークリッドの互除法のpythonコード

ユークリッドの互除法を再帰を使わずに書くと、

# a, b の最大公約数 gcd(a, b) を返す関数
def gcd(a, b):
    while b:  # b が 0(False) になると終了 
        a, b = b, a % b
    return a  # 終了したとき最大公約数は a だから

これを再帰関数を使って書くと、

# a, b の最大公約数 d = gcd(a, b) を返す関数
def gcd(a, b):
    if b == 0:  # 最初に、無限ループにならないための終了条件を書く
        return a

    r = a % b
    """
      ユークリッドの互除法より b, r の最大公約数 d' が求まっていれば
      a, b の最大公約数 d は d = d' となる．
      d' は gcd(b, r) で求まる！（再帰呼び出し）
    """
    d = gcd(b, r)
    return d

冗長な表現を解消すると

# a, b の最大公約数 gcd(a, b) を返す関数
def gcd(a, b):
    if b == 0:
        return a

    return gcd(b, a % b)

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

二元一次不定方程式 $${ax+by=gcd(a, b)=d}$$ の整数解 $${x}$$ , $${y}$$ を求めるアルゴリズム。

$${a}$$ を $${b}$$ で割った商を $${q}$$, 余りを $${r}$$ とすると $${a=bq+r}$$ と書ける。
$${ax+by=d}$$ に $${a=bq+r}$$ を代入して
$${(bq+r)x+by=d}$$ より
$${b(qx+y)+rx=d}$$
いま、$${bs+rt=d}$$ の整数解 $${s}$$, $${t}$$ が求まっていれば、
$${qx+y=s}$$, $${x=t}$$ より
$${x=t}$$, $${y=s-qt}$$ となる。
そこで、$${s}$$, $${t}$$ を extgcd(b, r) で求める。（再帰呼び出し）

拡張ユークリッドの互除法のpythonコード

終了したときの戻り値は、
最大公約数 $${d=a}$$ だから不定方程式は $${ax+by=a}$$ となり
解は $${x=1}$$, $${y=0}$$ となるので

# ax+by=gcd(a, b)=d となる x, y, d を返す関数
def extgcd(a, b):
    if b == 0:
        return 1, 0, a
    
    q, r = a // b, a % b
    s, t, d = extgcd(b, r)
    x, y = t, s - q*t
    return x, y, d

冗長な表現を解消すると

# ax+by=gcd(a, b)=d となる x, y, d を返す関数
def extgcd(a, b):
    if b == 0:
        return 1, 0, a
    
    s, t, d = extgcd(b, a % b)
    return t, s - (a//b)*t, d

（参考）

三項演算子を使ったユークリッドの互除法のコード

# a, b の最大公約数 gcd(a, b) を返す関数
def gcd(a, b):
    return gcd(b, a % b) if b else a

再帰を使わない拡張ユークリッドの互除法のコード

# ax+by=gcd(a, b)=d となる x, y, d を返す
def extgcd(a, b):
    x, y = 1, 0
    s, t = 0, 1
    while b:
        q, r = a // b, a % b
        x, s = s, x - s*q
        y, t = t, y - t*q
        a, b = b, r
    return x, y, a

$${ax+by=a}$$　・・・①
$${as+bt=b}$$　・・・②
$${①-②×q}$$ を計算すると、$${a-bq=r}$$ だから
$${a(x-sq)+b(y-tq)=r}$$　・・・③
$${②-③×q_1}$$ を計算した結果を④
$${③-④×q_2}$$ を計算した結果を⑤
これを繰り返して、余りが $${0}$$ になるまで続ける。
初期値は
①を満たす $${x=1}$$, $${y=0}$$
②を満たす $${s=0}$$, $${t=1}$$

（数学に応用）　※答えだけで良いとき
　$${123x+56y=1}$$ の整数解のうちの $${1}$$ 組を求める。
　係数だけ書くと
　　　 1　 0　123　・・・①
　　　 0　 1　 56　・・・②
　　　 1　-2　 11　・・・③　　123 // 56 = 2　だから　①-②×2
　　　-5　11　 1　・・・④　　56 // 11 = 5　だから　②-③×5
　右端の数が 1 になったとき
　左から $${x}$$, $${y}$$ の値となる。

ユークリッドの互除法と再帰関数