ユークリッドの互除法と拡張ユークリッドの互除法のpythonプログラム

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

ユークリッドの互除法とは、2つの整数 \(a\) と \(b\) \((a>b)\) が与えられたとき、\(a\) を \(b\) で割った余り \(r\) とすることで、\(a\) と \(b\) の最大公約数を求める方法。除法の原理を利用し、割り算を繰り返すことによって最大公約数を求める。

ユークリッドの互除法のアルゴリズム

入力：整数\(a,b\)
出力：最大公約数 \(d\)

1. \(a_0 = a\), \(a_1 = b\)
2. \(a_i=0\)のとき，
   \(d=a_{i-1}\)とし終了
3. \(a_{i-1}=a_iq_i+a_{i+1}\)
   　　として2に戻る

プログラム

def euclid(a,b):
    a_list = []
    if a < b:
        a_list.append(b)
        a_list.append(a)
    if a >= b:
        a_list.append(a)
        a_list.append(b)
    i = 0
    while(a_list[-1]!=0):
        a_list.append(a_list[i]%a_list[i+1])
        i +=1
    return a_list[-2]

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

拡張ユークリッドの互除法とは、一次不定方程式 \(ax+by=d\) の一つの解を求める方法。\(a_0=a\)、\(a_1=b\) とおくと、以下のように求めることができる。

\([\begin{array}{cc} a_{i-1} \\ a_i \end{array}]= [\begin{array}{cc} a_iq_i+a_{i+1} \\ a_i \end{array}]\) とすると， \([\begin{array}{cc} a_{i-1} \\ a_i \end{array}]= [\begin{array}{cc} q_i & 1 \\ 1 & 0 \end{array}] [\begin{array}{cc} a_i \\ a_{i+1} \end{array}] \) とかける． \([\begin{array}{cc} q_i & 1 \\ 1 & 0 \end{array}]\) の逆行列を，\(L_i\)とする． \([\begin{array}{cc} a_i \\ a_{i+1} \end{array}]=L_i [\begin{array}{cc} a_{i-1} \\ a_i \end{array}] \) これを繰り返すと， \([\begin{array}{cc} d \\ 0 \end{array}]=L_i,\dots,L_2 [\begin{array}{cc} a \\ b \end{array}] \) となる．

拡張ユークリッドの互除法のアルゴリズム

入力：整数\(a,b\)
出力：最大公約数\(d\) と \(ax+by=d\)となる整数\(x, y\)

1. \(a_0 =a\), \(a_1 =b\)
2. \(x_0 =1\), \(x_1 =0\)，\(y_0 =0\), \(y_1 =1\)
3. \(a_i=0\)のとき，
   \(d=a_i−1\)，\(x=x_{i−1}\)，\(y=y_{i−1}\)とし終了.
4. \(a_{i−1} = a_iq_i + a_{i+1}\)により，\(a_{i+1}\)と\(q_i\)を定める.
   \(x_{i+1} = x_{i−1} − q_ix_i\) \(y_i+1=y_i−1−q_iy_i\)
   として3に戻る．

プログラム

def exEuclid(a,b):
    a_list = []
    if a < b:
        a_list.append(b)
        a_list.append(a)
    if a >= b:
        a_list.append(a)
        a_list.append(b)
    q = []
    x = []
    x.append(1)
    x.append(0)
    y = []
    y.append(0)
    y.append(1)
    i = 0
    while(a_list[-1]!=0):
        a_list.append(a_list[i]%a_list[i+1])
        q.append(a_list[i]//a_list[i+1])
        x.append(x[-2]-q[-1]*x[-1])
        y.append(y[-2]-q[-1]*y[-1])
        i +=1
    return x[-2],y[-2],a_list[-2]