POINT
- 整数の最大公約数の求め方．
- 繰り返し2数の割り算を計算することで，最大公約数がわかる．
整数$a$と$b$の最大公約数を求める方法に「ユークリッドの互除法」と呼ばれる方法があります．
名前は難しそうですが，やっていることはとても簡単です．実際，英語では "Euclidean algorithm" （ユークリッドの方法くらいの意味）です．
次のような応用ができます：
- 分母・分子が大きい数の分数の約分を行う．
- これ以上分数の約分ができないこと（＝分母と分子の最大公約数が1であること）を示す．
まずは図で理解するとわかりやすいでしょう：
手順
整数$a_1$と$a_2$を考えます．マイナスの整数の約数の場合は符号を除いて考えるので，$a_1 \geq a_2 > 0$の場合を考察すれば十分です．このとき
\begin{aligned}
& a_1\text{と}a_2\text{の最大公約数} \\
=&\, a_2\text{と「} a_1\div a_2 \text{の余り}a_3\text{」の最大公約数} \\
=&\, a_3\text{と「} a_2\div a_3 \text{の余り}a_4\text{」の最大公約数} \\
=&\, \cdots
\end{aligned}
であることが示せます（次節）．割り算において，（割る数）＞（余り）であることに注意すれば& a_1\text{と}a_2\text{の最大公約数} \\
=&\, a_2\text{と「} a_1\div a_2 \text{の余り}a_3\text{」の最大公約数} \\
=&\, a_3\text{と「} a_2\div a_3 \text{の余り}a_4\text{」の最大公約数} \\
=&\, \cdots
\end{aligned}
\begin{aligned}
a_1 \geq a_2 > a_3 > \cdots \geq 0
\end{aligned}
ですが，$a_1,a_2,a_3,...$は全て整数なので，ある$N$で$a_N=0$となります．a_1 \geq a_2 > a_3 > \cdots \geq 0
\end{aligned}
これは「$a_{N-2}$と$a_{N-1}$の最大公約数」が$a_{N-1}$であることを意味しています（$a_{N-2}\div a_{N-1}$の余り＝$a_N=0$）．したがって
\begin{aligned}
& a_1\text{と}a_2\text{の最大公約数} \\
=&\, \cdots \\
=&\, a_{N-2}\text{と「} a_{N-3}\div a_{N-2} \text{の余り}a_{N-1}\text{」の最大公約数} \\
=&\, a_{N-1}
\end{aligned}
となり，$a_1$と$a_2$の最大公約数を求めることができます．& a_1\text{と}a_2\text{の最大公約数} \\
=&\, \cdots \\
=&\, a_{N-2}\text{と「} a_{N-3}\div a_{N-2} \text{の余り}a_{N-1}\text{」の最大公約数} \\
=&\, a_{N-1}
\end{aligned}
証明
整数$a$と$b$を考えます（$a \geq b>0$）．以下を示せば，上の手順が示されたことになります：示したい性質
[$a,b$の最大公約数] ＝ [$b$と「$a\div b$の余り」の最大公約数]
【証明】
$a\div b$を考えてみましょう．商を$q$，余りを$r$とすると
\begin{aligned}
a=bq+r \qquad(0\leq r < b )
\end{aligned}
と表すことができます．a=bq+r \qquad(0\leq r < b )
\end{aligned}
この式は，「$b,r$の公約数は$a$の約数である」ことを意味しています（右辺を割り切る数は，左辺も割り切る）．特に，「$b,r$の公約数は$a,b$の公約数である」ということがわかるので，
ここで，
\begin{aligned}
r=a-bq
\end{aligned}
と書き直してみると，全く同様に「$a,b$の公約数は$r$の約数」となり「$a,b$の公約数は$b,r$の公約数である」ことがわかります．したがって，r=a-bq
\end{aligned}
以上(1), (2)から
