ユークリッドの互除法の原理

ユークリッドの互除法の原理

 今回は 2000 年も昔から知られる ユークリッドの互除法 (Euclid's Algorism) の原理 という有名な定理を証明します。

[定理 A12 ユークリッドの互除法の原理]
 2 つの整数 $a,\:b\quad (a\gt b\gt 0)$ について
\[a=bq+r\quad (0\leq r\lt b)\]を満たすような $(q,\:r)$ が唯一組存在し、
\[(a,\:b)=(b,\:r)\]が成り立ちます。

[定理 A12 の証明] $a=bq+r\quad (0\leq r\lt b)$ を満たすような $(q,\:r)$ が唯一組だけ存在することは 定理A1 で述べてあります。ここでは
 
\[(a,\:b)=(b,\:r)\]
が成り立つことを証明します。
 
\[g_1=(a,\:b),\quad g_2=(b,\:r4)\]
とおきます。$a=bq+r$ なので
 
\[r=a-bq\]
と書き直すと、$a,\:b$ ともに $g_1$ を約数にもつので、$a,\:b$ の 1 次結合 $r$ もまた $g_1$ を約数にもちます
 
\[g_1\:|\:r\]
です。$g_1$ は $b$ と $r$ の公約数なので、$b$ と $r$ の最大公約数以下となっているはずです。
 
\[g_1\leq g_2\]
 同様に $a=bq+r$ において、$b,\:r$ ともに $g_2$ を約数にもつので、その 1 次結合である $a$ も $g_2$ を約数にもちます。すなわち $g_2$ は $a$ と $b$ の公約数なので、$a$ と $b$ の最大公約数以下となっているはずです。
 
\[g_1\geq g_2\]
 $g_1\leq g_2$ かつ $g_1\geq g_2$ なので
 
\[g_1=g_2\]
が成り立ちます。すなわち
 
\[(a,\:b)=(b,\:r)\]
が成り立つことが示されました。(証明終)
 

ユークリッドの互除法

 $a_1\gt a_2\gt 0$ なる 2 整数について、除算アルゴリズムを次々に適用してみます。
 
\[\begin{align*}&a_1=a_2\,q_1+a_3\quad (0\leq a_3\lt a_2)\\[6pt]
&a_2=a_3\,q_2+a_4\quad (0\leq a_4\lt a_3)\\[6pt]
&a_3=a_4\,q_3+a_5\quad (0\leq a_5\lt a_4)\\[6pt]
&\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\end{align*}\]
 $a_1\gt a_2\gt a_3\gt\cdots$ なので、いつかは余りが 0 となって割り切れます。
 それが $n$ 回目であったとすると
 
\[\begin{align*}&a_3=a_4\,q_3+a_5\quad (0\leq a_5\lt a_4)\\[6pt]
&\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\\[6pt]
&a_{n-1}=a_n\,q_{n-1}+a_{n+1}\quad (0\leq a_{n+1}\lt a_n)\\[6pt]
&a_n=a_{n+1}q_n\end{align*}\]
となります。そこで定理 A12(ユークリッドの互除法の原理)を適用すると
 
\[(a_1,\:a_2)=(a_2,\:a_3)=(a_3,\:a_4)=\:\cdots\:=(a_n,\:a_{n+1})=a_{n+1}\]
となります。すなわち最後に $a_n$ を割り切った $a_{n+1}$ が最大公約数であるということです。
 

ユークリッドの互除法の具体例

 簡単な例として 556 と 208 の最大公約数を求めてみます。
 
\[\begin{align*}556&=208\times 2+140\\[6pt]
208&=140\times 1+68\\[6pt]
140&=68\times 2+4\\[6pt]
68&=4\times 17\end{align*}\]
 最後に 68 を割り切った 4 が 556 と 208 の最大公約数です。
 

ユークリッドの互除法の視覚化

 ユークリッドの互除法を視覚化してみましょう。
 例として、72 と 56 の最大公約数を求めます。

 ユークリッドの互除法説明図

 横が 72, 縦が 56 の長方形です。作業は簡単です。
 まず、この長方形からなるべく大きな正方形ができるように切込みを入れます。
 1辺の長さ 56 の青い正方形が1つとれましたね。
 もとの長方形の辺の長さを、この青い正方形の1辺を使って表すと、

72 = 56 × 1 + 16

となります。今度は青い正方形を切り離してしまって、右側の細長い長方形からなるべく大きな正方形がとれるように切込みを入れます。1辺の長さ 16 赤い正方形が 3 つとれます。式で表すと、

56 = 16 × 3 + 8

です。残ったのは1辺の長さ 16 の緑色の長方形で、これは

16 = 8 × 2

と 2 つに分けることができます。もとの長方形は1辺が 8 の正方形タイルできれいに敷き詰めることができます。つまり 72 と 56 の最大公約数は 8 だということです。これが最大公約数の図形的な意味です。上の計算式をまとめて書いてみます。

  72 = 56 × 1 + 16

  56 = 16 × 3 + 8

  16 = 8 × 2  ∴ 8 が最大公約数

 もう少し簡略化して書くと、

  72 ÷ 56 = 1 [余り 16]

  56 ÷ 16 = 3 [余り 8]

  16 ÷ 8 = 2  [余り 0]  ∴ 8 が最大公約数

というように計算します。除数(割る数)を余りで割ることの繰返しですね。それでは問題でいくつか練習してみましょう。


 

コメントをどうぞ

メールアドレスが公開されることはありません。