ユークリッド互除法
ユークリッド互除法とは、２つの正数の最大公約数を求めるアルゴリズムです。ユークリッド互除法は次の手順で行います。
- ２つの正数の $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$ $=x_{i-2}-q_{i-1}x_{i-1}$ |
$y_i$ $=y_{i-2}-q_{i-1}y_{i-1}$ |
商 $q_i$ | 余り |
| $i=0$ | － | $x_0=1$ | $y_0=0$ | － | － |
| $i=1$ | 798 ÷ 91 | $x_1=0$ | $y_1=1$ | $q_1=8$ | 70 |
| $i=2$ | 91 ÷ 70 | $x_2=x_0-q_1x_1$ ＝１－８･０＝１ |
$y_2=y_0-q_1y_1$ ＝０－８･１＝－８ |
$q_2=1$ | 21 |
| $i=3$ | 70 ÷ 21 | $x_3=x_1-q_2x_2$ ＝０－１･１＝－１ |
$y_3=y_1-q_2y_2$ ＝１－１･(-８)＝９ |
$q_3=3$ | ７ |
| $i=4$ | 21 ÷ ７ | $x_4=x_2-q_3x_3$ ＝１－３･(-１)＝４ |
$y_4=y_2-q_3y_3$ ＝－８－３･９＝－35 |
$q_4=3$ | ０ |
①式を導く
２つの正数を $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)$$$$=\left(\begin{array}{cc} ax+by \\ az+bw \end{array}\right)$$
