次: 一次不定方程式 上: 約数と倍数 前: 最大公約数と最小公倍数

ユークリッドの互除法

ここで，最大公約数を求める一般的な方法であるユークリッドの互除法をまとめよう．

エウクレイデス

「エウクレイデス」のことを英語では「ユークリッド」という．最近は「マホメット」も「ムハンマド」というように，本来の読みで書くのが習わしだ．ただ,「ユークリッド」はあまりにも定着しているので，幾何学をさすときは「ユークリッド幾何学」のようにもいうことにする．

公理を立て，公理からはじめて論証を進め，新たに発見された事実を揺るぎないものとして示す，という幾何の論証はエウクレイデスにはじまる． それをまとめたものが『(幾何学)原論』である．これは複数人の共著であり， その一人がエウクレイデスであるといわれている．

エウクレイデス（Eukleides，紀元前365年〜紀元前275年，英語表記 Euclid）は古代ギリシアの数学者，天文学者とされる人で，アテナイで学びプトレマイオス1世治下のアレクサンドリアで教えた．ちなみにプトレマイオス1世とは，アレクサンドロス3世（アレキサンダー大王）の部下であったマケドニア地方出身のギリシア人で，大王の死後，エジプトの支配を継ぎ，プトレマイオス朝を創始した．

『原論』はラテン語圏，アラビア語圏にもたらされ，その後各地で二千数百年にわたって幾何学，いや数学そのもの基本となる書物であった．この書は13巻から成り，1〜6巻は平面幾何，7〜9巻は数論，10巻は無理量，11〜13巻は立体幾何を取り扱っている．

図形以外では，最大公約数を求める方法であるユークリッドの互除法，素数の個数は無限であることの背理法による証明，などが書かれている.『原論』では，概念の定義から始まり，公準（要請）・公理・命題とその作図・証明・結論という形式で書かれている． 公準とは公理のように自明ではないが，公理と同様，証明不可能な命題を意味する．近代ではこれを含めて公理とすることが一般的である.「公準」と訳されるものもここでは公理に統一する．

『原論』はこのような形式で数学を論述する．自明なことをまず明らかにし，そこからはじめて厳格な論証によって数学的現象を論述していく，この学問記述の方法は，二千年以上にわたって，数学のみならす学問一般の模範であった．いまもその精神は受け継がれるべきものである．

『原論』の原典としては例えば『ユークリッド　原論(試案)』 等にある．

ユークリッドの互除法

24と42の最大公約数を求めようとすれば，いずれをも割り切る素数を見い出して，順に割っていくのだ．

$$(24,\ 42)=2\cdot (12,\ 21)=2\cdot 3\cdot(4,\ 7)=6$$

しかしこの方法には欠点がある．暗算で見つかるような素数ならよいが，6188と4709 のように少し大きい素数となると，なかなか難しい． ところが，つねに最大公約数を見い出すことのできる方法がある． それがユークリッドの互除法である．その根拠は次のような除法の式からの結論である．

定理 3 (ユークリッドの互除法)

(1)

$a>b>0$ を整数とし, $a$ を $b$ で割った余りを $r$ とする．このとき

$$(a,\ b)=(r,\ b)$$

が成り立つ．

(1)

数列 $\{ r_n \}$ を次のように定める．

$$\left\{ \begin{array}{l} r_1=a,\ r_2=b\\ n \ge 2 ... ...\ \quad r_n=0なら， r_{n+1}=0 \end{array} \right.$$

このときある番号 $N$ で $r_N\ne 0$ で $r_{N+1}=0$ となるものがあり

$$r_N=(a,\ b)$$

が成り立つ．■

証明    
(1)    $(a,\,b)=d_1$ とすると $a=a'd_1,\;b=b'd_1$ とおける.

$$r=a'd_1-b'd_1q=d_1(a'-b'q)$$

これより$r$ も $d_1$ で割れる. よって,$d_1$ は $b$と$r$ の公約数なので, $d_1\leq (b,\,r)=d_2$． 次に$(b,\,r)=d_2$ とすると, $b=b'd_2,\;r=r'd_2$ とおける.

$$a= b'd_2q+r'd_2= d_2(b'q+r')$$

より同様に $d_2\leq (a,\,b)=d_1$．よって $d_1=d_2$ ，つまり

$$(a,\,b)=(b,\,r)$$

(2)    除法の定理から$r_k>0なら$

$$r_1=a>r_2=b>r_3>\cdots >r_k >r_{k+1}\ge r_{k+2} \ge \cdots \ge 0$$

自然数の単調減少列なのである番号 $N$ で

$$r_N> 0 かつ r_{N+1}=0$$

となる．このとき $r_{N-1}$は $r_N$の倍数になる．よって (1)より

$$(a,\,b)=(b,\,r_3)=\cdots =(r_{N-1},\,r_N)=r_N$$

□

これが最大公約数を求める一般的な方法で ユークリッドの互除法 といわれる．このように「必ずできる一般的方法」をアルゴリズムという．ユークリッドの互除法はアルゴリズムの基本例である．

三つ以上の整数 $a,\ b,\ c,\ \cdots$ の最大公約数もこれを応用して求めることができる．$a$ が $a,\ b,\ c,\ \cdots$ のなかの最小の数とする．$a$ で他の数を割った余りを $b',\ c',\ \cdots$ とする．すると上の定理と同様に

$$(a,\ b,\ c,\ \cdots)=(a,\ b',\ c',\ \cdots)$$

この操作を繰り返すと余りのなかに0が現れる．それを取り除いてさらに同様の操作を繰り返す．ついにはただひとつの数が残る．それが $a,\ b,\ c,\ \cdots$ の最大公約数である．

例 1.3.1        $(6188,4709)$を求めよう．

順次割り算を行うことにより次の系列を得る．

$$\begin{eqnarray*} (6188,\,4709)&=&(4709,\,1479)\\ &=&(1479,\,272)\\ &=&(272,\,119)\\ &=&(119,\,34)\\ &=&(34,\,17)=17 \end{eqnarray*}$$

例 1.3.2  

$$(629,391,255)=(119,136,255)=(119,17,17)=17$$

次: 一次不定方程式 上: 約数と倍数 前: 最大公約数と最小公倍数