ユークリッドの互除法

1.除法
整数aを整数bで割る割り算では，a/b=q+r/b において 0?r/b<1となるので， 商qはa/bを超えない最大の整数である． 一般に実数xに対して，xを超えない最大の整数を[x]と書き表す． この記号を用いると， q=[a/b]と書き表すことができる．

整数の集合 Zでは除法の原理が土台になる． 代数的整数といわれる世界では，この除法の原理は成り立たない． そこでは新たな考え方が必要になる． 一般化された「代数的整数」に対してわれわれの整数を「有理整数」という． 有理整数でない代数的整数は後に「ガウス整数」でその端緒を紹介する． この『整数論入門』は基本的に有理整数の世界の探求である．

これからは，特に断らなければ記号 N, Z, Q, R, C はそれぞれ， 自然数，整数，有理数，実数，複素数の集合を表すものとする．

2. 最大公約数

整数a, b, c, ・・・ の最大公約数を，座標と混同する恐れのないときは(a, b,c,・・・) と書く．
整数a, b, c,・・・ の最大公約数が1であることを簡単に 「公約数をもたない」という．この場合， (a, b, c, ・・・)=1． 特に二つの整数a, b が公約数をもたないとき，つまり (a, b)=1のとき，a, b は互いに素であるという．

3. ユークリッドの互除法

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

(ユークリッドの互除法)
a > b > 0 を整数とし, a を b で割った余りを r とする．このとき
(a, b) = (r, b)
が成り立つ．
数列 { r_n } を次のように定める．
r_1=a, r_2=b
n ?2 のとき
　r_n > 0 なら、r_(n+1)=r_(n-1) を r_n で割った余り
　r_n=0 なら、r_(n+1)=0

このときある番号 N で r_N ≠ 0で r_(N+1)=0となるものがあり，このとき
r_N=(a, b)

が成り立つ．

証明は、http://aozoragakuen.sakura.ne.jp/suuronN/node11.html　を参照。Orz〜

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

三つ以上の整数a, b, c, ・・・ の最大公約数もこれを応用して求めることができる．

a が a, b, c, ・・・ のなかの最小の数とする． a で他の数を割った余りを b', c', ・・・とする．すると上の定理と同様に
(a, b, c,・・・)=(a, b', c',・・・)


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

問題
(6188, 4709) を求めよ。

(6188, 4709)=(4709, 1479)
=(1479, 272)
=(272,119)
=(119,34)
=(34,17)
=17

問題
(629, 391, 255)=(119,136,255)=(119,17,17)=17

a < b < c のとき、
一番小さい数 c を引いた、a-m*c, b-n*c, c の中に、最大公約数はあるはずということにほかならない分けですよね。


画像：ユークリッド/エウクレイデス　Eucleidesエウクレイデス〔ユークリッド〕 (c. 330-235 B.C.)　
art-random.main.jp/ samescale/090.html　より Orz〜
「・・・一説によると、アテナイで、プラトンに数学を師事したともいわれ、のちプラトンの死後、彼が創始した哲学学校アカデメイアで数学の教師の１人だった時期があると見られている。確実なのは、彼が古代の卓越した数学者で、アレクサンドリアで数学を教えていたこと、またそこで数学の一派をなしたことである。ユークリッド幾何学の祖で、原論では、平面・立体幾何学、整数論、実数論などの当時の数学が公理的方法によって組み立てられているが、これはギリシャ数学の一つの成果として受け止められている。・・・「幾何学原論」は、ピタゴラス以来のあらゆる初期ギリシャの数学的知識を体系的に編集したものである。・・・扱われている内容は、ピタゴラスの定理をはじめとする平面幾何学、相似図形、立体幾何学などのほか、(a+b)a=aa+abのような恒等式や最大公約数、素数といった、今日私たちが代数的に扱っているものも含まれる。中世、近世を通じてユークリッド幾何学は唯一の真なる幾何学とされ、本書は幾何学の教科書として用いられた。19世紀になって、ロバチェフスキーやリーマン等が非ユークリッド幾何学の体系を作り上げたが、現在もなお中学や高校で教えられる図形問題はユークリッド幾何学である。その意味で、世界で最も長く用いられている教科書と言える」。・・・」

９０歳という長命な方だったんですねえ ^^
同じ頃のアルキメデスに関してはまたいずれ。。。v
軍人に殺されたのはアルキメデスでしたよね。。。^^;

[草木の精霊]

❀❀ユークリッドの互除法の原理を分かりやすく例で説明しますネ❀❀
♥ 6188と4709の最大公約数ってのは.....6188/4709をイッキに約分する数♪
♥ 6188/4709=1+1479/4709 なので、1479/4709をイッキに約分する数 ♬♬
♥ 逆数にして、4709/1479をイッキに約分する数 ｡o○ﾟ♫♫
♡ 4709/1479=3+272/1479 なので、272/1479をイッキに約分する数 ♬♬
♡ 逆数にして、1479/272をイッキに約分する数 ｡o☆ﾟ♫♫
♡ 1479/272=5+119/272 なので、119/272をイッキに約分する数 ♬♬
♡ 逆数にして、272/119をイッキに約分する数 ｡o○ﾟ♫♫

[草木の精霊]

♡ 272/119=2+34/119 なので、34/119をイッキに約分する数 ♬♬
♡ 逆数にして、119/34をイッキに約分する数 ｡o☆ﾟ♫♫
♡ 119/34=3+17/34 なので、17/34をイッキに約分する数 ♬♬
♡ 逆数にして、34/17をイッキに約分する数 ｡o○ﾟ♫♫,
♥ 34/17=2 だから、イッキに約分する数は分母の17 ✿✿
♥ ってことで、6188と4709の最大公約数は17ってコト。
長くなったけど♡の行はリフレインなので、テキトーにε=ε=ε=

[スモークマン]

＞草木の精霊さんへ ^^♪
分母分子を約分する数は最初からすべて共通してるから...このアルゴリズムでよいということが了解できますね ^^v Orz〜

[草木の精霊]

❀❀ユークリッドの互除法ダケド、説明がムズそうなので、
中学生でも、チャント読んだら解るようにと思って、コメしました(*⌒∇⌒*)テヘ♪

[スモークマン]

＞草木の精霊さんへ ^^
フォローサンクスです m(_ _)mγ
この欄も時間あれば完成させたいのですが...なにせ時間が足りない...^^; また気付かれましたらご協力の程よろしくお願いいたします〜〜〜♪