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

2 min read

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

ユークリッドの互除法とは、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に戻る

プログラム

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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に戻る．

プログラム

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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]