ユークリッド互除法とは

/代数学

ユークリッド互除法

ユークリッド互除法とは、2つの正数の最大公約数を求めるアルゴリズムです。ユークリッド互除法は次の手順で行います。

  1. 2つの正数の $a,b$($a\ge b$)の大きい方($a$)を小さい方($b$)で割り、余り($c$)を求める。
    $$c=a\pmod{b}$$
  2. 先ほどの割った数($b$)を先ほどの余り($c$)で割り、余り($d$)を求める。
    $$d=b\pmod{c}$$
  3. これを余りが0になるまで繰り返し、その時の1つ前の余りが最大公約数となる。

これを実際に、798と91で計算してみます。次の表の様に、最大公約数は7であることが分かります。

回数 割り算 余り
798 ÷ 91 70
91 ÷ 70 21
70 ÷ 21
21 ÷ 7

ユークリッド互除法のポイントは以下の通りで、

  • 余りは割られる数の半分より小さい
  • 割られる数は2つ前の余りである

これらの特徴により、高速に最大公約数を求めることができます。

拡張ユークリッド互除法

拡張ユークリッド互除法とは、2つの正数 $a,b$ と最大公約数 $d$ について、以下の式が成り立つ整数 $x,y$ を求めるアルゴリズムです。

$$ax+by=d  -①$$

拡張ユークリッド互除法は、ユークリッド互除法の手順に次の手順が加わります。

  1. $x$ と $y$ の初期値を以下で設定する。
    $$x_0=1 , x_1=0 , y_0=0 , y_1=1$$
  2. $a_{i-1}$ と $a_i$ の商($q_i$)より、$x$ と $y$ の値を計算する。
    $$x_{i+1}=x_{i-1}-q_ix_i  ,  y_{i+1}=y_{i-1}-q_iy_i$$
  3. $a_i=0$ の場合は、$x=x_i , y=y_i$ と置く。

先ほどと同様、798と91で計算してみます。次の表の様に、$x=4$、$y=-35$ であることが分かります。

回数 割り算 $x_{i-1}-q_ix_i=x_{i+1}$ $y_{i-1}-q_iy_i=y_{i+1}$ 余り
798 ÷ 91 70
91 ÷ 70 1-8・0=1 0-8・1=-8 21
70 ÷ 21 0-1・1=-1 1-1・(-8)=9
21 ÷ 7 1-3・(-1)= -8-3・9=-35
①式を導く

2つの正数を $a_0=a$、$a_1=b$($a_0\ge a_1$)と置き、商を $q_i$ とすると、以下のように表すことができます。

$$a_0=a_1q_1+a_2$$

$$a_1=a_2q_2+a_3$$

$$\cdots$$

$$a_{i-1}=q_ia_i+a_{i+1}$$

これを行列で表すと、

$$\left(\begin{array}{cc} a_{i-1} \\ a_i \end{array}\right)=
\left(\begin{array}{cc} q_i & 1 \\
1 & 0 \end{array}\right)\left(\begin{array}{cc} a_i \\ a_{i+1} \end{array}\right)$$

この逆行列、

$$M_i=\left(\begin{array}{cc} q_i & 1 \\
1 & 0 \end{array}\right)^{-1}=
\left(\begin{array}{cc} 0 & 1 \\
1 & -q_i \end{array}\right)$$

を使うと、

$$\left(\begin{array}{cc} a_i \\ a_{i+1} \end{array}\right)=M_i
\left(\begin{array}{cc} a_{i-1} \\ a_i \end{array}\right)=
M_iM_{i-1}\cdots M_1\left(\begin{array}{cc} a_0 \\ a_1 \end{array}\right)$$

従って、$i$ 回目で余りが0($a_i=0$)であれば、その1つ前の余りが最大公約数($d=a_{i-1}$)であるため、以下のように表すことができます。

$$\left(\begin{array}{cc} d \\ 0 \end{array}\right)=
M_{i-1}\cdots M_1\left(\begin{array}{cc} a \\ b \end{array}\right)\equiv
\left(\begin{array}{cc} x & y \\
z & w \end{array}\right)\left(\begin{array}{cc} a \\ b \end{array}\right)$$

 

数学
線形代数学、正規分布、統計分析
数理の散策路
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

Wikipedia

 

タイトルとURLをコピーしました