問題はこちら（画像をクリックするとPDFファイルで開きます。）
２つの正整数の最大公約数を求めるときに用いられる「ユークリッドの互除法」と呼ばれるアルゴリズムについて、原理と証明を考えてみます。
古典的な手法による証明だけでなく、ユークリッドの互除法の原理が主張している内容が「当然じゃん」と思えるようなイメージをもつことで身近に感じてもらうとともに、自分の中にしっかりと落とし込むことを目的とします。
ユークリッドの互除法とは
以下 , 2 つの整数 \(a\) , \(b\) の最大公約数を \(G(a \ , \ b)\) と表します。
互除法の原理
\(a\) , \(b\) を \(a \gt b\) を満たす正の整数とする。
\(a\) を \(b\) で割った商を \(q\) , 余りを \(r\) とするとき、
\(G(a \ , \ b)=G(b \ , \ r)\)
が成立する。
この原理を用いて２つの数の最大公約数を探すプロセスを、ユークリッドの互除法と言います。
最大公約数を求めてみる
具体例１
例題１
\(437\) と \(247\) の最大公約数を求めよ。
解答例
\(437=19 \times 23\)
\(247=19 \times 13\)
なので、最大公約数は \(19\)
このように、素因数分解ができれば、解決するのは言うまでもありません。
ただし、数が大きくなってくると話が変わってきます。
具体例２
例題１
\(1517\) と \(851\) の最大公約数を求めよ。
数が大きいため、素因数分解をするにも苦労します。
そこで先ほどの
互除法の原理
\(a\) , \(b\) を \(a \gt b\) を満たす正の整数とする。
\(a\) を \(b\) で割った商を \(q\) , 余りを \(r\) とするとき、
\(G(a \ , \ b)=G(b \ , \ r)\)
が成立する。
の出番です。
解答例
\(1517=851 \cdot 1+666\) より
\(G(1517 \ , \ 851)=G(851 \ , \ 666)\)
\(851=666 \cdot 1+185\) より、
\(G(851 \ , \ 666)=G(666 \ , \ 185)\)
\(666=185 \cdot 3+111\) より、
\(G(666 \ , \ 185)=G(185 \ , \ 111)\)
\(185=111 \cdot 1+74\) より、
\(G(185 \ , \ 111)=G(111 \ , \ 74)\)
\(111=74 \cdot 1+37\) より、
\(G(111 \ , \ 74)=G(74 \ , \ 37)\)
\(74=37 \cdot 2\) より、
\(G(74 \ , \ 37)=37\)
であり、求める最大公約数は \(37\)
ユークリッドの互除法のうまみ
ユークリッドの互除法のうまみは、余りを用いることで、数がどんどん小さくしても、求める最大公約数は変化しないということです。
したがって、数が大きな２数の最大公約数を求めるにあたっては必須のアルゴリズムと言えます。
互除法の原理の証明
問題はこちら（再掲）（画像をクリックするとPDFファイルで開きます。）
ユークリッドの互除法の証明方法の１つとして、有名な手法があります。
詳しい導出過程は【解答】の中で説明していますが、簡単な流れだけここで押さえます。
狙い筋
\(a\) , \(b\) の最大公約数を \(G\) , \(b\) , \(r\) の最大公約数を \(G'\) として
- \(G \geq G'\) を示す。
- \(G \leq G'\) を示す
という２つのことを示すことで、\(G=G'\) を得るというのが狙い筋です。
これは経験がないと、中々難しい部分があります。
互除法をもう少し身近に
そもそも、単元学習においてユークリッドの互除法を学んだとき
「へぇ～」と思いましたか？それとも「え、当然じゃない？」と思いましたか？
身近に感じないと、自分の中に中々入ってこないでしょう。
互除法の主張を少しでも身近に感じるための、「原理」のイメージを押さえたいと思います。
そのために、一つあることをインストールします。
互いに素な２数の差
補題
\(p\) , \(q\) を \(p \gt q\) で、互いに素である正の整数とするとき、
\(q\) と \(p-q\) も互いに素
である。
ということが言えます。
補題の証明
\(p\) , \(q\) が互いに素であるとき、\(q\) と \(p-q\) が互いに素でないと仮定する。
このとき、\(q\) と \(p-q\) は、\(2\) 以上の公約数 \(g\) をもつため、整数 \(K\) , \(L\) を用いて
$$\begin{eqnarray}
\left\{
\begin{array}{l}
q = gK \\
p-q = gL
\end{array}
\right.
\end{eqnarray}$$
と表せる。
よって、これらの辺々を加えると \(p=g(K+L)\) となり、\(p\) , \(q\) は \(2\) 以上の公約数 \(g\) をもつことになり、互いに素であることに矛盾する。
互除法のイメージ
\(a \gt b\) である２つの正整数 \(a\) と \(b\) の最大公約数を \(G\) とします。
このとき、互いに素である２つの正整数 \(\alpha\) , \(\beta\) ( \(\alpha \gt \beta\) ) を用いて
$$\begin{eqnarray}
\left\{
\begin{array}{l}
a = G\alpha \\
b = G\beta
\end{array}
\right.
\end{eqnarray}$$
と表せます。
これより、\(a-b=G(\alpha-\beta)\) を得ます。
補題より、\(\beta\) , \(\alpha-\beta\) は互いに素であるため、
\(b\) と \(a-b\) の最大公約数も \(G\) であることが言えます。
つまり、
引いても最大公約数は変化しない
というわけです。
ということは、\(a\) から \(b\) を出来る限り引いてやった
\(a-\overbrace{b-b-b-b-\cdots-b}^{q個}\)
で考えても最大公約数は変化しません。
このとき、
\(a-\overbrace{b-b-b-b-\cdots-b}^{q個}=r\)
すなわち
\(a-bq=r\)
とすれば
\(G(a \ , \ b)=G(b \ , \ a-bq)\)
すなわち
\(G(a \ , \ b)=G(b \ , \ r)\)
ということになるわけです。
\(a\) から \(b\) を出来る限り引いたときの回数を「商」、これ以上引けなくなって残ったものを「余り」と呼んでいたわけです。
引いても最大公約数は変化しないんだったら、引けるだけ引いて小さくしてやろう
というのが人情でしょう。
この気持ちがあれば、互除法の原理の主張が少しは身近に感じて、「そりゃそうだわな」と感じてもらえるかなと思います。