ユークリッド互除法
ユークリッド互除法とは、２つの正数の最大公約数を求めるアルゴリズムです。ユークリッド互除法は次の手順で行います。
- ２つの正数の $a,b$（$a\ge b$）の大きい方（$a$）を小さい方（$b$）で割り、余り（$c$）を求める。
$$c=a\pmod{b}$$ - 先ほどの割った数（$b$）を先ほどの余り（$c$）で割り、余り（$d$）を求める。
$$d=b\pmod{c}$$ - これを余りが０になるまで繰り返し、その時の１つ前の余りが最大公約数となる。
これを実際に、798と91で計算してみます。次の表の様に、最大公約数は７であることが分かります。
| 回数 | 割り算 | 商 | 余り |
| １ | 798 ÷ 91 | ８ | 70 |
| ２ | 91 ÷ 70 | １ | 21 |
| ３ | 70 ÷ 21 | ３ | ７ |
| ４ | 21 ÷ ７ | ３ | ０ |
ユークリッド互除法のポイントは以下の通りで、
- 余りは割られる数の半分より小さい
- 割られる数は２つ前の余りである
これらの特徴により、高速に最大公約数を求めることができます。
拡張ユークリッド互除法
拡張ユークリッド互除法とは、２つの正数 $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}$ | 商 | 余り |
| １ | 798 ÷ 91 | ０ | １ | ８ | 70 |
| ２ | 91 ÷ 70 | １－８･０＝１ | ０－８･１＝－８ | １ | 21 |
| ３ | 70 ÷ 21 | ０－１･１＝－１ | １－１･(-８)＝９ | ３ | ７ |
| ４ | 21 ÷ ７ | １－３･(-１)＝４ | －８－３･９＝－35 | ３ | ０ |
①式を導く
２つの正数を $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$ 回目で余りが０（$a_i=0$）であれば、その１つ前の余りが最大公約数（$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)$$
