ユークリッド互除法
ユークリッド互除法とは、2つの正数の最大公約数を求めるアルゴリズムです。ユークリッド互除法は次の手順で行います。
- 2つの正数の $a,b$($a\ge b$)の大きい方($a$)を小さい方($b$)で割り、余り($c$)を求める。
$$c=a\pmod{b}$$ - 先ほどの割った数($b$)を先ほどの余り($c$)で割り、余り($d$)を求める。
$$d=b\pmod{c}$$ - これを余りが0になるまで繰り返し、その時の1つ前の余りが最大公約数となる。
これを実際に、798と91で計算してみます。次の表の様に、最大公約数は7であることが分かります。
回数 | 割り算 | 商 | 余り |
1 | 798 ÷ 91 | 8 | 70 |
2 | 91 ÷ 70 | 1 | 21 |
3 | 70 ÷ 21 | 3 | 7 |
4 | 21 ÷ 7 | 3 | 0 |
ユークリッド互除法のポイントは以下の通りで、
- 余りは割られる数の半分より小さい
- 割られる数は2つ前の余りである
これらの特徴により、高速に最大公約数を求めることができます。
拡張ユークリッド互除法
拡張ユークリッド互除法とは、2つの正数 $a,b$ と最大公約数 $d$ について、以下の式が成り立つ整数 $x,y$ を求めるアルゴリズムです。
$$ax+by=d -①$$
拡張ユークリッド互除法は、ユークリッド互除法の手順に次の手順が加わります。
- $x$ と $y$ の初期値を以下で設定する。
$$x_0=1 , x_1=0 , y_0=0 , y_1=1$$ - $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$$ - $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}$ | 商 | 余り |
1 | 798 ÷ 91 | 0 | 1 | 8 | 70 |
2 | 91 ÷ 70 | 1-8・0=1 | 0-8・1=-8 | 1 | 21 |
3 | 70 ÷ 21 | 0-1・1=-1 | 1-1・(-8)=9 | 3 | 7 |
4 | 21 ÷ 7 | 1-3・(-1)=4 | -8-3・9=-35 | 3 | 0 |
①式を導く
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)$$

