ユークリッドの互除法 Javascript + D3 アニメーション
ユークリッドの互除法とは「割り算（除算）の余り（あまり）を次々に求める」を繰り返すことで「2つの自然数の最大公約数を求める」アルゴリズムです。
大きな数のときでも数回のステップで最大公約数を求めることができる強力な方法です。
このアルゴリズムは、「長方形領域を同じ大きさの正方形で埋め尽くす問題」と同値になります。
「長方形の正方形による分割問題」「正方形のタイル張りの問題」と言い換えてもよいです。
この問題を可視化したものが以下のプログラムになります。
図の描画には Javascript の D3 ライブラリを使ってます。
図形の問題として見ることで、理解がより深まりますので様々な数値の設定でやってみてください。
- a と b の欄に1以上の自分の好きな自然数を入れて[セット]ボタンを押してください
- [次のステップ]ボタンを押すごとに互除法のステップを1ずつ進めます
- [最終結果]ボタンを押すとタイル張りの埋め尽くしが完了します
- 白枠に計算と図の説明が出るので見比べてください
- 埋め尽くすための正方形の数があまりにも多いとき、最後のタイル張りは実行しません
- 最終結果が出たら、a と b の数値のセットに戻ります
- 画像 on/off のチェックを外してセットすると、図を表示しなくなります
(6596, 3400), (5130, 2340), (3355, 2379), (1071, 1029), (1649, 221), (969, 357) 等、色々な数の組をセットして試してみてください。
自分で適当に設定すると最大公約数が1になってしまう場合が多いので問題集など参考にしたり、後の解説を読んで逆算して設定してみるとよいでしょう。
ある数の約数（divisor）とは、その数を割り切る数のことです。
例えば $12$ という数を考えてみましょう。
\begin{align*}
& 12 \div 1 = 12,\quad 12 \div 2 = 6,\quad 12 \div 3 = 4,\quad 12 \div 4 = 3,\quad 12 \div 6 = 2,\quad 12 \div 12 = 12 \\
& 12 \mbox{ の約数は } \{1, 2, 3, 4, 6, 12\}
\end{align*}
上のように $12$ を割ったときに余りが出ない数（$12$ を割り切る数）が $12$ の約数です。
公約数（common divisor）とは、共通の約数のことです。
例えば $12$ と $30$ について考えてみましょう。
\begin{align*}
& 12 \mbox{ の約数は } \{1, 2, 3, 4, 6, 12\} \\
& 30 \mbox{ の約数は } \{1, 2, 3, 5, 6, 10, 15, 30\} \\
& 12 \mbox{ と } 30 \mbox{ の公約数は } \{1, 2, 3, 6\}
\end{align*}
上のように $12$ の約数と $30$ の約数の両方に入っている数が $12$ と $30$ の公約数です。
最大公約数（greatest common divisor）とは、公約数の中で最大の数です。
例えば $12$ と $30$ について考えてみましょう。
\begin{align*}
& 12 \mbox{と} 30 \mbox{ の公約数は } \{1, 2, 3, 6\} \\
& 12 \mbox{と} 30 \mbox{ の最大公約数は } 6
\end{align*}
約数や公約数や最大公約数を見つけるには、割り切る数を手探りで探すのが単純な方法です。
数が小さいうちは手探りでもなんとかなるのですが、大きな数になってくると大変な作業になってきます。
どんな大きな数に対してでも「最大公約数を少ない手順で求めるアルゴリズム」がユークリッドの互除法です。
ユークリッド（Euclid）は紀元前3世紀頃の古代ギリシャ文化のアレクサンドリア（現エジプト）の数学者です。
ギリシャ語読みではエウクレイデスといいます。
「原論」という著書にユークリッドの互除法を記しています。
「互いに素」という言い回しがありまして、なかなかとっつきにくいのですが、慣れてくると非常に便利な言葉です。
公約数が $1$ のみである数の組のことを互いに素（coprime, relative prime）といいます。
公約数が $1$ のみなので最大公約数も $1$ になります。
例えば $12$ と $55$ について考えてみましょう。
\begin{align*}
& 12 \mbox{ の約数は } \{1, 2, 3, 4, 6, 12\} \\
& 55 \mbox{ の約数は } \{1, 5, 11, 55\} \\
& 12 \mbox{ と } 55 \mbox{ の公約数は } \{1\}
\end{align*}
上のように $12$ の約数と $55$ の約数の両方に入ってる数は $1$ しかありません。
このとき「$12$ と $55$ は互いに素である」といいます。
互いに素である2数で分数を構成すると、これ以上約分できない既約分数になります。
例えば $\frac{12}{55}$ という分数はこれ以上約分できません。
互いに素でない2数で分数を構成すると、最大公約数で約分できます。
例えば $\frac{12}{30}$ という分数は $12$ と $30$ の最大公約数 $6$ で約分できて、$\frac{2}{5}$ になります。
素因数分解に関しては（ここ）でも詳しく説明してますので参考にしてください。
素数とは、自分自身と $1$ のみを約数に持つ数です。
ただし、$1$ は素数ではありません。
$2, 3, 5, 7, \ldots $ 等が素数で、無限にあります。
2以上の全ての自然数は一通りの素数の積で表すことができます。
このことを素因数分解といいます。
$12$ という数を素因数分解すると次のようになります。
\begin{align*}
12 = 2\cdot 2\cdot 3
\end{align*}
素数の $2$ や $3$ を元に、掛け算で $12$ を合成するイメージです。
合成元の素数 $2$ や $3$ のことを素因数といいます。
$12$ の約数 $\{1, 2, 3, 4, 6, 12\}$ は $12$ の素因数から、素数を取り出して掛け算で合成することで作り出せます。
\begin{align*}
1 & & &\mbox{素因数を一つも取り出さずに合成} \\
2 & & &\mbox{素因数から} 2 \mbox{ を一つ取り出して合成} \\
3 & & &\mbox{素因数から} 3 \mbox{ を一つ取り出して合成} \\
4 &=2\cdot 2 & &\mbox{素因数から } 2 \mbox{ を二つ取り出して合成} \\
6 &=2\cdot 3 & &\mbox{素因数から } 2 \mbox{ を一つ } 3 \mbox{ を一つ取り出して合成} \\
12 &=2\cdot 2\cdot 3 & &\mbox{素因数から } 2 \mbox{ を二つ } 3 \mbox{ を一つ取り出して合成}
\end{align*}
$12$ と $30$ から公約数である $2$ を取り出して以下のように分解してみましょう。
\begin{align*}
12 &= 6\cdot 2 \\
30 &= 15\cdot 2
\end{align*}
$12$ を $2$ で割ると $6$ が商として残ります。
$30$ を $2$ で割ると $15$ が商として残ります。
この残った $6$ と $15$ の公約数を調べてみます。
\begin{align*}
&6 \mbox{ の約数 } \{1, 2, 3, 6\} \\
&15 \mbox{ の約数 } \{1, 3, 5, 15\} \\
&6 \mbox{ と } 15 \mbox{ の公約数 } \{1, 3\}
\end{align*}
$6$ と $15$ には $1$ 以外の公約数があるので、互いに素ではないことが分かりました。
$12$ と $30$ から公約数である $3$ を取り出して以下のように分解してみましょう。
\begin{align*}
12 &= 4\cdot 3 \\
30 &= 10\cdot 3
\end{align*}
$12$ を $3$ で割ると $4$ が商として残ります。
$30$ を $3$ を割ると $10$ が商として残ります。
この残った $4$ と $10$ の公約数を調べてみます。
\begin{align*}
&4 \mbox{ の約数 } \{1, 2, 4\} \\
&10 \mbox{ の約数 } \{1, 2, 5, 10\} \\
&4 \mbox{ と } 10 \mbox{ の公約数 } \{1, 2\}
\end{align*}
$4$ と $10$ には $1$ 以外の公約数があるので、互いに素ではないことが分かりました。
$12$ と $30$ から最大公約数である $6$ を取り出して以下のように分解してみましょう。
\begin{align*}
12 &= 2\cdot 6 \\
30 &= 5\cdot 6
\end{align*}
$12$ を $6$ で割ると $2$ が商として残ります。
$30$ を $6$ で割ると $5$ が商として残ります。
この残った $2$ と $5$ の公約数を調べてみます。
\begin{align*}
&2 \mbox{ の約数 } \{1, 2\} \\
&5 \mbox{ の約数 } \{1, 5\} \\
&2 \mbox{ と } 5 \mbox{ の公約数 } \{1\}
\end{align*}
$2$ と $5$ には $1$ 以外の公約数がないので、互いに素であることが分かりました。
$12$ と $30$ を一般化して $a, b$ とすると、次のようになります。
二つの数 $a$ と $b$ を公約数の $d$ で次のように分解する。
\begin{align*}
a &= pd \\
b &= qd
\end{align*}
このとき次の性質が成り立ちます。
\begin{align*}
&d \mbox{ が最大公約数なら } & & p \mbox{ と } q \mbox{ は互いに素である} \\
&d \mbox{ が最大じゃない公約数なら } & & p \mbox{ と } q \mbox{ は互いに素ではない}
\end{align*}
これは、逆も成り立ちます。
\begin{align*}
& p \mbox{ と } q \mbox{ が互いに素であるなら} & & d \mbox{ は最大公約数である}\\
& p \mbox{ と } q \mbox{ が互いに素でないなら} & & d \mbox{ は最大じゃない公約数である}\\
\end{align*}
$12$ と $30$ の例をもう一度見てみましょう。
まずは、素因数分解してみます。
\begin{align*}
12 &= 2\cdot 2\cdot 3 \\
30 &= 2\cdot 3\cdot 5
\end{align*}
最大じゃない公約数 $2$ を取り出してみます。
\begin{align*}
12 &= (2\cdot 3)\cdot (2) = 6\cdot 2 \\
30 &= (3\cdot 5)\cdot (2) = 15\cdot 2
\end{align*}
$6$ と $15$ には共通の素因数の $3$ があるので互いに素ではないことが分かります。
最大じゃない公約数 $3$ を取り出してみます。
\begin{align*}
12 &= (2\cdot 2)\cdot (3) = 4\cdot 3 \\
30 &= (2\cdot 5)\cdot (3) = 10\cdot 3
\end{align*}
$4$ と $10$ には共通の素因数の $2$ があるので互いに素ではないことが分かります。
最大公約数 $6$ を取り出してみます。
\begin{align*}
12 &= (2)\cdot (2\cdot 3) = 2\cdot 6 \\
30 &= (5)\cdot (2\cdot 3) = 5\cdot 6
\end{align*}
$2$ と $5$ には共通の素因数がないので互いに素であることが分かります。
最後に $126$ と $420$ を素因数分解することで、最大公約数を求める例題をやってみましょう。
まずは素因数分解です。
\begin{align*}
126 &= 2\cdot 3\cdot 3\cdot 7 \\
420 &= 2\cdot 2\cdot 3\cdot 5\cdot 7
\end{align*}
共通素因数を最大限取り出します。
\begin{align*}
126 &=& (3)\cdot (2\cdot 3\cdot 7) &=& 3\cdot 42 \\
420 &=& (2\cdot 5)\cdot (2\cdot 3\cdot 7) &=& 10\cdot 42
\end{align*}
最大公約数は $42$, 最大公約数を除いた $3$ と $10$ は互いに素になります。
素因数分解は、数を分析する強力な武器です。
ただし、大きな数になると素因数を見つけることが大変困難になります。
しらみつぶしに探していくことになり非常に効率が悪いです。
大きな数の最大公約数を見つけるには、ユークリッドの互除法が最強の武器になります。
ぜひともアルゴリズムを習得してください。
ユークリッドの互除法は、一手前の割る数を、一手前の余りで割る、を余りが $0$ になるまで続けるアルゴリズムです。
以下の手順で筆算を、手を動かしてやってみると、そのアルゴリズムの概要がつかめてきます。
例として $2013$ と $1159$ の最大公約数を求めてみましょう。
[第1ステップ] $2013\div 1159$ の筆算を実行します。
その際、左側には大きく空きスペースを取っておいてください。
（後の節での説明の為に、割られる数を $2013=a=r_0$ の記号で、 割る数を $1159=b=r_1$ の記号でおいておきます。）
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& & & & & \\[-3pt]
\phantom{61}&\phantom{\enclose{longdiv}{244}}&\phantom{\enclose{longdiv}{305}}&\phantom{\enclose{longdiv}{859}}& 1159&\enclose{longdiv}{2013}\\[-3pt]
& & & &\phantom{\enclose{longdiv}{1159}}& \\[-3pt]
& & & & & \\[-3pt]
\end{array}
\end{align*}
筆算の結果、商 $1$ と、余り $859$ が求まりました。
（後の節での説明の為に、商を $1=q_1$ の記号で、 余りを $859=r_2$ の記号でおいておきます。）
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& & & & & 1 \\[-3pt]
\phantom{61}&\phantom{\enclose{longdiv}{244}}&\phantom{\enclose{longdiv}{305}}&\phantom{\enclose{longdiv}{859}}& 1159&\enclose{longdiv}{2013}\\[-3pt]
& & & &\phantom{\enclose{longdiv}{1159}}& \underline{1159}\\[-3pt]
& & & & & 859 \\[-3pt]
\end{array}
\end{align*}
[第2ステップ] 一手前の割る数 $1159$ を、一手前の余り $\color{red}{859}$ で割ります。 $1159\div \color{red}{859}$ の割り算の筆算を左に繋げて実行しましょう。
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& & & & & 1 \\[-3pt]
\phantom{61}&\phantom{\enclose{longdiv}{244}}&\phantom{\enclose{longdiv}{305}}& \color{red}{859}&\enclose{longdiv}{1159}&\enclose{longdiv}{2013}\\[-3pt]
& & &\phantom{\enclose{longdiv}{859}}& & \underline{1159}\\[-3pt]
& & & & & \color{red}{859}\\[-3pt]
\end{array}
\end{align*}
筆算の結果、商 $1$ と、余り $305$ が求まりました。
（後の節での説明の為に、商を $1=q_2$ の記号で、 余りを $305=r_3$ の記号でおいておきます。）
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& & & & 1 & 1 \\[-3pt]
\phantom{61}&\phantom{\enclose{longdiv}{244}}&\phantom{\enclose{longdiv}{305}}& 859&\enclose{longdiv}{1159}&\enclose{longdiv}{2013}\\[-3pt]
& & &\phantom{\enclose{longdiv}{859}}& \underline{854}& \underline{1159}\\[-3pt]
& & & & 305 & 859 \\[-3pt]
\end{array}
\end{align*}
[第3ステップ] 一手前の割る数 $859$ を、一手前の余り $\color{red}{305}$ で割ります。 $859\div \color{red}{305}$ の割り算の筆算を左に繋げて実行します。
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& & & & 1 & 1 \\[-3pt]
\phantom{61}&\phantom{\enclose{longdiv}{244}}& \color{red}{305}&\enclose{longdiv}{859}&\enclose{longdiv}{1159}&\enclose{longdiv}{2013}\\[-3pt]
& &\phantom{\enclose{longdiv}{305}}& & \underline{854}& \underline{1159}\\[-3pt]
& & & & \color{red}{305}& 859 \\[-3pt]
\end{array}
\end{align*}
筆算の結果、商 $2$ と、余り $244$ が求まりました。
（後の節での説明の為に、商を $2=q_3$ の記号で、 余りを $244=r_4$ の記号でおいておきます。）
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& & & 2 & 1 & 1 \\[-3pt]
\phantom{61}&\phantom{\enclose{longdiv}{244}}& 305&\enclose{longdiv}{859}&\enclose{longdiv}{1159}&\enclose{longdiv}{2013}\\[-3pt]
& &\phantom{\enclose{longdiv}{305}}& \underline{610}& \underline{854}& \underline{1159}\\[-3pt]
& & & 244 & 305 & 859 \\[-3pt]
\end{array}
\end{align*}
[第4ステップ] 一手前の割る数 $305$ を、一手前の余り $\color{red}{244}$ で割ります。 $305\div \color{red}{244}$ の割り算の筆算を左に繋げて実行しましょう。
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& & & 2 & 1 & 1 \\[-3pt]
\phantom{61}& \color{red}{244}&\enclose{longdiv}{305}&\enclose{longdiv}{859}&\enclose{longdiv}{1159}&\enclose{longdiv}{2013}\\[-3pt]
&\phantom{\enclose{longdiv}{244}}& & \underline{610}& \underline{854}& \underline{1159}\\[-3pt]
& & & \color{red}{244}& 305 & 859 \\[-3pt]
\end{array}
\end{align*}
筆算の結果、商 $1$ と、余り $61$ が求まりました。
（後の節での説明の為に、商を $1=q_4$ の記号で、 余りを $61=r_5$ の記号でおいておきます。）
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& & 1 & 2 & 1 & 1 \\[-3pt]
\phantom{61}& 244&\enclose{longdiv}{305}&\enclose{longdiv}{859}&\enclose{longdiv}{1159}&\enclose{longdiv}{2013}\\[-3pt]
&\phantom{\enclose{longdiv}{244}}& \underline{244}& \underline{610}& \underline{854}& \underline{1159}\\[-3pt]
& & 61 & 244 & 305 & 859 \\[-3pt]
\end{array}
\end{align*}
[第5ステップ] 一手前の割る数 $244$ を、一手前の余り $\color{red}{61}$ で割ります。 $244\div \color{red}{61}$ の割り算の筆算を左に繋げて実行しましょう。
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& & 1 & 2 & 1 & 1 \\[-3pt]
\color{red}{61}&\enclose{longdiv}{244}&\enclose{longdiv}{305}&\enclose{longdiv}{859}&\enclose{longdiv}{1159}&\enclose{longdiv}{2013}\\[-3pt]
& & \underline{244}& \underline{610}& \underline{854}& \underline{1159}\\[-3pt]
& & \color{red}{61}& 244 & 305 & 859 \\[-3pt]
\end{array}
\end{align*}
筆算の結果、商 $4$ と、余り $\color{blue}{0}$ が求まりました。
後の節での説明の為に商を $4=q_5$ の記号で表しておきます。
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& 4 & 1 & 2 & 1 & 1 \\[-3pt]
\color{blue}{61}&\enclose{longdiv}{244}&\enclose{longdiv}{305}&\enclose{longdiv}{859}&\enclose{longdiv}{1159}&\enclose{longdiv}{2013}\\[-3pt]
& \underline{244}& \underline{244}& \underline{610}& \underline{854}& \underline{1159}\\[-3pt]
& \color{blue}{0}& 61& 244 & 305 & 859 \\[-3pt]
\end{array}
\end{align*}
余りが $\color{blue}{0}$ になったのでここで終了です。この時の割る数 $\color{blue}{61}$ が $2013$ と $1159$ の最大公約数になります。
最終結果、$\color{blue}{61}$ が $2013$ と $1159$ の最大公約数になることが分かります。第5ステップで終了になります。
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& 4 & 1 & 2 & 1 & 1 \\[-3pt]
\color{blue}{61}&\enclose{longdiv}{244}&\enclose{longdiv}{305}&\enclose{longdiv}{859}&\enclose{longdiv}{1159}&\enclose{longdiv}{2013}\\[-3pt]
& \underline{244}& \underline{244}& \underline{610}& \underline{854}& \underline{1159}\\[-3pt]
& \color{blue}{0}& 61& 244 & 305 & 859 \\[-3pt]
\end{array}
\end{align*}
後の節での議論と比較する為に、つぎのような記号を導入して書き換えておきます。
\begin{align*}
\require{enclose}
\begin{array}{rrrrrr}
& q_5 & q_4 & q_3 & q_2 & q_1 \\[-3pt]
\color{blue}{r_5}&\enclose{longdiv}{\quad r_4}&\enclose{longdiv}{\quad r_3}&\enclose{longdiv}{\quad r_2}&\enclose{longdiv}{\quad r_1}&\enclose{longdiv}{\quad r_0}\\[-3pt]
& \underline{q_5r_5}& \underline{q_4r_4}& \underline{q_3r_3}& \underline{q_2r_2}& \underline{q_1r_1}\\[-3pt]
& \color{blue}{0}& r_5 & r_4 & r_3 & r_2 \\[-3pt]
\end{array}
\end{align*}
例題として、$a = 2013$ と $b = 1159$ の最大公約数を求めてみましょう。
ステップごとに割り算の商（quatient）と余り（reminder）を求めていきます。
$r_0 = a = 2013,\, r_1 = b = 1159$ とします。
[第1ステップ] まず、$r_0 \div r_1$ の商 $q_1$ と 余り $r_2$ を求めましょう。
\begin{align*}
2013 \div 1159 = 1 \,\mbox{余り}\, 854 \tag{1}
\end{align*}
なので $q_1 = 1, r_2 = 854$ になります。
[第2ステップ] 次に、$r_1 \div r_2$ の商 $q_2$ と 余り $r_3$ を求めましょう。
\begin{align*}
1159 \div 854 = 1 \,\mbox{余り}\, 305 \tag{2}
\end{align*}
なので $q_2 = 1, r_3 = 305$ になります。
[第3ステップ] 次に、$r_2 \div r_3$ の商 $q_3$ と 余り $r_4$ を求めましょう。
\begin{align*}
854 \div 305 = 2 \,\mbox{余り}\, 244 \tag{3}
\end{align*}
なので $q_3 = 2, r_4 = 244$ になります。
[第4ステップ] 次に、$r_3 \div r_4$ の商 $q_4$ と 余り $r_5$ を求めましょう。
\begin{align*}
305 \div 244 = 1 \,\mbox{余り}\, 61 \tag{4}
\end{align*}
なので $q_4 = 1, r_5 = 61$ になります。
[第5ステップ] 次に、$r_4 \div r_5$ の商 $q_5$ と 余り $r_6$ を求めましょう。
\begin{align*}
244 \div 61 = 4 \,\mbox{余り}\, 0 \tag{5}
\end{align*}
なので $q_5 = 4, r_6 = 0$ になります。
余りが $0$ になったのでここで終了です。
$r_2, r_3. \ldots$ の最後の割る数の $r_5 = 61$ が $a=r_0$ と $b=r_1$ の最大公約数になります。
$r_5 = 61$ は $0$ じゃない最後の余りと考えても差し支えありません。
公約数になる理由は、$(1), (2), (3), (4), (5)$ の関係式を逆に解いていけば分かります。
$(5)$ 式から次の関係式「$244$ は $61$ の $4$ 倍の数」が分かります。
\begin{align*}
244 = 4\cdot 61 \tag{5'}
\end{align*}
$(4)$ 式から次の関係式「$305$ は $244$ の $1$ 倍に $61$ を加えた数」が分かります。
\begin{align*}
305 = 1\cdot 244 + 61 \tag{4'}
\end{align*}
$(4')$ 式の右辺に $(5')$ 式の「$244$ は $61$ の $4$ 倍」を代入して整理すると 、「$305$ は $61$ の $5$ 倍の数」だと分かります。
\begin{align*}
305 = 1\cdot 4\cdot 61 + 61 = (4 + 1)\cdot 61 = 5\cdot 61 \tag{4''}
\end{align*}
$(3)$ 式から次の関係式「$854$ は $305$ の $2$ 倍に $244$ を加えた数」が分かります。
\begin{align*}
854 = 2\cdot 305 + 244 \tag{3'}
\end{align*}
$(3')$ 式の右辺に$(4'')$ 式の「$305$ は $61$ の $5$ 倍の数」と、$(5')$ 式の「$244$ は $61$ の $4$ 倍の数」代入して整理すると、「$854$ が $61$ の $14$ 倍の数」だと分かります。
\begin{align*}
854 = 2\cdot 5\cdot 61 + 4\cdot 61 = (10 + 4)\cdot 61 = 14\cdot 61 \tag{3''}
\end{align*}
$(2)$ 式から次の関係式「$1159$ は $854$ の $1$ 倍に $305$ を加えた数」が分かります。
\begin{align*}
1159 = 1\cdot 854 + 305 \tag{2'}
\end{align*}
$(2')$ 式の右辺に $(3'')$ 式の「$854$ は $61$ の $14$ 倍の数」と $(4'')$ 式の「$301$ は $61$ の $5$ 倍の数」代入して整理しますと、「$1159$ が $61$ の $19$ 倍の数」だと分かります。
\begin{align*}
1159 = 1\cdot 14\cdot 61 + 5\cdot 61 = (14 + 5)\cdot 61 = 19\cdot 61 \tag{2''}
\end{align*}
$(1)$ 式から次の関係式「$2013$ は $1159$ の $1$ 倍に $854$ を加えた数」が分かります。
\begin{align*}
2013 = 1\cdot 1159 + 854 \tag{1'}
\end{align*}
$(1')$ 式の右辺に $(2'')$ 式の「$1159$ は $61$ の $19$ 倍の数」と $(3'')$ 式の「$854$ は $61$ の $14$ 倍の数」代入して整理しますと、「$2013$ が $61$ の $33$ 倍の数」だと分かります。
\begin{align*}
2013 = 1\cdot 19\cdot 61 + 14\cdot 61 = (19 + 14)\cdot 61 = 33\cdot 61 \tag{1''}
\end{align*}
上記結果をまとめます。
\begin{align*}
2013 &= 1\cdot 1159 + 854 \tag{1'} \\
1159 &= 1\cdot 854 + 305 \tag{2'} \\
854 &= 2\cdot 305 + 244 \tag{3'} \\
305 &= 1\cdot 244 + 61 \tag{4'} \\
244 &= 4\cdot 61 \tag{5'}
\end{align*}
から以下の関係を求めました。
\begin{align*}
244 &= 4\cdot 61 \tag{5'} \\
305 &= 5\cdot 61 \tag{4''} \\
854 &= 14\cdot 61 \tag{3''} \\
1159 &= 19\cdot 61 \tag{2''} \\
2013 &= 33\cdot 61 \tag{1''}
\end{align*}
[最終結果] $(1'')$ 式と $(2'')$ 式から $61$ が $2013 = 33\cdot 61$ と $1159 = 19\cdot 61$ の公約数であることが分かります。
実は $33$ と $19$ は互いに素（公約数が $1$ のみ）です。上のタイル張りのアニメで $(33, 19)$ をセットして確かめてみてくさい。
互いに素のため $33$ と $19$ には、これ以上共通の約数が存在しないので $61$ が $2013$ と $1159$ の最大公約数であることが分かります。
ユークリッドの互除法で得られた公約数がいつでも最大公約数になるのは、得られた公約数を除いた残りの部分が必ず互いに素になるからです。
必ず互いに素になる理由は先ほどの計算を記号で実行してみると分かります。
$(1'), (2'), (3'), (4'), (5')$ 式を記号で書くと次のようになります。
記号で表すことで、数値に関係なく5ステップで終了するパターンの全てを扱っていることになります。
\begin{align*}
a = r_0 &= q_1 r_1 + r_2 \tag{1'} \\
b = r_1 &= q_2 r_2 + r_3 \tag{2'} \\
r_2 &= q_3 r_3 + r_4 \tag{3'} \\
r_3 &= q_4 r_4 + r_5 \tag{4'} \\
r_4 &= q_5 r_5 \tag{5'}
\end{align*}
ここで $q_5$ は $1$ ではない数になります。
なぜなら $q_5$ が $1$ だとしたら $(5')$ 式より $r_4 = r_5$ となるので、$(4')$ の時点で $r_3 = (q_4+1) r_4$ になります。
つまり、「ひとつ前のステップで商が $q_4+1$ に、余りが $0$ になっていて終了していたはずだ」、ということになってしまいます。
このことを上のタイル張りの問題でいうと、「最終ステップで、正方形 $1$ 個だけで埋め尽くすということはありえない」ということに対応します。
「最終ステップが正方形 $1$ 個だけで埋め尽くすとしたら、その前のステップで埋め尽くしが終了していたはずだ」ということです。
「最終ステップでは必ず $2$ 個以上の正方形で埋め尽くす」ことになります。
いろんな数値で試してみてください。
$(1')$ から $(5')$ までの関係式を $q_5 \neq 1$ の条件で下から解いていきましょう。
まず、$(5')$ 式を $(4')$ 式に代入して整理すると次の式になります。
\begin{align*}
r_3 = q_4 q_5 r_5 + r_5 = (q_4 q_5 + 1) r_5 = Q_4 r_5 \tag{4''}
\end{align*}
この最後の式で次のように $Q_4$ を定義しました。
\begin{align*}
Q_4\equiv q_4 q_5 + 1
\end{align*}
ここで $q_5$ は $1$ ではないので $Q_4$ を $q_5$ の $1$ 以外の約数で割ろうとすると、$q_4 q_5$ の部分は割り切れますが、$1$ の部分は割り切れません。
そのため $q_5$ と $Q_4$ は互いに素（$1$ 以外の共通の約数を持たない）ということが分かり、次のようにまとまります。
\begin{align*}
r_3 &= Q_4 r_5 \tag{4''} \\
r_4 &= q_5 r_5 \tag{5'} \\
\end{align*}
$Q_4$ と $q_5$ は互いに素
次に、$(4'')$ 式と $(5')$ 式を $(3')$ 式に代入して整理すると次の式になります。
\begin{align*}
r_2 = q_3 Q_4 r_5 + q_6 r_5 = (q_3 Q_4 + q_5) r_5 = Q_3 r_5 \tag{3''}
\end{align*}
この最後の式で次のように $Q_3$ を定義しました。
\begin{align*}
Q_3\equiv q_3 Q_4 + q_5
\end{align*}
ここで、$Q_4$ と $q_5$ は 互いに素で $1$ 以外の共通の約数を持たないので、$Q_3$ を $Q_4$ の $1$ 以外の約数で割ろうとすると、$q_3 Q_4$ の部分は割り切れますが、$q_5$ の部分は割り切れません。
そのため $Q_4$ と $Q_3$ は互いに素（$1$ 以外の共通の約数を持たない）ということが分かり、次のようにまとまります。
\begin{align*}
r_2 &= Q_3 r_5 \tag{3''} \\
r_3 &= Q_4 r_5 \tag{4''} \\
\end{align*}
$Q_3$ と $Q_4$ は互いに素
次に、$(3'')$ 式と $(4'')$ 式を $(2')$ 式に代入して整理すると次の式になります。
\begin{align*}
r_1 = q_2 Q_3 r_5 + Q_4 r_5 = (q_2 Q_3 + Q_4) r_5 = Q_2 r_5 \tag{2''}
\end{align*}
この最後の式で次のように $Q_2$ を定義しました。
\begin{align*}
Q_2\equiv q_2 Q_3 + Q_4
\end{align*}
ここで、$Q_3$ と $Q_4$は 互いに素で $1$ 以外の共通の約数を持たないので、$Q_2$ を $Q_3$ の1以外の約数で割ろうとすると、$q_2 Q_3$ の部分は割り切れますが、$Q_4$ の部分は割り切れません。
そのため $Q_3$ と $Q_2$ は互いに素（$1$ 以外の共通の約数を持たない）ということが分かり、次のようにまとまります。
\begin{align*}
r_1 &= Q_2 r_5 \tag{2''} \\
r_2 &= Q_3 r_5 \tag{3''} \\
\end{align*}
$Q_2$ と $Q_3$ は互いに素
最後に、$(2'')$ 式と $(3'')$ 式を $(1')$ 式に代入して整理すると次の式になります。
\begin{align*}
r_0 = q_1 Q_2 r_5 + Q_3 r_5 = (q_1 Q_2 + Q_3) r_5 = Q_1 r_5 \tag{1''}
\end{align*}
この最後の式で次のように $Q_1$ を定義しました。
\begin{align*}
Q_1\equiv q_1 Q_2 + Q_3
\end{align*}
ここで、$Q_2$ と $Q_3$ は 互いに素で $1$ 以外の共通の約数を持たないので、$Q_1$ を $Q_2$ の $1$ 以外の約数で割ろうとすると、$q_1 Q_2$ の部分は割り切れますが、$Q_3$ の部分は割り切れません。
そのため $Q_2$ と $Q_1$ は互いに素（$1$ 以外の共通の約数を持たない）ということが分かり、次のようにまとまります。
\begin{align*}
r_0 &= Q_1 r_5 \tag{1''} \\
r_1 &= Q_2 r_5 \tag{2''} \\
\end{align*}
$Q_1$ と $Q_2$ は互いに素
この結果 $r_5$ が $a = r_0$ と $b = r_1$ の最大公約数であることが分かります。
まとめると $(1'), (2'), (3'), (4'), (5')$ 式から次の関係式を求めたことになります。
\begin{align*}
r_4 &= q_5 r_5, \qquad q_5 \neq 1 \tag{5'} \\
r_3 &= Q_4 r_5, \qquad Q_4\equiv q_4 q_5 + 1 \tag{4''} \\
r_2 &= Q_3 r_5, \qquad Q_3\equiv q_3 Q_4 + q_5 \tag{3''} \\
b = r_1 &= Q_2 r_5, \qquad Q_2\equiv q_2 Q_3 + Q_4 \tag{2''} \\
a = r_0 &= Q_1 r_5, \qquad Q_1\equiv q_1 Q_2 + Q_3 \tag{1''} \\
\end{align*}
$q_5, Q_4, Q_3, Q_2, Q_1$ は、全て互いに素
$r_5$ が $r_4, r_3, r_2, r_1, r_0$ の最大公約数
今回の例では第5ステップで余りが $0$ になり、$r_5$ が最大公約数になったわけですが、第6ステップで余りが $0$ になった場合は、$r_6$ が最大公約数になるわけです。
ユークリッドの互除法は有限回のステップで余りが0になり終了することが証明できます。
どんな値の $a, b$ でも、有限回のステップで最大公約数が必ず得られる強力なアルゴリズムがユークリッドの互除法というわけです。
共通因数を探す方法はトライアンドエラーが多すぎて、手計算ではとてもやってられません。
仕組みが分かってしまえば、問題作成が可能になります。
6 回ステップで終了する問題を考えてみましょう。
\begin{align*}
a = r_0 &= q_1 r_1 + r_2 \\
b = r_1 &= q_2 r_2 + r_3 \\
r_2 &= q_3 r_3 + r_4 \\
r_3 &= q_4 r_4 + r_5 \\
r_4 &= q_5 r_5 + r_6 \\
r_5 &= q_6 r_6
\end{align*}
$r_6$ には最大公約数にしたい数を、$q_6, q_5, q_4, q_3, q_2, q_1$ にはタイル張りの各ステップでの正方形の枚数にしたい数を設定します。
設定した数を使って $r_5, r_4, r_3, r_2, b=r_1, a=r_0$ を順次求めていきます。
$r_6 = 36, q_6 = 3, q_5 = 2, q_4 = 1, q_3 = 2, q_2 = 2, q_1 = 1$ に設定
\begin{align*}
r_5 &= 3\cdot 36 = 108 \\
r_4 &= 2\cdot 108 + 36 = 216 + 36 = 252 \\
r_3 &= 1\cdot 252 + 108 = 360 \\
r_2 &= 2\cdot 360 + 252 = 720 + 252 = 972 \\
b = r_1 &= 2\cdot 972 + 360 = 1944 + 360 = 2304 \\
a = r_0 &= 1\cdot 2304 + 972 = 3276
\end{align*}
$(3276, 2304)$ の組や、$(2304, 972)$ の組をセットしてタイル張りのアニメーションを実行してみましょう。
証明は抽象的に見えますが、ここまで具体例を見てきた人は納得できると思います。
先ずは次の定理を証明します。
$a, b, q, r$ が整数で、関係式
\begin{align*}
a = qb + r
\end{align*}
が成り立つとき
$a$ と $b$ の最大公約数と、$b$ と $r$ の最大公約数は一致する。
この関係式には $q$ と $r$ の文字を使っていますが、商や余りには関係しません。
どのような整数（正負の数やゼロ）に対してでも成り立つ関係式です。
例えば、$a=18, q=2, b=-12, r=42$ とすると
$18 = 2\cdot (-12) + 42$
が成り立ちます。
このとき、$a, b$ の最大公約数 $6$ と、$b, r$ の最大公約数 $6$ は一致します。
それでは証明していきましょう。
$a$ と $b$ の最大公約数を $k$ と置き、
$b$ と $r$ の最大公約数を $l$ と置く。
$b$ と $r$ は $l$ の倍数なので
\begin{align*}
a = qb + r
\end{align*}
の右辺は $l$ の倍数になる。
よって、左辺の $a$ は $l$ を約数に持つことが分かる。
すなわち、$l$ は $a$ と $b$ の公約数である。
$a$ と $b$ の公約数で最大の数が最大公約数なので
\begin{align*}
k\ge l
\end{align*}
の関係が成り立つ。
次に、$a$ と $b$ は $k$ の倍数なので
\begin{align*}
r = a - qb
\end{align*}
の右辺は $k$ の倍数になる。
よって、左辺の $r$ は $k$ を約数に持つことが分かる。
すなわち、$k$ は $r$ と $b$ の公約数である。
$r$ と $b$ の公約数で最大の数が最大公約数なので
\begin{align*}
l\ge k
\end{align*}
の関係が成り立つ。
関係式 $k\ge l$ と $l\ge k$ が両方同時に成り立つためには
\begin{align*}
k = l
\end{align*}
が成り立つほかない。
よって $a, b$ の最大公約数 $k$ と $b, r$ の最大公約数 $l$ が一致することが示された。
この定理を割り算の商と余りに適用します。
$a$ を割られる数、$b$ を割る数、$q$ を商、$r$ を余りとします。
整数 $a, b, q, r$ ただし $0\le r \lt b$ に
\begin{align*}
a = qb + r
\end{align*}
の関係が成り立つとき
$a$ と $b$ の最大公約数と、$b$ と $r$ の最大公約数は一致する。
この余りの $r$ が割る数 $b$ より必ず小さくなることがポイントです。
このステップを次々と続けていきますと、余りの部分がどんどん小さくなっていって、互除法の有限のステップで余りが $0$ になるしかなくなります。
定理を次の記号で書き直します。
整数 $r_{k-1},\, r_k,\, q_k,\, r_{k+1}$ ただし $0 \le r_{k+1} \lt r_k \lt r_{k-1}$ に
\begin{align*}
r_{k-1} = q_k r_k + r_{k+1}
\end{align*}
の関係が成り立つとき
$r_{k-1}$ と $r_k$ の最大公約数と、$r_k$ と $r_{k+1}$ の最大公約数は一致する。
上記の $r_{k-1}\div r_k$ の割り算から得られる関係式を、余りが $0$ になる $n$ 回ステップまで続けると、次のように $r_n$ が $a, b$ の最大公約数になることが証明されます。
\begin{align*}
a = r_0 &= q_1r_1 + r_2, \quad (0\lt r_2 \lt r_1 = b) \\
b = r_1 &= q_2r_2 + r_3, \quad (0\lt r_3 \lt r_2) \\
r_2 &= q_3r_3 + r_4, \quad (0\lt r_4 \lt r_3) \\
r_3 &= q_4r_4 + r_5, \quad (0\lt r_5 \lt r_4) \\
&\quad \vdots \\
r_{n-2} &= q_{n-1}r_{n-1} + r_n, \quad (0\lt r_n \lt r_{n-1}) \\
r_{n-1} &= q_n r_n, \quad\quad\quad (r_{n+1}=0) \\
\end{align*}
$b = r_1\gt r_2\gt r_3\gt\cdots\gt r_{n-1}\gt r_n \gt 0$
\begin{align*}
a = r_0 \mbox{と} b = r_1 \mbox{の最大公約数}
&= r_1 \mbox{と} r_2 \mbox{の最大公約数} \\
&= r_2 \mbox{と} r_3 \mbox{の最大公約数} \\
&= r_4 \mbox{と} r_5 \mbox{の最大公約数} \\
&\quad \vdots \\
&= r_{n-1} \mbox{と} r_n \mbox{の最大公約数} \\
&= r_n \mbox{と} 0 \mbox{の最大公約数} \\
&= r_n
\end{align*}
最後の $0$ と $r_n$ の最大公約数が $r_n$ になるのは次の理由によります。
- $0$ じゃないあらゆる整数は $0$ の約数
（$0$ にはどんな数を掛けても $0$ になるので、$0$ は $0$ 以外のどんな整数で割っても割り切れる）
- $0$ を約数に持つ整数は存在しない
（どのような整数も $0$ で割ることができない）
$0$ じゃないある整数 $m\ne 0$ の最大約数は絶対値 $|m|$ で、$0$ の約数に $|m|$ が存在するので、$m$ と $0$ の最大公約数は $|m|$ になります。
ちなみに $0$ の約数はあらゆる整数なので $0$ の約数には最大のものがありません。
そのため $0$ と $0$ の最大公約数はありません。
$a=r_0=2013, b=r_1=1159$ として $a\div b=\frac{a}{b}$ を考えてみましょう。
(1')式より $2013 = 1\cdot 1159 + 854, (q_1=1, r_2=854)$ なので、次のように $\frac{2013}{1159}$ を変形できます。
\begin{align*}
\frac{2013}{1159} = \frac{1\cdot 1159 + 854}{1159}
= 1 + \frac{854}{1159}
= 1 + \cfrac{1}{\cfrac{1159}{854}} \tag{1'''}
\end{align*}
(2')式より $1159 = 1\cdot 854 + 305, (q_2=1, r_3=305)$ なので、次のように $\frac{1159}{854}$ を変形できます。
\begin{align*}
\frac{1159}{854} = \frac{1\cdot 854 + 305}{854}
= 1 + \frac{305}{854}
= 1 + \cfrac{1}{\cfrac{854}{305}} \tag{2'''}
\end{align*}
(3')式より $854 = 2\cdot 305 + 244, (q_3=2, r_4=244)$ なので、次のように $\frac{854}{305}$ を変形できます。
\begin{align*}
\frac{854}{305} = \frac{2\cdot 305 + 244}{305}
= 2 + \frac{244}{305}
= 2 + \cfrac{1}{\cfrac{305}{244}} \tag{3'''}
\end{align*}
(4')式より $305 = 1\cdot 244 + 61, (q_4=1, r_5=61)$ なので、次のように $\frac{305}{244}$ を変形できます。
\begin{align*}
\frac{305}{244} = \frac{1\cdot 244 + 61}{244}
= 1 + \frac{61}{244}
= 1 + \cfrac{1}{\cfrac{244}{61}} \tag{4'''}
\end{align*}
(5')式より $244 = 4\cdot 61, (q_5=4, r_6=0)$ なので、次のように $\frac{244}{61}$ を変形できます。
\begin{align*}
\frac{244}{61} = \frac{4\cdot 61}{61}
= 4 \tag{5'''}
\end{align*}
(5''')式を(4''')式に代入します。
\begin{align*}
\frac{305}{244} = 1 + \frac{1}{4} \tag{4''''}
\end{align*}
(4'''')式を(3''')式に代入します。
\begin{align*}
\frac{854}{305} = 2 + \cfrac{1}{1 + \cfrac{1}{4}} \tag{3''''}
\end{align*}
(3'''')式を(2''')式に代入します。
\begin{align*}
\frac{1159}{854} = 1 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{4}}} \tag{2''''}
\end{align*}
(2'''')式を(1''')式に代入します。
\begin{align*}
\frac{2013}{1159} = 1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{4}}}} \tag{1''''}
\end{align*}
(1'''')や(2'''')や(3'''')や(4'''')式のことを連分数といいます。
これを5ステップの互除法の商と余りの記号で一般化すると次のようになります。
\begin{align*}
\frac{r_4}{r_5} &= \frac{q_5r_5}{r_5}
= q_5 \tag{5'''} \\
\frac{r_3}{r_4} &= \frac{q_4r_4 + r_5}{r_4}
= q_4 + \frac{r_5}{r_4}
= q_4 + \cfrac{1}{\cfrac{r_4}{r_5}}
= q_4 + \cfrac{1}{q_5} \tag{4''''} \\
\frac{r_2}{r_3} &= \frac{q_3r_3 + r_4}{r_3}
= q_3 + \frac{r_4}{r_3}
= q_3 + \cfrac{1}{\cfrac{r_3}{r_4}}
= q_3 + \cfrac{1}{q_4 + \cfrac{1}{q_5}} \tag{3''''} \\
\frac{r_1}{r_2} &= \frac{q_2r_2 + r_3}{r_2}
= q_2 + \frac{r_3}{r_2}
= q_2 + \cfrac{1}{\cfrac{r_2}{r_3}}
= q_2 + \cfrac{1}{q_3 + \cfrac{1}{q_4 + \cfrac{1}{q_5}}} \tag{2''''} \\
\frac{a}{b} = \frac{r_0}{r_1} &= \frac{q_1r_1 + r_2}{r_1}
= q_1 + \frac{r_2}{r_1}
= q_1 + \cfrac{1}{\cfrac{r_1}{r_2}}
= q_1 + \cfrac{1}{q_2 + \cfrac{1}{q_3 + \cfrac{1}{q_4 + \cfrac{1}{q_5}}}} \tag{1''''} \\
\end{align*}
最終的に次のような互除法の各ステップの商を並べた連分数を得ることになります。
\begin{align*}
\frac{a}{b} = \frac{r_0}{r_1} = q_1 + \cfrac{1}{q_2 + \cfrac{1}{q_3 + \cfrac{1}{q_4 + \cfrac{1}{q_5}}}}
\end{align*}
互除法のステップ数が多くなるに従って、連分数の深さが増すことになるわけです。