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

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

 今回は 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 の最大公約数です。

 ≫ 3 整数の最大公約数と最小公倍数 ≫ 初等整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

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

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください